2016新编二叉树非递归后序遍历

2016新编二叉树非递归后序遍历

ID:25464468

大小:139.00 KB

页数:28页

时间:2018-11-20

2016新编二叉树非递归后序遍历_第1页
2016新编二叉树非递归后序遍历_第2页
2016新编二叉树非递归后序遍历_第3页
2016新编二叉树非递归后序遍历_第4页
2016新编二叉树非递归后序遍历_第5页
资源描述:

《2016新编二叉树非递归后序遍历》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

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

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

3、har50//数组最多元素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

4、'(':top++;St[top]=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];}}voidP

5、ostOrder(BTNode*b)//非递归后序遍历{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

6、!=-1);printf("");}}voidmain(){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

7、-3输入所给二叉树的括号表示“A(B(D(,G)),C(E,F))”,如图6-3所示。按下Enter后,即输出其后序遍历序列:GDBEFCA,如图6-4所示。图6-4输入其他二叉树的括号表示法,也可得到对应的后序遍历序列,如图6-5所示。图6-5实验总结:本次试验通过对二叉树实现非递归的后序遍历,我了解并学会使用二叉树的链式存储结构,以及针对二叉树的括号表示法进行二叉树链式结构的创建。最大的收获还是学会了使用非递归算法实现二叉树的后序遍历,之前用递归算法只需使用递归函数层层调用,而今通过研究使用非递归算法进行这项工

8、作并不能说多余,因为非递归算法中结合了二叉树和栈的相关运算,使我对栈的应用又更深了一步。---------------------------------------------------------------范文最新推荐------------------------------------------------------电力安全月工作总结[电力安

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。