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

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

2、表示左子树，若左边无元素，则说明左子树为空；右边（设r个元素）是右子树，若为空，则右子树为空。根据前序遍历中“根左子树右子树”的顺序，则由从第二元素开始的l个结点序列和中序序列根左边的l个结点构成左子树，由前序序列最后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 为左子树的中序序列, z j+ 1, z j+ 2, , zm 为右子树的中序序列。若j= 1, 即z 1 为根, 此时二叉树的左子树为空, q2, q3, , qm 为左子树的前序序列, z 2

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

5、; m - 1, 则子序列q1, q2, ,qj - 1 和z 1, z 2, , z j - 1 根据假设可知, 它们唯一地确定了一棵左子树。 同理, 子序列qj+ 1, qj+ 2, qm 和z j+ 1, z j+ 2 , , zm 唯一地确定了一棵右子树。 前者确定的左子树与后者确定的右子树及z j可唯一地确定一棵二叉树。 由此, 从理论上证明了由一棵二叉树的前序遍历序列和中序遍历序列能够唯一确定一棵二叉树。 同理, 即由一棵二叉树的后序遍历序列和中序遍历序列, 也能够唯一地确定一棵二叉树。具体思想例如： 前序序列为ABDEGCFHIJ， 中序遍历为DBGEAHFIJC由前序遍历可确定

6、根为A，中序遍历可得A的左右子树分别包含结点有DBGE、HFIJC构造A的左子树：A的左子树分别包含结点有DBGE，由前序遍历可知B为根结点，B的左右子树分别包含结点有D、GE。则B的左子树为就为D，然后构造B右子树，由前序遍历可知E为根结点，B的右子树的中序遍历知G为E的左孩子。同理可以构造出A的右孩子结构体定义：typedef struct NodeDataType data;struct Node *leftChild;/左指数指针struct Node *rightChild;/右指数指针BiTreeNode;/结点的结构体定义创建二叉树函数：BiTreeNode *TreeCreat

7、(char *a,char b,int c)/创建二叉树函数BiTreeNode *r; char pa100,pb100;int i,j,q,n;Initiate(&r);n=strlen(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;j<c-i;j+)q+;pbj=bq;pbj='0'n=strlen(pa);r->leftChild=TreeCreat(a+1,pa,i);/插入

8、左子树r->rightChild=TreeCreat(a+n+1,pb,c-i-1);/ 插入右子树return r;打印二叉树：void PrintBiTree(BiTreeNode *t,int n)/ 逆时针寻转打印二叉树，n为缩进层数，初始值为0 int i;if(t=NULL)return;/递归出口PrintBiTree(t->rightChild,n+1);/ 遍历打印右子树/访问根结点for(i=0;i<n;i+)printf(" ");if(n>=0)printf("-");printf("%cn&qu

9、ot;,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.调试分析唯一的确定一颗二叉树在调试时，问题主要出现在创建二叉树函数上，其中

10、需要在定义两个数组 pa100,pb100分别存储每次根结点的左右子树。构建二叉树的左子树和右子树时，递归调用构造二叉树函数，容易出错。后面前序，中序，后序遍历二叉树函数写起来很简单，但要理解其是怎么递归调用遍历函数的，书上也给了一定的讲解。二叉树的打印函数是将二叉树逆时针旋转90度后得到的。4.用户手册运行程序后，上面会提示你输入二叉树的前序序列a，输完后回车后上面会提示你输入二叉树的中序序列b，然后回车后，便可以看到相应的输出结果，即前序遍历，中序遍历，后序遍历的结果，和凹入法打印出二叉树。5.测试结果 6.源代码.BiTree.h.typedef struct NodeDataType

11、data;struct Node *leftChild;/左指数指针struct Node *rightChild;/右指数指针BiTreeNode;/结点的结构体定义void Initiate(BiTreeNode *root)/初始化创建二叉树的头结点if(*root)=(BiTreeNode *)malloc(sizeof (BiTreeNode)=NULL) return ;(*root)->leftChild=NULL;(*root)->rightChild=NULL;BiTreeNode *TreeCreat(char *a,char b,int c)/创建二叉树函数B

12、iTreeNode *r; char pa100,pb100;int i,j,q,n;Initiate(&r);n=strlen(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;j<c-i;j+)q+;pbj=bq;pbj='0'n=strlen(pa);r->leftChild=TreeCreat(a+1,pa,i);/插入左子树r->rightChild=TreeCreat(a

13、+n+1,pb,c-i-1);/ 插入右子树return r;void PreOrder(BiTreeNode *t)/前序遍历if(t!=NULL)printf("%c",t->data);PreOrder(t->leftChild);PreOrder(t->rightChild);void InOrder(BiTreeNode *t)/中序遍历if(t!=NULL)InOrder(t->leftChild);printf("%c",t->data);InOrder(t->rightChild);void PostO

14、rder(BiTreeNode *t)/后序遍历if(t!=NULL)PostOrder(t->leftChild); PostOrder(t->rightChild);printf("%c",t->data);void PrintBiTree(BiTreeNode *t,int n)/ 逆时针寻转打印二叉树，n为缩进层数，初始值为0 int i;if(t=NULL)return;/递归出口PrintBiTree(t->rightChild,n+1);/ 遍历打印右子树/访问根结点for(i=0;i<n;i+)printf(" &qu

15、ot;);if(n>=0)printf("-");printf("%cn",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)->rig

16、htChild);free(*p);main.cpp#include<stdio.h>#include<malloc.h>#include<string.h>#define DataType char#include"BiTree.h"void main()BiTreeNode *root;char a100,b100;printf("请输入前序序列a: n"); scanf("%s",a);printf("n"); printf("请输入中序序列b: n"); scanf("%s",b);printf("nn");root=TreeCreat(a,b,strlen(a);printf("前序遍历:n");PreOrder