唯一的确定一棵二叉树.docx

唯一的确定一棵二叉树数据结构上机习报告姓名：学号：班级：【实习二】唯一的确定一棵二叉树目录1.需求分析 (2)2.设计 (2)（1）设计思想 (2)（2）概要设计 (3)（3）详细设计 (3)3.调试分析 (7)4.用户手册 (7)5.测试结果 (8)6.源程序清单 (8)1.需求分析【问题描述】如果给出了遍历二叉树的前序序列和中序序列，则可以构造出唯一的一棵二叉树试编写实现上述功能的程序基本要求】已知一棵二叉树的前序和中序序列，试设计完成下列任务的一个算法：（1）构造一棵二叉树；（2）证明构造正确（即分别以前序和中序遍历该树，将得到的结果与给出的序列进行比较）3）对该二叉树进行后序遍历，输出后序遍历序列4）用凹入法输出该二叉树测试数据示例】前序序列为ABDEGCFHIJ，中序序列为DBGEAHFIJC2.设计【设计思想】(1)一棵二叉树，我们知道了其前序遍历和中序遍历，则可以唯一确定2)用数学归纳法证明由这两个序列能够唯一地确定一棵二叉树B t.假设一棵二叉树中结点的个数为n, 即该棵二叉树的前序遍历序列为q1, q2, q3, ?, qn , 中序遍历序列为z 1, z 2, z 3, ?, z n , 用数学归纳法证明由这两个序列能够唯一地确定一棵二叉树B t.1、当n= 1 时, 即前序遍历序列和中序遍历序列均只有一个元素, 且相同, 即为树的根, 由此唯一地确定了一棵二叉树2、现在假设n3、当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 } 为右子树的中序序列。

再通过递归调用，找出非根节点的左右子树由此, 从理论上证明了由一棵二叉树的前序遍历序列和中序遍历序列能够唯一确定一棵二叉树，同理, 即由一棵二叉树的后序遍历序列和中序遍历序列, 也能够唯一地确定一棵二叉树，但是, 由一棵二叉树的前序遍历序列和后序遍历序列, 却不能唯一地确定一棵二叉树3)对构造的二叉树用凹入法输出4)对该二叉树进行后序遍历，输出后序遍历序列概要设计】(1)用单链表存储二叉树的结点结构体定义(2)构造二叉树(3)对所构造的二叉树进行前序和中序遍历，并输出，并由此证明构造正确4)凹入法打印二叉树5)测试函数【详细设计】>>>>>>>>>>主要算法框架>>>>>>>>>>结构体定义/////二叉树结构体定义typedefstructBiTNode {char data; //数据域structBiTNode * lchild,* rchild; //指针域}BiTNode, * BiTree;>>>>>>>>>>计算结点个数intcountTree (char * tree){inti;for (i = 0; tree [i] != '\0';i ++);returni;}>>>>>>>>>>构造二叉树///////构造函数BiTreeCreatBiTree (char * pre,char * in,int n){BiTree tree;char * root;int k;if (n return NULL;tree = ((BiTree) malloc (sizeof (BiTNode)));tree->data = * pre;//查找中序序列中根节点位置for (root = in;rootif (* root == * pre)break;k = root - in;tree->lchild = CreatBiTree (pre + 1,in,k); /*构造左子树*/tree->rchild = CreatBiTree (pre + 1 + k,root + 1,n - k - 1); /*构造右子树*/return tree;}>>>>>>>>>>前序遍历二叉树voidpre_order(BiTree t){if (t != NULL){printf("%c ",t->data);pre_order(t->lchild);pre_order(t->rchild);}}>>>>>>>>>>中序遍历二叉树voidin_order(BiTree t){if (t != NULL){in_order(t->lchild);printf("%c ",t->data);in_order(t->rchild);}}>>>>>>>>>>后序遍历二叉树voidpost_order(BiTree t){if (t != NULL){post_order(t->lchild);post_order(t->rchild);printf("%c ",t->data);}}>>>>>>>>>>凹入法打印二叉树voidPrintBiTree(BiTreet,int n)//逆时针旋转90打印二叉树root,n为缩进层数，初始值为0 {inti;if(t==NULL) return; //递归出口PrintBiTree(t->rchild,n+1); //遍历打印右子树//访问根结点for(i=0;iif(n>0){printf("---");printf("%c\n",t->data);}elseprintf("---%c\n",t->data);PrintBiTree(t->lchild,n+1); //遍历打印左子树}>>>>>>>>>>主函数int main(){ BiTree tree;char pre[size];char in[size];char pre1[size];char in1[size];inti,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");pre_order(tree);printf("\n中序遍历结果：\n");in_order(tree);printf("\n后序遍历结果：\n");post_order(tree);printf("\n");}3.调试分析(1)、最初对于二叉树的构造一直没有头绪，多次出错，经过查阅资料、课本最终成功构造出二叉树。

2)、ERROR LNK2001:unresolved external symbol “symbol”（不确定的外部“符号”）如果连接程序不能在所有的库和目标文件内找到所引用的函数、变量或标签，将产生此错误消息一般来说，发生错误的原因有两个：一是所引用的函数、变量不存在、拼写不正确或者使用错误；其次可能使用了不同版本的连接库3)、这次编程使我更多地理解掌握了线性链表的逻辑机构和物理特性对学过的知识有了很好的巩固困难还是很多的，但通过认真的调试修改，最终克服种种困难，完成程序最后，通过这次编程，不仅仅考察了我对知识的掌握，更重要的是锻炼了我的思维能力和耐心4.用户手册运行程序后的初始画面：当输入的系数和指数均为0时输出多项式多项式a和b均输出后，再输入求和类型，相加运算输入1；相减运算输入04.测试结果（1）5.原程序清单>>>>>>>>>>完整程序#include#include#include#define size 100typedefstructBiTNode{char data; //数据域structBiTNode * lchild,* rchild; //指针域}BiTNode, * BiTree;intcountTree (char * tree){inti;for (i = 0; tree [i] != '\0';i ++);returni;}BiTreeCreatBiTree (char * pre,char * in,int n){BiTree tree;char * root;int k;if (n return NULL;tree = ((BiTree) malloc (sizeof (BiTNode)));tree->data = * pre;//查找中序序列中根节点位置for (root = in;rootif (* root == * pre)break;k = root - in;tree->lchild = CreatBiTree (pre + 1,in,k);tree->rchild = CreatBiTree (pre + 1 + k,root + 1,n - k - 1);return tree;}/* 前序遍历*/voidpre_order(BiTree t){if (t != NULL){printf("%c ",t->data);pre_order(t->lchild);pre_order(t->rchild);}}/* 中序遍历*/voidin_order(BiTree t){if (t != NULL){in_order(t->lchild);printf("%c ",t->data);in_order(t->rchild);}}/* 后序遍历*/voidpost_order(BiTree t){if (t != NULL){post_order(t->lchild);post_order(t->rchild);printf("%c ",t->data);}}/*凹入法打印二叉树*/voidPrintBiTree(BiTreet,int n)//逆时针旋转90打印二叉树root,n为缩进层数，初始值为0 {inti;if(t==NULL) return; //递归出口PrintBiTree(t->rchild,n+1); //遍历打印右子树//访问根结点for(i=0;i0){printf("---");printf("%c\n",t->data);}elseprintf("---%c\n",t->data);PrintBiTree(t->lchild,n+1); //遍历打印左子树}int main(){ BiTree tree;char pre[size];char in[size];char pre1[size];char in1[size];inti,n;i=0;printf("请输入前序遍历结果：\n");scanf("%s",pre);printf("请输入中序遍历结果：\n");。