实习二唯一的确定一颗二叉树

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

2、边（设I个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设r个元素）是右子树，若为空，则右子树为空。根据前序遍历中“根一左子树一右子树”的顺序，则由从第二兀素开始的I个结点序列和中序序列根左边的I个结点构成左子树，由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树。假设一棵二叉树中结点的个数为n,即该棵二叉树的前序遍历序列为q1, q2, q3, ?, qn ,中序遍历序列为z 1, z 2, z 3, ?, z n ,用数学归纳法证明由这两个序列能够唯一地确定一棵二叉树B t.当n= 1时，即前序遍历序列和中序遍历序列均只有一个元素，且相同，即为树的根，由此唯一地确

3、定了一棵二叉树。现在假设n m - 1时命题成立，则需要证明当n= m时亦成立。当n=m时，前序序列为q1, q2, q3, ?, qm ,中序序列为z 1, z 2, z 3, ?, zm.因为前序序列由前序遍历二叉树 所得,则q1必为根结点这个兀素；又中序序列由中序遍历二叉树所得,则在中序序列中必能找到和q1相同的元素，设为z j ,由此z 1, z 2, ?, z j - 1为左子树的中序序列，zj+1, z j+ 2, ?, zm 为 右子树的中序序列。若j= 1,即z 1为根，此时二叉树的左子树为空，q2, q3, ?, qm 为左子树的前 序序列，z 2, z 3, ?, zm 为

4、右子树的中序序列。右子树的结点数为m - 1,根据假设，这两个序列唯一确定了一棵右子树。因此，唯一确定的一棵二叉树是由 z1为根，该棵右子树为右子树（唯 一确定的这棵二叉树无左子树 ）来构成。若=m ,即zm为根，此时二叉树的右子树为空，q1, q2, ?, qm- 1为左子树的前序序列，z 1, z 2, ?,zm - 1为左子树的中序序列。左子树的结点数为 m - 1,根据假设，这两个序列唯一地确定了一棵左子树。因此，唯一确定的一棵二叉树是由 zm为根,该棵左子树为左子树（唯一确定的这棵二叉树无右子树 ）来构成。若2 jdata=(*a);for(i=0;i n ;i+)if(bi=(*a

5、)break;pai=bi;pai=0：q=i;for(j=0;jleftChild=TreeCreat(a+1,pa,i); 插入左子树 r-rightChild=TreeCreat(a+n+1,pb,c-i-1);插入右子树return r;打印二叉树：void Prin tBiTree(BiTreeNode *t,i nt n)/逆时针寻转打印二叉树，n为缩进层数，初始值为0int i;if(t=NULL)return; 递归出口Prin tBiTree(t-rightChild, n+1);遍历打印右子树II访问根结点for(i=0;i=0)prin tf(-);prin tf(%cn

6、,t-data);PrintBiTree(t-leftChild,n+1); 遍历打印左子树void Destroy(BiTreeNode *p) 删除二叉树if(*p)!=NULL&(*p)-leftChild!=NULL)Destroy(&( *p)-leftChild);if(*p)!=NULL&( *p)-rightChild!=NULL)Destroy(&(*p)-rightChild);free(*p);3.调试分析唯一的确定一颗二叉树在调试时，问题主要出现在创建二叉树函数上，其中需要在定义 两个数组 pa1OO,pb1OO分别存储每次根结点的左右子树。构建二叉树的左子树和右子树

7、时，递归调用构造二叉树函数，容易出错。后面前序，中序，后序遍历二叉树函数写起来很 简单，但要理解其是怎么递归调用遍历函数的，书上也给了一定的讲解。二叉树的打印函数是将二叉树逆时针旋转90度后得到的。4用户手册运行程序后，上面会提示你输入二叉树的前序序列a，输完后回车后上面会提示你输入二叉树的中序序列b，然后回车后，便可以看到相应的输出结果，即前序遍历，中序遍历，后序遍历的结果，和凹入法打印出二叉树。5.测试结果H:flann h散擇2D e bu 甘2. exe卩青输入前序序列a：ABDEGCFHIJ请输入中序序列“DBGEAHFIJC前序遍历：砸DEGCFH1J中序遍历二DBGEAHFIJC

8、后序遍历：DGEBHJIFCrt用凹入法输出该二叉树:Press any kty to cont inue6.源代码 .BiTree.htypedef struct NodeDataType data;struct Node *leftChild; 左指数指针 struct Node *rightChild; 右指数指针BiTreeNode;结点的结构体定义void Ini tiate(BiTreeNode *root) 初始化创建二叉树的头结点 if(*root)=(BiTreeNode *)malloc(sizeof (BiTreeNode)=NULL) return ;(*root)-l

9、eftChild=NULL; (*root)-rightChild=NULL;BiTreeNode *TreeCreat(char *a,char b,int c)/ 创建二叉树函数BiTreeNode *r;char pa100,pb100;int i,j,q, n;In itiate(&r);n=strle n( b);if(n=0)return NULL;elser-data=(*a);for(i=0;i n ;i+)if(bi=(*a)break;pai=bi;pai=0;q=i;for(j=0;jleftChild=TreeCreat(a+1,pa,i); 插入左子树 r-right

10、Child=TreeCreat(a+n+1,pb,c-i-1);插入右子树return r;void PreOrder(BiTreeNode *t) 前序遍历if(t!=NULL)prin tf(%c,t-data);PreOrder(t-leftChild);PreOrder(t-rightChild); void InOrder(BiTreeNode *t) 中序遍历if(t!=NULL)In Order(t-leftChild); prin tf(%c,t-data);In Order(t-rightChild);void PostOrder(BiTreeNode *t) 后序遍历 if

11、(t!=NULL)PostOrder(t-leftChild);PostOrder(t-rightChild); prin tf(%c,t-data); void Prin tBiTree(BiTreeNode *t,i nt n)/逆时针寻转打印二叉树，n为缩进层数，初始值为0int i;if(t=NULL)return; 递归出口Prin tBiTree(t-rightChild, n+1);遍历打印右子树II访问根结点for(i=0;i=0)prin tf(-);prin tf(%cn,t-data);PrintBiTree(t-leftChild,n+1); 遍历打印左子树 void

12、Destroy(BiTreeNode *p) 删除二叉树 if(*p)!=NULL&(*p)-leftChild!=NULL) Destroy(&( *p)-leftChild);if(*p)!=NULL&( *p)-rightChild!=NULL) Destroy(&(*p)-rightChild);free(*p); main,cpp#in clude#in clude#in clude#defi ne DataType char#i ncludeBiTree.hvoid mai n()BiTreeNode *root;char a100,b100;printf(请输入前序序列a: n);scan f(%s,a);prin tf(n);printf(请输入中序序列b: n);scan f(%s,b);prin tf(nn); root=TreeCreat(a,b,strle n(a); pri