实习二【唯一的确定一颗二叉树】.doc

《实习二【唯一的确定一颗二叉树】.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.实习二1.需求分析：【问题描述】：如果给出了遍历二叉树的前序序列和中序序列，则可以构造出唯一的二叉树。试编写实现上述功能的程序。【基本要求】：已知一颗二叉树的前序和中序序列，试设计完成下列任务的一个算法。（1）构造一颗二叉树。（2）证明构造正确（即分别以前序和中序遍历该树，将得到的结果与给出的序列进行比较）。（3）对该二叉树进行后序遍历，输出后续遍历序列。（4）用凹入法输出该二叉树。【开发环境】：系统：windows7编程软件：VC++6.0..2.设计：给定二叉树结点的前序序列和中序序列，可以唯一确定该二

2、叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设l个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设r个元素）是右子树，若为空，则右子树为空。根据前序遍历中“根—左子树—右子树”的顺序，则由从第二元素开始的l个结点序列和中序序列根左边的l个结点构成左子树，由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树。假设一棵二叉树中结点的个数为n,即该棵二叉树的前序遍历序列为q1,q2,q3,⋯,qn,中序遍历序列为z1,z2,z3,⋯,zn,用数学归纳法证明

3、由这两个序列能够唯一地确定一棵二叉树Bt.当n=1时,即前序遍历序列和中序遍历序列均只有一个元素,且相同,即为树的根,由此唯一地确定了一棵二叉树。现在假设n

4、m}为右子树的中序序列。若j=1,即z1为根,此时二叉树的左子树为空,{q2,q3,⋯,qm}为左子树的前序序列,{z2,z3,⋯,zm}为右子树的中序序列。右子树的结点数为m-1,根据假设,这两个序列唯一确定了一棵右子树。因此,唯一确定的一棵二叉树是由z1为根,该棵右子树为右子树(唯一确定的这棵二叉树无左子树)来构成。若j=m,即zm为根,此时二叉树的右子树为空,{q1,q2,⋯,qm-1}为左子树的前序序列,{z1,z2,⋯,zm-1}为左子树的中序序列。左子树的结点数为m-1,根据假设,这两个序列唯一地

5、确定了一棵左子树。因此,唯一确定的一棵二叉树是由zm为根,该棵左子树为左子树(唯一确定的这棵二叉树无右子树)来构成。若2

6、后序遍历序列和中序遍历序列,也能够唯一地确定一棵二叉树。具体思想例如：前序序列为ABDEGCFHIJ，中序遍历为DBGEAHFIJC由前序遍历可确定根为A，中序遍历可得A的左右子树分别包含结点有DBGE、HFIJC构造A的左子树：A的左子树分别包含结点有DBGE，由前序遍历可知B为根结点，B的左右子树分别包含结点有D、GE。则B的左子树为就为D，然后构造B右子树，由前序遍历可知E为根结点，B的右子树的中序遍历知G为E的左孩子。..同理可以构造出A的右孩子结构体定义：typedefstructNode{Data

7、Typedata;structNode*leftChild;//左指数指针structNode*rightChild;//右指数指针}BiTreeNode;//结点的结构体定义..创建二叉树函数：BiTreeNode*TreeCreat(char*a,charb[],intc)//创建二叉树函数{BiTreeNode*r;charpa[100],pb[100];inti,j,q,n;Initiate(&r);n=strlen(b);if(n==0){returnNULL;}else{r->data=(*a);

8、for(i=0;ileftChild=TreeCreat(a+1,pa,i);//插入左子树r->rightChild=TreeCreat(a+n+1,pb,c-i-1