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

《实习二 唯一的确定一颗二叉树.docx》由会员分享，可在线阅读，更多相关《实习二 唯一的确定一颗二叉树.docx（7页珍藏版）》请在三一办公上搜索。

1、实习二 唯一的确定一颗二叉树实习二 1.需求分析： ：如果给出了遍历二叉树的前序序列和中序序列，则可以构造出唯一的二叉树。试编写实现上述功能的程序。 ：已知一颗二叉树的前序和中序序列，试设计完成下列任务的一个算法。 构造一颗二叉树。 证明构造正确。 对该二叉树进行后序遍历，输出后续遍历序列。 用凹入法输出该二叉树。 ： 系统：windows7 编程软件：VC+6.0 2.设计： 给定二叉树结点的前序序列和中序序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边表示左子树，若左边无元素，则说明左子树为空；右边是右子树，若为空，则右子树为空。根据前序

2、遍历中“根左子树右子树”的顺序，则由从第二元素开始的l个结点序列和中序序列根左边的l个结点构成左子树，由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树。 假设一棵二叉树中结点的个数为n, 即该棵二叉树的前序遍历序列为q1, q2, q3, , qn , 中序遍历序列为z 1, z 2, z 3, , z n , 用数学归纳法证明由这两个序列能够唯一地确定一棵二叉树B t.当n= 1 时, 即前序遍历序列和中序遍历序列均只有一个元素, 且相同, 即为树的根, 由此唯一地确定了一棵二叉树。现在假设n m - 1 时命题成立, 则需要证明当n= m 时亦成立。当n= m 时, 前序

3、序列为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, z 3, , zm 为右子树的中序序列。右子树的结点数为m - 1, 根据假设, 这两个序列唯一确定了一

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

5、i; for(j=0;jleftChild=TreeCreat(a+1,pa,i);/插入左子树 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=0) printf(-); printf(%cn,t-data); Pr

6、intBiTree(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.调试分析 唯一的确定一颗二叉树在调试时，问题主要出现在创建二叉树函数上，其中需要在定义两个数组 pa100,pb100分别存储每次根结点的左右子树。构建二叉树的左子树和右子树时，递归调用构

7、造二叉树函数，容易出错。后面前序，中序，后序遍历二叉树函数写起来很简单，但要理解其是怎么递归调用遍历函数的，书上也给了一定的讲解。二叉树的打印函数是将二叉树逆时针旋转90度后得到的。 4.用户手册 运行程序后，上面会提示你输入二叉树的前序序列a，输完后回车后上面会提示你输入二叉树的中序序列b，然后回车后，便可以看到相应的输出结果，即前序遍历，中序遍历，后序遍历的结果，和凹入法打印出二叉树。 5.测试结果 6.源代码 .BiTree.h. typedef struct Node DataType data; struct Node *leftChild;/左指数指针 struct Node *r

8、ightChild;/右指数指针 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)/创建二叉树函数 BiTreeNode *r; char pa100,pb100; int i,j,q,n; Init

9、iate(&r); n=strlen(b); if(n=0) return NULL; else r-data=(*a); for(i=0;in;i+) if(bi=(*a) 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 PreOrder(BiTreeNode *t)/前序遍历 if(t!=NULL) printf(%c,t-data); PreOrder(t-leftCh

10、ild); PreOrder(t-rightChild); void InOrder(BiTreeNode *t)/中序遍历 if(t!=NULL) InOrder(t-leftChild); printf(%c,t-data); InOrder(t-rightChild); void PostOrder(BiTreeNode *t)/后序遍历 if(t!=NULL) PostOrder(t-leftChild); PostOrder(t-rightChild); printf(%c,t-data); void PrintBiTree(BiTreeNode *t,int n) / 逆时针寻转打

11、印二叉树，n为缩进层数，初始值为0 int i; if(t=NULL)return;/递归出口 PrintBiTree(t-rightChild,n+1);/ 遍历打印右子树 /访问根结点 for(i=0;i=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

12、!=NULL) Destroy(&(*p)-rightChild); free(*p); main.cpp #include #include #include #define DataType char #includeBiTree.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(root); printf(nn); printf(中序遍历:n); InOrder(root); printf(nn); printf(后序遍历:n); PostOrder(root); printf(nnn); printf(用凹入法输出该二叉树:nn); PrintBiTree(root,0); Destroy(&root); printf(n);