数计学院数据结构二叉树遍历课程设计(2)

}

⑨二叉树的非递归后序遍历：

void houxu(treenode* b)

{

treenode *stack[MAXSIZE], *p;

int sign, top = -1;

printf("非递归后序遍历:\t");

if (b != NULL)

{

do

{

while (b != NULL)

{

top++;

stack[top] = b;

b = b->left;

}

p = NULL;

sign = 1;

while (top != -1 && sign)

{

b = stack[top];

if (b->right == p)

{

printf("%d\t", b->data);

top--;

p = b;

}

else

{

b = b->right;

sign = 0;

}

}

}

while (top != -1);

printf("\n");

}

}

附：由于程序只是递归遍历与非递归遍历的算法不一样，实现的代码不一样，但是main函数部分绝大部分是一样的，就不一一列举了。

五.测试与结论

图一 创建二叉树，输入数据

图二 输入数据后选择功能

图三 选择1,2,3功能，实现二叉树三种递归遍历， 其间可选择继续或者退出

图四 选择4实现查找节点功能

图五 若输入没有的功能号，程序将报错并可重新输入

图六 非递归的三种遍历，功能与递归的几乎一样

结论：本次的课程设计能成功的实现老师要求程序所具有的功能，并加以改进。因为递归与非递归的程序运行结果一样，所以在此非递归的程序运行图就不一一截取了。

六.课程设计总结

通过这次的实验，明白了用具有递归功能的程序设计语言就能很方便的实现二叉树递归遍历，二叉树的非递归遍历算法是通过建立栈来实现的。我不仅写出了二叉树递归与非递归的三种遍历，而且还加入了查找节点与菜单选择功能，使程序更美观，更人性化。经过此次试验，我发现自己对链式存储与函数的调用这两方面运用的还不是很熟练，同时也明白我还有好东东西没有学习和掌握，以后我会更加的努力的去自我学习，争取能够对一些简单的程序信手拈来。