《2023年实验二叉树实验报告.docx》由会员分享，可在线阅读，更多相关《2023年实验二叉树实验报告.docx（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实验四二叉树的操作班级：计算机10（）2班 姓名:唐自鸿 学号：完毕日期：20 2 3.6. 1 4题目:对于给定的一二叉树，实现各种约定的遍历。一、实验目的：（1）掌握二叉树的定义和存储表达，学会建立一棵特定二叉树的方法；（2）掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想，并学会遍历 算法的递归实现和非递归实现。二、实验内容:构造二叉树，再实现二叉树的先序、中序、后序遍历，最后记录二 叉树的深度。三、实验环节：（一）需求分析. 二叉树的建立一方面要建立一个二叉链表的结构体,包含根节点和左右子 树。由于树的每一个左右子树又是一颗二叉树，所以用递归的方法来建立其左右 子树。二叉树的遍历
2、是一种把二叉树的每一个节点访问并输出的过程，遍历时根 结点与左右孩子的输出顺序构成了不同的遍历方法,这个过程需要按照不同的遍 历的方法，先输出根结点还是先输出左右孩子，可以用选择语句来实现。1 .程序的执行命令为：1）构造结点类型，然后创建二又树。2）根据提醒，从键盘输入各个结点。3）通过选择一种方式（先序、中序或者后序）遍历。4）输出结果,结束。（二）概要设计1 .二叉树的二叉链表结点存储类型定义typed e f st r uct NodeDa t aT y p e da t a;P ostOrd e r ( r oot -LChi 1 d)；P ostOrder(r o ot R Chi
3、 1 d);V i si t ( r oot data);)int Po s tTre e Dep t h (Bit T r ee b t)(int hl,hr,ma x ;i f(bt! =NULL)h l=PostTr e eDepth( b tLChild)：hr=Pos t TreeDe p t h (bt-R C hild)；max = hl h r ? h I: h r；r e t u r n(ma x + 1 );)else r e tu r n(0);求二叉树的深度求二叉树的深度求左子树的深度/求右子树的深度得到左、右子树深度较大者返回树的深度/假如是空树,则返回0) v oi
4、d main() BitTree T；int h;int layer;i n t treel e a f ；1 aye r =0;printf(请输入二叉树中的元素(以扩展先序遍历序列输入，其中.代表空子树)：rT);Or e a t BiTr e e (&T)：pr int f (先序遍历序列为:);PreO r der(T)；print f (n中序遍历序列为:)；InOrd er(T)：prin tf(n后序遍历序列为：)；Pos t Order (T);h=PostTre e De p th(T);p r i ntf(n);pr i nt f (此二义树的深度为:小斤刈;struc t
5、 Node *LChild;s t r u c t Node *RChi 1 d;JBitNod e ,*BitTr e e;.建立如下图所示二叉树:vo i d CreatB i Tree(B i t Tr e e *bt)用扩展先序遍历 序列创建二叉树，假如是当前树根置为空，否则申请一个新节点。2 .本程序包含四个模块1)主程序模块：2)先序遍历模块3)中序遍历模块4)后序遍历模块(三)具体设计1 .建立二又树存储类型=4勾造二叉树=void C r eat BiTree (Bit Tree *bt) 用扩展先序遍历序列创建二叉树，假如是当前树根置为空，否则申请一个新节点/Char ch；
6、c h = g etchar();if (ch=,./) *b t =NULL;else*bt= (Bit Tree)ma 1 Io c ( s i ze o f (B itNod e ); / / 申请一段关于该节点类型的存储空间(*b t ) d a ta= c h;生成根结点CreatBiT r e e(& (*bt)-LC h ild)； 构造左子树CreatBiTree (& (*bt)-RChi 1 d); 构造右子树)2 .编程实现以上二叉树的前序、中序和后序遍历操作，输出遍历序列1 )先序遍历二叉树的递归算法如下：void Pr e Or d e r(Bit T r e e r
7、o o t)(i f (root! = NULL)(V i s it(roo t da t a )；P r e 0 r der (r o ot - L Child); /递归调用核心P r e0rd e r (root RChi 1 d);)2)中序遍历二叉树的递归算法如下：void I n 0 r d er(B i tTree root)(if (root! =NULL)InO r d e r(root -LCh ild)；Vi s it (r o ot -d a t a)；1 nO r d e r (ro o t -RC h ild);)3)后序遍历二叉树的递归算法如下：voi d P o
8、 s tOr d e r (BitT r e e root)(i f (root!=NULL )(PostOrder(roo t -LCh i Id)：Po s 10 rd e r(r o ot -RChi Id);Vis i t (roo t -d a ta);)4 )计算二叉树的深度算法如下：i n t PostTree D ep t h (Bit T re e b t)/求二叉树的深度int hl, h r.max;i f (bt! = NULL)(hl=PostTreeDep t h(bt-LChild); 求左子树的深度h r =P o stTre e Dep t h( b t- R
9、Child) ; /求右子树的深度max= h lhr?hl:hr;/得到左、右子树深度较大者返回树的深度ret u r n(max+1);else return (0);else return (0);/假如是空树，则返回0四、调试分析及测试结果1 .进入演示程序后的显示主界面：请输入二叉树中的元素；先序、中序和后序遍历分别输出结果。2 .测试结果以扩展先序遍历序列输入，其中.代表空子树：ABC. DE.G. .F.先序遍历序列为:A BCDEGF中序遍历序列为:CBEGDFA后序遍历序列为:C GEFDBA此二叉树的深度为:5.程序运营结果1）输入二叉树中的元素（以扩展先序遍历序列输入，其
10、中.代表空子树），显示截图 为： *C:Program Files （x86）Microsoft Visual StudioMyProjectseeDebugee.exe请输入二叉树中的元素V 以扩展先序遍历序列输入.其中.代表空子树）：图一2）输出结果,显示界面为:S3 C:Program Files (x86)Microsoft Visual StudioMyPrqiectseeDebugee.exe八.Disw 叉 wc.tylyij-八.Disw 叉 wc.tylyij-二叉树中的元素 以扩展先序遍历序列输入，其中.代表空子树:1. G. F.万庄列为：ABCDEGF力序歹为：CBEG
11、DFA无序歹J为：CGEFDBA用的深度为邙any key to continue图二4.调试分析：本程序通过度别调用先序遍历、中序遍历以及后序遍历函数对二叉树中的元 素进行遍历，整个程序基本满足实验规定，但是在一些细节问题上面还是存在缺 陷，比如大小写字母不同也会导致程序无法运营，这就需要我们在解决问题上认 真细致，尚有就是程序并不是很完善，总之，我会在此后更加努力，是程序更完美。六、实验总结1 .二叉树对于进行表达式的前缀，中缀和后缀的表达有明显的优势，既方便，又 容易理解。其先序，中序和后序分别相应这表达式的前缀，中缀和后缀。2 .在建树与进行树的遍历的时候一定要理解其建树与遍历的整个过
12、程。不 然就会连为什么这样做都不知道。在遍历树的时候最常用到的就是栈的结构了 （非递归）。3 .本次实验让我更加了解了哈夫曼树的构造和生成方法，以及如何用顺序结 构来存储哈夫曼树及构树过程的信息，如何进行编码、译码。也感知到模块程序 设计在大程序设计使用中的普遍性，该实验是最佳的证明，通过模块程序设计，能 使程序可读可写性明显加强。通过本次实验，使我初步掌握了二叉树的结构特性以及各种存储的结构的特 点和合用范围，掌握了哈夫曼树的定义和思想，初步掌握了用凹入法显示树。但 是程序仍有树的显示不够完善的缺陷，在此后的学习中，我会不断学习，在学习 中注意改变。附录源程序清单:# i ncl u dei
13、 nclude# inc 1 u de in c I u de t y pede f int Data T y p e ;t ype d e f s t ruct Node创建结点类型结构体(D a taT ype d a ta；s truct Node *LC h ild；st r uct N o d e * RChild;BitNo d e,*BitTree;v oid CreatBiTre e (B i tTree *bt) /用扩展先序遍历序列创建二叉树，假如是当前树 根置为空，否则申请一个新节点/ch a r ch；ch=g e tchar()；if(ch=z. )*bt=NULL；
14、else(*bt= ( B i tTreeJmall o c(siz e of(Bi t Nod e );(*bt)-d a ta= c h;C r eatBiT r e e (& (*bt) LChild);CreatB i Tree(&(* bt)- RChild)；)v o id v is i t(char c h)访问根节点printf (%cM, c h);void Pre Order(B i tTree root) /先序遍历二叉树的递归算法(i f (roo t !=NULL)Visi t (ro o t data);PreO r der (root -LC h i 1 d);PreOrd e r (root RChild)；voi d InOrd e r (B i tTre e r oot) /中序遍历二叉树的递归算法(if (root!=NULL)(In O rde r (ro o t -LChild);Vi s it(roo t -d a ta);InOrde r (r o o t -RChil d );)voi d P o s t O r de r (B i tTree root) /后序遍历求二叉树的递归算法if(root!=NULL)