《2022年唯一的确定一棵二叉文件 .pdf》由会员分享，可在线阅读，更多相关《2022年唯一的确定一棵二叉文件 .pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构上机习报告姓名：学号：班级：【实习二】唯一的确定一棵二叉树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - - - 1 目录1.需求分析 .22.设计. 2（1）设计思想 . 2（2）概要设计 . 3（3）详细设计 . 33.调试分析 . 74.用户手册 . 75.测试结果 . 86.源程序清单. 8名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -
2、 - - - - - - 第 2 页，共 12 页 - - - - - - - - - 2 1. 需求分析【问题描述 】如果给出了遍历二叉树的前序序列和中序序列，则可以构造出唯一的一棵二叉树。试编写实现上述功能的程序。【基本要求】已知一棵二叉树的前序和中序序列，试设计完成下列任务的一个算法：（1）构造一棵二叉树；（2） 证明构造正确 （即分别以前序和中序遍历该树，将得到的结果与给出的序列进行比较）。（3）对该二叉树进行后序遍历，输出后序遍历序列。（4）用凹入法输出该二叉树。【测试数据示例】前序序列为ABDEGCFHIJ ，中序序列为DBGEAHFIJC 2. 设计【设计思想 】(1) 一棵二叉
3、树，我们知道了其前序遍历和中序遍历，则可以唯一确定。(2) 用数学归纳法证明由这两个序列能够唯一地确定一棵二叉树B t. 假设一棵二叉树中结点的个数为n, 即该棵二叉树的前序遍历序列为q1, q2, q3, ?, qn , 中序遍历序列为z 1, z 2, z 3, ?, z n , 用数学归纳法证明由这两个序列能够唯一地确定一棵二叉树B t. 1、当 n= 1 时, 即前序遍历序列和中序遍历序列均只有一个元素, 且相同 , 即为树的根, 由此唯一地确定了一棵二叉树2、现在假设n主要算法框架结构体定义计算结点个数构造二叉树 /构造函数BiTreeCreatBiTree (char * pre,
4、char * in,int n) BiTree tree; char * root; int k; if (n data = * pre; / 查找中序序列中根节点位置for (root = in;rootlchild = CreatBiTree (pre + 1,in,k); /* 构造左子树 */ tree-rchild = CreatBiTree (pre + 1 + k,root + 1,n - k - 1); /* 构造右子树*/ return tree; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理
5、- - - - - - - 第 5 页，共 12 页 - - - - - - - - - 5 前序遍历二叉树data); pre_order(t-lchild); pre_order(t-rchild); 中序遍历二叉树lchild); printf(%c ,t-data); in_order(t-rchild); 后序遍历二叉树lchild); post_order(t-rchild); printf(%c ,t-data); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页
6、，共 12 页 - - - - - - - - - 6 凹入法打印二叉树rchild,n+1); / 遍历打印右子树/ 访问根结点for(i=0;i0) printf(-); printf(%cn,t-data); else printf(-%cn,t-data); PrintBiTree(t-lchild,n+1); / 遍历打印左子树 主函数 完整程序 #include #include #include #define size 100 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -
7、- 第 9 页，共 12 页 - - - - - - - - - 9 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 data = * pre;
8、 / 查找中序序列中根节点位置for (root = in;rootlchild = 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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 12 页 - - - - - - - -
9、 - 10 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); /* 凹入法打印二叉
10、树*/ voidPrintBiTree(BiTreet,int n) / 逆时针旋转90 打印二叉树root,n 为缩进层数，初始值为0 inti; if(t=NULL) return; / 递归出口PrintBiTree(t-rchild,n+1); / 遍历打印右子树/ 访问根结点for(i=0;i0) printf(-); printf(%cn,t-data); else printf(-%cn,t-data); PrintBiTree(t-lchild,n+1); / 遍历打印左子树 int main() BiTree tree; char presize; char insize;
11、char pre1size; char in1size; inti,n; i=0; printf( 请输入前序遍历结果：n); scanf(%s,pre); printf( 请输入中序遍历结果：n); scanf(%s,in); n=countTree (pre); /* 建树*/ tree = CreatBiTree (pre,in,n); printf(n前序遍历结果：n); pre_order(tree); printf(n中序遍历结果：n); in_order(tree); printf(n后序遍历结果：n); post_order(tree); PrintBiTree(tree,0); printf(n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 12 页 - - - - - - - - -