2022年实习二整理 .pdf
实习二1.需求分析：【问题描述】 ：如果给出了遍历二叉树的前序序列和中序序列，则可以构造出唯一的二叉树。试编写实现上述功能的程序。【基本要求】：已知一颗二叉树的前序和中序序列，试设计完成下列任务的一个算法。（1）构造一颗二叉树。（2）证明构造正确（即分别以前序和中序遍历该树，将得到的结果与给出的序列进行比较）。（3）对该二叉树进行后序遍历，输出后续遍历序列。（4）用凹入法输出该二叉树。【开发环境】：系统： windows7 编程软件： VC+6.0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 10 页 - - - - - - - - - 2.设计：给定二叉树结点的前序序列和中序序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设l个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设r个元素）是右子树，若为空，则右子树为空。根据前序遍历中“根左子树右子树”的顺序，则由从第二元素开始的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 时, 前序序列为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, 根据假设 , 这两个序列唯一确定了一棵右子树。因此,唯一确定的一棵二叉树是由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=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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 10 页 - - - - - - - - - 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 分别存储每次根结点的左右子树。构建二叉树的左子树和右子树时，递归调用构造二叉树函数，容易出错。后面前序，中序，后序遍历二叉树函数写起来很简单， 但要理解其是怎么递归调用遍历函数的，书上也给了一定的讲解。二叉树的打印函数是将二叉树逆时针旋转90 度后得到的。4.用户手册运行程序后，上面会提示你输入二叉树的前序序列a，输完后回车后上面会提示你输入二叉树的中序序列b，然后回车后，便可以看到相应的输出结果，即前序遍历，中序遍历，后序遍历的结果，和凹入法打印出二叉树。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 10 页 - - - - - - - - - 5.测试结果6.源代码.BiTree.h.typedef struct Node DataType data; struct Node *leftChild;/ 左指数指针struct Node *rightChild;/ 右指数指针名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 10 页 - - - - - - - - - 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; Initiate(&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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 10 页 - - - - - - - - - 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 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 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);/遍历打印左子树 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 10 页 - - - - - - - - - void 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 #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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 10 页 - - - - - - - - - printf(n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 10 页 - - - - - - - - -
