二叉树非递归后序遍历

《二叉树非递归后序遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验题目：树的应用实验目的：（1）针对问题的实际要求，正确应用树形结构组织和存储数据；（2）掌握二叉树的存储方法；（3）掌握二叉树的各种遍历方法。实验内容：二叉树后序遍历的非递归算法。设计分析：实验要求完成用非递归算法实现对二叉树的后序遍历，过程包括建立二叉树的链式存储结构、创建二叉树和对二叉树进行非递归的后序遍历。实验所需要的二叉树要用括号表示法输入进去，创建二叉树时，先用字符数组ch存放采用括号表示法表示二叉树的字符串，再对字符串逐一进行扫描，期间用栈存储双亲结点，通过进栈和出栈将这个字符串所描述的二叉树完整地存放在链式

2、结构中。在后续遍历中，对于每个结点，先访问其左子树，然后访问右子树，最后才是该结点本身，所以必须告知节点，其左右子树是否访问过。采用一个栈保存需要返回的结点指针，先扫描根结点的所有左结点并一一进栈，出栈一个结点*b作为当前结点，然后扫描该结点的右子树。当一个结点的左右子树均访问后再访问该结点，如此这样，直到栈空为止。源程序代码：#include#include#include#defineMaxSize20//结点数最多为20#defineMaxChar50//数组最

3、多元素typedefcharElemType;typedefstructnode//二叉树链式存储结构{ElemTypedata;structnode*lchild;structnode*rchild;}BTNode;voidCreatBTNode(BTNode*&b,char*str)//创建二叉树{BTNode*St[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;b=NULL;ch=str[j];while(ch!=''){switch(ch){case'(':top++;St[to

4、p]=p;k=1;break;case')':top--;break;case',':k=2;break;default:p=(BTNode*)malloc(sizeof(BTNode));p->data=ch;p->lchild=p->rchild=NULL;if(b==NULL)b=p;else{switch(k){case1:St[top]->lchild=p;break;case2:St[top]->rchild=p;break;}}}j++;ch=str[j];}}voidPostOrder(BTNode*b)//

5、非递归后序遍历{BTNode*St[MaxSize];BTNode*p;intflag,top=-1;if(b!=NULL){do{while(b!=NULL){top++;St[top]=b;b=b->lchild;}p=NULL;flag=1;while(top!=-1&&flag){b=St[top];if(b->rchild==p){printf("%c",b->data);top--;p=b;}else{b=b->rchild;flag=0;}}}while(top!=-1);printf("");}}void

6、main(){BTNode*BT;charch[MaxChar];printf("请用括号表示法输入二叉树:");scanf("%s",&ch);CreatBTNode(BT,ch);printf("该二叉树后序遍历序列为:");PostOrder(BT);}测试用例：对图示二叉树进行测试，括号法表示为A(B(D(,G)),C(E,F))，后序遍历序列G,D,B,E,F,C,A.ABCDGEF图6-1图6-2程序执行初始界面，要求用括号表示法输入二叉树。图6-3输入所给二叉树的括号表示“A(B(D(,G)),C(E,

7、F))”，如图6-3所示。按下Enter后，即输出其后序遍历序列：GDBEFCA，如图6-4所示。图6-4输入其他二叉树的括号表示法，也可得到对应的后序遍历序列，如图6-5所示。图6-5实验总结：本次试验通过对二叉树实现非递归的后序遍历，我了解并学会使用二叉树的链式存储结构，以及针对二叉树的括号表示法进行二叉树链式结构的创建。最大的收获还是学会了使用非递归算法实现二叉树的后序遍历，之前用递归算法只需使用递归函数层层调用，而今通过研究使用非递归算法进行这项工作并不能说多余，因为非递归算法中结合了二叉树和栈的相关运算，使我对栈的

8、应用又更深了一步。