数据结构上机实习(共10页)

1、【问题描述】 如果给出了遍历二叉树的前序序列和中序序列，则可以构造出唯一的一棵二叉树。试编写实现上述功能的程序。 【基本要求】已知一棵二叉树的前序和中序序列，试设计完成下列任务的一个算法：（1）构造一棵二叉树；（2） 证明构造正确（即分别以前序和中序遍历该树，将得到的结果与给出的序列进行比较）。（3）对该二叉树进行后序遍历，输出后序遍历序列。（4）用凹入法输出该二叉树。【测试数据示例】 前序序列为ABDEGCFHIJ，中序序列为DBGEAHFIJC1. 设计【设计思想】(1)一棵二叉树，我们知道了其前序遍历和中序遍历，则可以唯一确定。(2) 用数学归纳法证明由这两个序列能够唯一地确定一棵二叉树

2、B t.假设一棵二叉树中结点的个数为n, 即该棵二叉树的前序遍历序列为q1, q2, q3, , qn , 中序遍历序列为z 1, z 2, z 3, , z n , 用数学归纳法证明由这两个序列能够唯一地确定一棵二叉树B t.1、当n= 1 时, 即前序遍历序列和中序遍历序列均只有一个元素, 且相同, 即为树的根, 由此唯一地确定了一棵二叉树2、现在假设n< m - 1 时命题成立, 则需要证明当n= m 时亦成立3、当n= m 时, 前序序列为q1, q2, q3, , qm , 中序序列为z 1, z 2, z 3, , zm. 因为前序序列由前序遍历二叉树所得, 则q1必为根结点

3、这个元素; 又中序序列由中序遍历二叉树所得, 则在中序序列中必能找到和q1相同的元素, 设为z j , 由此z 1, z 2, , z j - 1 为左子树的中序序列, z j+ 1, z j+ 2, , zm 为右子树的中序序列。再通过递归调用，找出非根节点的左右子树。由此, 从理论上证明了由一棵二叉树的前序遍历序列和中序遍历序列能够唯一确定一棵二叉树， 同理, 即由一棵二叉树的后序遍历序列和中序遍历序列, 也能够唯一地确定一棵二叉树， 但是, 由一棵二叉树的前序遍历序列和后序遍历序列, 却不能唯一地确定一棵二叉树。(3)对构造的二叉树用凹入法输出。(4) 对该二叉树进行后序遍历，输出后序遍

4、历序列。【概要设计】(1) 用单链表存储二叉树的结点结构体定义lchilddatarchild(2) 构造二叉树(3) 对所构造的二叉树进行前序和中序遍历，并输出，并由此证明构造正确。(4) 凹入法打印二叉树。(5) 测试函数结构体定义/二叉树结构体定义typedef struct BiTNode char data;/数据域 struct BiTNode * lchild,* rchild; /指针域 BiTNode, * BiTree;计算结点个数int countTree (char * tree)int i;for (i = 0; tree i != '0'i +);r

5、eturn i;构造二叉树/构造函数BiTree CreatBiTree (char * pre,char * in,int n)BiTree tree;char * root;int k; if (n <= 0) return NULL;tree = (BiTree) malloc (sizeof (BiTNode);tree->data = * pre;/查找中序序列中根节点位置 for (root = in;root < in + n;root +) if (* root = * pre)break;k = root - in;tree->lchild = Cre

6、atBiTree (pre + 1,in,k); /*构造左子树*/tree->rchild = CreatBiTree (pre + 1 + k,root + 1,n - k - 1); /*构造右子树*/ return tree;前序遍历二叉树/ 前序遍历 void pre_order(BiTree t) if (t != NULL) printf("%c ",t->data); pre_order(t->lchild); pre_order(t->rchild);中序遍历二叉树/ 中序遍历 void in_order(BiTree t) if

7、(t != NULL) in_order(t->lchild); printf("%c ",t->data); in_order(t->rchild); 后序遍历二叉树/ 后序遍历 void post_order(BiTree t) if (t != NULL) post_order(t->lchild); post_order(t->rchild); printf("%c ",t->data); 凹入法打印二叉树/*凹入法打印二叉树*/void PrintBiTree(BiTree t,int n)/逆时针旋转90打

8、印二叉树root,n为缩进层数，初始值为0int i;if(t=NULL) return; /递归出口PrintBiTree(t->rchild,n+1); /遍历打印右子树 /访问根结点for(i=0;i<n;i+) printf(" ");if(n>0)printf("-");printf("%cn",t->data);elseprintf("-%cn",t->data);PrintBiTree(t->lchild,n+1); /遍历打印左子树主函数int main() Bi

9、Tree tree; char presize; char insize;char pre1size; char in1size;int i,n;i=0; printf("请输入前序遍历结果：n"); scanf("%s",pre); printf("请输入中序遍历结果：n"); scanf("%s",in); n=countTree (pre); /* 建树 */ tree = CreatBiTree (pre,in,n); PrintBiTree(tree,0); printf("n前序遍历结果：n&

10、quot;); pre_order(tree); printf("n中序遍历结果：n"); in_order(tree); printf("n后序遍历结果：n"); post_order(tree);printf("n"); 2. 调试分析(1)、最初对于二叉树的构造一直没有头绪，多次出错，经过查阅资料、课本最终成功构造出二叉树。(2)、ERROR LNK2001:unresolved external symbol “symbol”（不确定的外部“符号”）。如果连接程序不能在所有的库和目标文件内找到所引用的函数、变量或标签，将产生此

11、错误消息。一般来说，发生错误的原因有两个：一是所引用的函数、变量不存在、拼写不正确或者使用错误；其次可能使用了不同版本的连接库。(3)、这次编程使我更多地理解掌握了线性链表的逻辑机构和物理特性。对学过的知识有了很好的巩固。困难还是很多的，但通过认真的调试修改，最终克服种种困难，完成程序。 最后，通过这次编程，不仅仅考察了我对知识的掌握，更重要的是锻炼了我的思维能力和耐心。4. 运行程序后的初始画面：当输入的系数和指数均为0时输出多项式。多项式a和b均输出后，再输入求和类型，相加运算输入1；相减运算输入03. 测试结果（1）4. 原程序清单#include<stdio.h> #inc

12、lude<stdlib.h> #include<string.h> #define size 100 typedef struct BiTNode char data;/数据域 struct BiTNode * lchild,* rchild; /指针域 BiTNode, * BiTree;int countTree (char * tree)int i;for (i = 0; tree i != '0'i +);return i;BiTree CreatBiTree (char * pre,char * in,int n)BiTree tree;cha

13、r * root;int k; if (n <= 0) return NULL;tree = (BiTree) malloc (sizeof (BiTNode);tree->data = * pre;/查找中序序列中根节点位置 for (root = in;root < in + n;root +) if (* root = * pre)break;k = root - in;tree->lchild = CreatBiTree (pre + 1,in,k);tree->rchild = CreatBiTree (pre + 1 + k,root + 1,n -

14、k - 1); return tree;/* 前序遍历 */void pre_order(BiTree t) if (t != NULL) printf("%c ",t->data); pre_order(t->lchild); pre_order(t->rchild);/* 中序遍历 */void in_order(BiTree t) if (t != NULL) in_order(t->lchild); printf("%c ",t->data); in_order(t->rchild); /* 后序遍历 */vo

15、id post_order(BiTree t) if (t != NULL) post_order(t->lchild); post_order(t->rchild); printf("%c ",t->data); /*凹入法打印二叉树*/void PrintBiTree(BiTree t,int n)/逆时针旋转90打印二叉树root,n为缩进层数，初始值为0int i;if(t=NULL) return; /递归出口PrintBiTree(t->rchild,n+1); /遍历打印右子树 /访问根结点for(i=0;i<n;i+) prin

16、tf(" ");if(n>0)printf("-");printf("%cn",t->data);elseprintf("-%cn",t->data);PrintBiTree(t->lchild,n+1); /遍历打印左子树 int main() BiTree tree; char presize; char insize;char pre1size; char in1size;int i,n;i=0; printf("请输入前序遍历结果：n"); scanf("%s",pre); printf("请输入中序遍历结果：n"); scanf("%s