《实习二-【唯一的确定一颗二叉树】》由会员分享，可在线阅读，更多相关《实习二-【唯一的确定一颗二叉树】（12页珍藏版）》请在装配图网上搜索。
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, z
4、3, , zm 为右子树的中序序列。右子树的结点数为m - 1, 根据假设, 这两个序列唯一拟定了一棵右子树。因此,唯一拟定的一棵二叉树是由z 1 为根, 该棵右子树为右子树(唯一拟定的这棵二叉树无左子树) 来构成。若j= m , 即zm 为根, 此时二叉树的右子树为空, q1, q2, , qm - 1 为左子树的前序序列, z 1, z 2, ,zm - 1 为左子树的中序序列。 左子树的结点数为m - 1, 根据假设, 这两个序列唯一地拟定了一棵左子树。因此, 唯一拟定的一棵二叉树是由zm 为根, 该棵左子树为左子树(唯一拟定的这棵二叉树无右子树) 来构成。若2 jdata=(*a);f
5、or(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 PrintBiTree(BiTreeNode *t,int n)/ 逆时针寻转打印二叉树，n为缩进层数，初始值为0 int i;if(t=NULL)return;/递归出口PrintBiTree(t-rightChild,n+1);/ 遍历打印右子树/访问根结点for(i=0;i=0
6、)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)-rightChild);free(*p);3.调试分析唯一的拟定一颗二叉树在调试时，问题重要出目前创立二叉树函数上，其中需要在定义两个数组 pa100,pb100分别存储每次根结点的左
7、右子树。构建二叉树的左子树和右子树时，递归调用构造二叉树函数，容易出错。背面前序，中序，后序遍历二叉树函数写起来很简朴，但要理解其是怎么递归调用遍历函数的，书上也给了一定的解说。二叉树的打印函数是将二叉树逆时针旋转90度后得到的。4.顾客手册运营程序后，上面会提示你输入二叉树的前序序列a，输完后回车后上面会提示你输入二叉树的中序序列b，然后回车后，便可以看到相应的输出成果，即前序遍历，中序遍历，后序遍历的成果，和凹入法打印出二叉树。5.测试成果 6.源代码.BiTree.h.typedef struct NodeDataType data;struct Node *leftChild;/左指数
8、指针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)/创立二叉树函数BiTreeNode *r; char pa100,pb100;int i,j,q
9、,n;Initiate(&r);n=strlen(b);if(n=0)return NULL;elser-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-leftChild);PreOr
10、der(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)/ 逆时针寻转打印二叉树，n为缩进层数，初始值为0 int
11、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!=NULL)Destroy(&(*p)-rightChild);
12、free(*p);main.cpp#include#include#include#define DataType char#includeBiTree.hvoid 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);
实习二-【唯一的确定一颗二叉树】
