实验六-二叉树实验报告

1、实验四二叉树的操作题目：对于给定的一二义树，实现各种约定的遍历。一、实验目的：1掌握二义树的定义和存储表示，学会建立一棵特定二义树的方法；2掌握二义树的遍历算法先序、中序、后序遍历算法的思想，并学会遍历算法的递归实现和非递归实现。二、实验内容：构造二义树，再实现二义树的先序、中序、后序遍历，最后统计二义树的深度。三、实验步骤：1. （一）需求分析二义树的建立首先要建立一个二义链表的结构体，包含根节点和左右子树。因为树的每一个左右子树乂是一颗二义树，所以用递归的方法来建立其左右子树。二义树的遍历是一种把二义树的每一个节点访问并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个

2、过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句来实现。2. 程序的执行命令为：1构造结点类型，然后创建二义树。2根据提小，从键盘输入各个结点。3通过选择一种方式先序、中序或者后序遍历。4输出结果，结束。1. （二）概要设计二义树的二义链表结点存储类型定义typedefstructNode（DataTypedata;structNode*LChild;structNode*RChild;2. BitNode,*BitTree;建立如下列图所示二义树：voidCreatBiTree（BitTree*bt）用扩展先序遍历序列创建二义树，如果是当前树根置为空，否则申请一个

3、新节点。3. 本程序包含四个模块1) 主程序模块:2) 先序遍历模块3) 中序遍历模块后序遍历模块三详细设计/=构造二又树=voidCreatBiTree(BitTree*bt)/用扩展先序遍历序列创建二叉树，如果是当前树根置为空,否则申请一个新节点/(charch;ch=getchar();if(ch='.')*bt=NULL;else(*bt=(BitTree)malloc(sizeof(BitNode);/申请一段关于该节点类型的存储空间(*bt)->data=ch;/生成根结点CreatBiTree(&(*bt)->LChild);/构造左子树Cre

4、atBiTree(&(*bt)->RChild);/构造右子树2.编程实现以上二叉树的前序、中序和后序遍历操作，输出遍历序列1先序遍历二叉树的递归算法如下：voidPreOrder(BitTreeroot)(if(root!=NULL)(Visit(root->data);PreOrder(root->LChild);/递归调用核心PreOrder(root->RChild);2中序遍历二叉树的递归算法如下：voidInOrder(BitTreeroot)if(root!=NULL)(InOrder(root->LChild);Visit(root->

5、;data);InOrder(root->RChild);3后序遍历二叉树的递归算法如下:voidPostOrder(BitTreeroot)(if(root!=NULL)(PostOrder(root->LChild);PostOrder(root->RChild);Visit(root->data);4计算二义树的深度算法如下：intPostTreeDepth(BitTreebt)求二叉树的深度(inthl,hr,max;if(bt!=NULL)(hl=PostTreeDepth(bt->LChild);求左子树的深度hr=PostTreeDepth(bt-&

6、gt;RChild);求右子树的深度max=hl>hr?hl:hr;得到左、右子树深度较大者return(max+1);返回树的深度elsereturn(0);如果是空树，则返回01. 四、调试分析及测试结果进入演示程序后的显示主界面：请输入二义树中的元素；先序、中序和后序遍历分别输出结果。以扩展先序遍历序列输入，其中.代表空子树：ABC.DE.G.F先序遍历序列为：ABCDEGF中序遍历序列为：CBEGDFA后序遍历序列为：CGEFDBA此二义树的深度为：5.代表空子树，显示1输入二义树中的元素以扩展先序遍历序列输入，其中截图为：2输出结果，显示界面为:'C:PrcgramFi

7、les(xSSJMicrosoftVisualStudioMyProiectsXeeDebLig?e.eKe*图二4. 调试分析：本程序通过分别调用先序遍历、中序遍历以及后序遍历函数对二义树中的元素进行遍历，整个程序基本满足实验要求，但是在一些细节问题上面还是存在缺陷，比方大小写字母不同也会导致程序无法运行，这就需要我们在处理问题上认真细致，还有就是程序并不是很完善，总之，我会在今后更加努力，是程序更完美。六、实验总结1. 二义树对于进行表达式的前缀，中缀和后缀的表示有明显的优势，既方便，乂容易理解。其先序，中序和后序分别对应这表达式的前缀，中缀和后缀。2. 在建树与进行树的遍历的时候一定要理

8、解其建树与遍历的整个过程。不然就会连为什么这样做都不知道。在遍历树的时候最常用到的就是栈的结构了非递归。3. 本次实验让我更加了解了哈夫曼树的构造和生成方法，以及如何用顺序结构来存储哈夫曼树及构树过程的信息，如何进行编码、译码。也感知到模块程序设计在大程序设计使用中的普遍性，该实验是最好的证明，通过模块程序设计，能使程序可读可写性明显加强。通过本次实验，使我初步掌握了二义树的结构特性以及各种存储的结构的特点和适用范围，掌握了哈夫曼树的定义和思想，初步掌握了用凹入法显示树。不过程序仍有树的显示不够完善的缺点，在今后的学习中，我会不断学习，在学习中注意改变。附录源程序活单：#include<

9、stdio.h>#include<stdlib.h>#include<malloc.h>#include<conio.h>typedefintDataType;typedefstructNode/创建结点类型结构体DataTypedata;structNode*LChild;structNode*RChild;BitNode,*BitTree;voidCreatBiTree(BitTree*bt)用扩展先序遍历序列创建二叉树，如果是当前树根置为空,否则申请一个新节点/charch;ch=getchar();if(ch='.')*bt=N

10、ULL;else*bt=(BitTree)malloc(sizeof(BitNode);(*bt)->data=ch;CreatBiTree(&(*bt)->LChild);CreatBiTree(&(*bt)->RChild);voidvisit(charch)/访问根节点printf("%c",ch);voidPreOrder(BitTreeroot)/先序遍历二叉树的递归算法if(root!=NULL)Visit(root->data);PreOrder(root->LChild);PreOrder(root->RC

11、hild);voidInOrder(BitTreeroot)中序遍历二叉树的递归算法if(root!=NULL)InOrder(root->LChild);Visit(root->data);InOrder(root->RChild);voidPostOrder(BitTreeroot)(if(root!=NULL)(PostOrder(root->LChild);PostOrder(root->RChild);Visit(root->data);intPostTreeDepth(BitTreebt)(inthl,hr,max;if(bt!=NULL)(hl=PostTreeDepth(bt->LChild);hr=PostTreeDepth(bt->RChild);max=hl>hr?hl:hr;return(max+1);elsereturn(0);voidmain()后序遍历求二叉树的递归算法求二叉树的深度求左子树的深度求右子树的深度得到左、右子树深度较大者返回树的深度如果是空树，则返回0(BitTreeT;inth;intlayer;inttreeleaf;layer=0;printf("请输入二叉树中的元素(以扩展先序遍历序列输入,其中.代表空子树):n");CreatBiTree(&T)