由中序和后序遍历确定二叉树

《由中序和后序遍历确定二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》课程设计设计题目：由中序和后序遍历确定二叉树姓名：吴剑院系：计算机科学与技术学院专业：计算机科学与技术年级：12级学号：E01214180指导老师：王爱平2014年10月26日目录一、课程设计的目的：3二、需求分析：3三、由中序和后序确定二叉树的设计：41、概要设计：42、详细设计：63、调试分析：8四、总结：9五、程序清单：(见附录)9六、参考文献：9七、程序运行结果：10附录：11一、课程设计的目的：(1)熟练使用C语言编写程序，解决实际问题;(2)了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3)初步掌握软件开发过程的问题分析、系统

2、设计、程序编码、测试等基本方法和技能;(4)提高综合运用所学的理论知识和方法独立分析和解决问题的能力;二、需求分析：此次程序讨论由二叉树的中序和后序确定二叉树并且输出这课二叉树，由理论知识知道，确定中序和后序就一定能确定这棵二叉树。解决这个问题，有以下需求：1.程序用到的树的数据结构：typedefstructnode{chardata;node*lchild;node*rchild;}bitree;2.从递归算法和非递归算法两个方面考虑，分别用两个函数封装起来，便于管理；由二叉树的递归定义可知,二叉树由3个基本单元组成:根结点、左子树和右子树。因此,若能依次遍历这3部分

3、,便是遍历了整棵二叉树。若限定先左后右,则有先序遍历、中序遍历和后序遍历3种遍历方式。基于二叉树的递归定义,可以很容易地得到遍历二叉树的递归算法。用非递归算法时，可能要考虑到要用到栈，便于存放信息。1.还要设计一个选择菜单，便于用户选择需要使用的算法。2.最后还需要一个输出函数printtree（），用来显示所有求的二叉树。三、由中序和后序确定二叉树的设计：1、概要设计：.程序需要的数据结构有：typedefstructnode{chardata;node*lchild;node*rchild;}bitree；//二叉树typedefstruct{bitree*paren

4、t;intflag;inti,j,n;}Elem;typedefstruct{Elem*base;Elem*top;intstacksize;intlength;}SqStack;//栈用函数node*creat1（char*inlist,char*postlist,inti,intj,intk,intl）实现递归算法，具体步骤如下:(1)如果后序和中序遍历序列都为空,则该二叉树是空树。(2)对于有n(n 1)个结点的二叉树,把后序遍历序列中的最后一个结点作为该二叉树的根结点。(3)在中序遍历序列中找到根结点,记录该结点的位置n。(4)在中序遍历序列中根结点前面的n-1个

5、结点序列就是根结点左子树的中序遍历序列;在中序遍历序列中根结点后面的结点序列就是根结点右子树的中序遍历序列。(5)在后序遍历序列中前n-1个结点序列就是根结点左子树的后序遍历序列;在后序遍历序列中后面的结点(除根结点)则是根结点右子树的后序遍历序列。(6)以此类推重复步骤(2)~步骤(5)就可以由后序遍历序列和中序遍历序列唯一确定。用函数node*create2(char*inlist,char*postlist,intn)实现非递归算法。具体算法如下：(1)若二叉树为空,返回一棵空树;(2)以二叉树后序序列的最后一个结点建立根结点;(3)在中序序列中找到根结点的位置,并

6、记录该位置n。中序序列的前n-1个元素和后序序列的前n-1个元素分别为根结点的左子树的中序序列和后序序列,剩下的元素(除根结点外)则分别为根结点的右子树的中序序列和后序序列;(4)把左子树的相关信息入栈;(5)把右子树的相关信息入栈;(6)出栈;(7)判断栈的长度是否大于0,大于0则回到步骤(2),否则回到步骤(8);(8)栈空,返回二叉树的根结点,结束程序用函数printtree（）实现二叉树的显示。2、详细设计：由中序和后序确定二叉树的递归算法：node*create1(char*inlist,char*postlist,inti,intj,intk,intl){in

7、tn;bitree*p;p=(bitree*)malloc(sizeof(bitree));p->data=*(postlist+l);n=i;for(;(*(inlist+n)!=*(postlist+l));n++);if(n==i)p->lchild=0;elsep->lchild=create1(inlist,postlist,i,n-1,k,k+n-i-1);if(n==j)p->rchild=0;elsep->rchild=create1(inlist,postlist,n+1,j,k+n-i,l-1);retur