实验六二叉树实验报告

实验四二叉树的操作班级：计算机1002班姓名：唐自鸿学号：201003010207完成日期：题目：关于给定的一二叉树，实现各种约定的遍历。一、实验目的：1）掌握二叉树的定义和储藏表示，学会建立一棵特定二叉树的方法；2）掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想，并学会遍历算法的递归实现和非递归实现。二、实验内容：构造二叉树，再实现二叉树的先序、中序、后序遍历，最后统计二叉树的深度。三、实验步骤：(一)需求解析二叉树的建立第一要建立一个二叉链表的构造体，包含根节点和左右子树。因为树的每一个左右子树又是一颗二叉树，所以用递归的方法来建立其左右子树。二叉树的遍历是一种把二叉树的每一个节点接见并输出的过程，遍历时根结点与左右孩子的输出序次构成了不同样的遍历方法，这个过程需要依照不同样的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句来实现。2．程序的执行命令为：1）构造结点种类，尔后创办二叉树。2）依照提示，从键盘输入各个结点。3）经过选择一种方式（先序、中序也许后序）遍历。4）输出结果，结束。(二)大纲设计1.二叉树的二叉链表结点储藏种类定义typedefstructNode{DataTypedata;structNode*LChild;structNode*RChild;}BitNode,*BitTree;2.建立以以下图所示二叉树：voidCreatBiTree(BitTree*bt)用扩展先序遍历序列创办二叉树，若是是当前树根置为空，否则申请一个新节点。3.本程序包含四个模块主程序模块：2)先序遍历模块3)中序遍历模块4)后序遍历模块4.模块调用关系：主程序模块先序遍历模块中序遍历模块后序遍历模块（三）详细设计1.建立二叉树储藏种类//==========构造二叉树=======voidCreatBiTree(BitTree*bt)//用扩展先序遍历序列创办二叉树，若是是当前树根置为空，否则申请一个新节点

//{charch;ch=getchar( );if(ch=='.')*bt=NULL;else{*bt=(BitTree)malloc(sizeof(BitNode));//(*bt)->data=ch;

申请一段关于该节点种类的储藏空间//生成根结点CreatBiTree(&((*bt)->LChild));CreatBiTree(&((*bt)->RChild));

//构造左子树//构造右子树}}编程实现以上二叉树的前序、中序和后序遍历操作，输出遍历序列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->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->RChild);//求右子树的深度max=hl>hr?hl:hr;

//获取左、右子树深度较大者return(max+1);

//返回树的深度}elsereturn(0);

//若是是空树，则返回

0}四、调试解析及测试结果进入演示程序后的显示主界面：请输入二叉树中的元素；先序、中序和后序遍历分别输出结果。2.测试结果以扩展先序遍历序列输入，其中.代表空子树：ABC..DE.G..F先序遍历序列为：ABCDEGF中序遍历序列为：CBEGDFA后序遍历序列为：CGEFDBA此二叉树的深度为：53.程序运行结果1）输入二叉树中的元素（以扩展先序遍历序列输入，其中.代表空子树），显示截图为：图一2）输出结果，显示界面为：图二4.调试解析：本程序经过分别调用先序遍历、中序遍历以及后序遍历函数对二叉树中的元素进行遍历，整个程序基本满足实验要求，但是在一些细节问题上面还是存在缺陷，比方大小写字母不同样也会以致程序无法运行，这就需要我们在办理问题上认真认真，还有就是程序其实不是很完满，总之，我会在今后更加努力，是程序更完美。六、实验总结1.二叉树关于进行表达式的前缀，中缀和后缀的表示有明显的优势，既方便，又简单理解。其先序，中序和后序分别对应这表达式的前缀，中缀和后缀。在建树与进行树的遍历的时候必然要理解其建树与遍历的整个过程。否则就会连为什么这样做都不知道。在遍历树的时候最常用到的就是栈的构造了（非递归）。3.本次实验让我更加认识了哈夫曼树的构造和生成方法，以及如何用序次结构来储藏哈夫曼树及构树过程的信息，如何进行编码、译码。也感知到模块程序设计在大程序设计使用中的宽泛性，该实验是最好的证明，经过模块程序设计，能使程序可读可写性明显加强。经过本次实验，使我初步掌握了二叉树的构造特点以及各种储藏的构造的特点和适用范围，掌握了哈夫曼树的定义和思想，初步掌握了用凹入法显示树。不过程序仍有树的显示不够完满的缺点，在今后的学习中，我会不休学习，在学习中注意改变。附录源程序清单:#include<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=NULL;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->RChild);}}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);

//若是是空树，则返回

0}voidmain( ){BitTreeT;inth;intlayer;inttreeleaf;layer=0;printf("请输入二叉树中的元素(以扩展先序遍历序列输入,其