数据结构实验报告-二叉树

数据结构上机实验报告学号姓名所在系计算机科学与技术班级:_实验名称二叉树的基本应用实验日期实验指导教师实验机房.实验目的⑴理解树这种数据结构⑵掌握二叉树二叉链表这种存储结构⑶完成二叉树各种基本运算的算法.实验内容

（1）实现二叉树创建的算法立现一y树名种遍吊篁部⑶蠢见三叉树其他操作的算包括统计叶子结点的个数求二叉树的深度、线索二叉树等

3.算法设计（编程思路或者流程图）1）二叉树创建的算法BiTNode.h#includeiostream#includequeueusingnamespacestd;TElemTypedata;structBiTNode*lchildJchild;.}BiTNode*BiTree;

14.//先序创建二叉树BiTreecreateBiTreeBiTreet{TElemTypedata;cindata;ifdata==#{t=NULL;else{t=newBiTNode;if!t{returnOVERFLOW;}t-data=data;t-lchild=createBiTreet-lchild;t-rchild=createBiTreet-rchild;}returnt;}//层序遍历二叉树voidlevelOrderBiTreet{queueBiTreeq;ift{//如果根节点非空，则根节点入队列q.pusht;while!q.empty{〃循环遍历，出队列的同时，摆布孩子入队尾BiTreetemp=q.front;q.pop；couttemp-dataendl;iftemp-lchild{q.pushtemp-lchild;45・}iftemp-rchild{q.pushtemp-rchild;•}}

51.}main.cpp:#include”B:iTNode・h”intmain{BiTreet=NULL;cout***************采用递归函数构造一个二叉树********************”endl;cout”请输入二叉树的字符序列ift=createBiTreet{cout〈二叉树创建成功！现在层序输出«endl;levelOrdert;}else{cout«”很遗憾创建二叉树失败！«endl;}return0;}2）二叉树各种遍历算法BiTNode.h#includeiostream#includequeueusingnamespacestd;#defineMAX20#defineOK1#defineERROR0#defineNULL0#defineOVERFLOW0typedefcharTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchildJ*rchild;.}BiTNode*BiTree;

14.//先序创建二叉树BiTreecreateBiTreeBiTreet{TElemTypedata;cindata;ifdata==#{t=NULL;else{t=newBiTNode;if!t{returnOVERFLOW;t-data=data;tlchild=createBiTreet-lchild;t-rchild=createBiTreet-rchild;}returnt;}//层序遍历二叉树voidlevelOrderBiTreet{queueBiTreeq;ift{//如果根节点非空，则根节点入队列q.pusht;while!q.empty{〃循环遍历，出队列的同时，摆布孩子入队尾BiTreetemp=q.front；q・pop;couttemp-dataiftemp-lchild{q・pushtemp-lchild;iftemp-rchild{qpushtemp-rchild;//先序遍历voidpreOrderBiTreet{ift==NULL{return;}coutt-datapreOrdert-lchild;.preOrdert-rchild;}//中序遍历voidinOrderBiTreet{ift==NULL{return;}inOrdert-lchild;coutt-data.inOrdert-rchild;}〃后序遍历voidpostOrderBiTreet{ift==NULL{return;.postOrdert-lchild;postOrdert-rchild;coutt-data}M6in.cqq

1.#includeBiTNode.h

2.

3.

4.intmain{BiTreet=NULL;

5.cout”**************=1c采用递归函数构造一个二叉树endl;

6.cout”请输入二叉树的字符序列:

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.ift=createBiTreet{cout二叉树创建成功！cout”先序遍历preOrdert;cout\n中序遍历inOrdert;cout\n后序遍历postOrdert;cout\n层序遍历”levelOrdert;*endl;endl;

17.

18.

19.

20.

21.

22.endl;endl;endl;else{cout”很遗憾创建二叉树失败！”endl;}return0;3叶子结点统计的算法创建二叉树的算法在前面实验中已经写过，这里只写计算叶子结点数的算法:在BiTNode.h中添加以下内容

1.

2.

3.〃计算叶子节点intleafNumber=0;voidgetLeafNumberBiTreet{

4.

5.iftif

6.

7.t-lchild==NULLt-rchild==NULL{leafNumber++;cout”叶子节数据t-dataendl;

8.

9.

10.

11.getLeafNumbert-lchild;getLeafNumbert-rchild;}

12.Main.cpp

1.#includeBiTNode.hintmain{BiTreet=NULL;cout”***************采用递归函数构造一个二叉树********************end1•cout”请输入二叉树的字符序列ift=createBiTreet{cout二叉树创建成功！endl;getLeafNumbert;cout”这棵二叉树的叶子节点有“leafNumber”个endl;}else{cout”很遗憾创建二叉树失败！endl;}return0;}4二叉树深度统计算法同理，这里只写统计深度的算法和main.cpp中的内容〃二叉树深度统计intgetMaxLevelBiTreet{intdepl=0Jdep2=0;ift{depl=getMaxLevelt-lchild;dep2=getMaxLevelt-rchild;returndepldep2depl+1:dep2+1;}else{return0;}}Main.cpp#includeBiTNode.hintmain{BiTreet=NULL;cout***************采用递归函数构造一个二叉树endl;cout”请输入二叉树的字符序列ift=createBiTreet{cout二叉树创建成功！endl;cout”这棵二叉树的深度是getMaxLeveltendl;}else{cout“很遗憾创建二叉树失败！«endl;}return0;}

4.程序调试（实验数据记录一一根据程序要求输入几组不同数据，记录程序运行结果，并分析结果分析程序运行中浮现的主要错误或者对其他程序环境的使用情况的记录注必须认真书写）1）二叉树创建的算法测试如下二叉树图1-1实验结果:□IMicrosoftVisualStudio伺试控制台二又树创足成功！现层序物出a2）二叉树各种遍历算法测试二叉树如下C*\UsftXAdsinistf*toc\D*sHtop\学剧作金、於据Z构*R\二义例、2*1归/二JLt^\D*bu\62气34；0«住修自向itlfu…4）二叉树深度统计算法仍然测试图2-1的二叉树:5・讨论（通过实验的一些体味、学会的知识和技能等）1）二叉树创建的算法关于二叉树的创建，首先为了能让每一个结点确认是否有摆布孩子，我们对它进行了扩展，也就是将二叉树中每一个结点的空指针引出一个虚结点，其值为一特定值，比如我们称这种处理后的二叉树为原二叉树的扩展二叉树扩展二叉树就可以做到一个遍历序列确定一棵二叉树了上面的实验用了先序遍历来创建而二叉树，就首先要写出扩展二叉树的先序遍历序列，然后从键盘上输入序列就可以创建二叉树了在层序遍历二叉树的时候用到了队列的知识，在C++头文件queue中封装了队列，直接引入头文件就可以来使用队列，通过Queue◊就可以创建对象，利用队列的性质，实现层序遍历二叉树2）二叉树各种遍历算法二叉树的遍历主要分为四种前序遍历，中序遍历，后序遍历以及层序遍历下面简述一下上面程序主要运用的思想前序遍历若树为空，则空操作返回否则，先访问根节点，然后前序遍历左子树，再前序遍历右子树中序遍历若树为空，则空操作返回否则，从根节点开始（注意并非先访问根节点），中序遍历根节点的左子树，然后是访问根节点，最后中序遍历根节点的右子树后序遍历若树为空，则空操作返回否则，从左到右先叶子后节点的方式遍历访问摆布子树，最后访问根节点层序遍历若树为空，则空操作返回否则，从树的第一层，也就是根节点开始访问，从上到下逐层遍历，在同一层中，按从左到右的顺序结点逐个访问3）叶子结点统计的算法统计叶子节点的算法设计与二叉树的几种遍历方法是分不开的，在本次实验中，采用先序遍历统计二叉树的叶子数，由于如果一个节点是叶子的话，其摆布孩子均为空，所以可用摆布孩子均为空的方法来判断是否为叶子节点，然后定义全局变量统计叶子节点即可4）二叉树深度统计算法求二叉树的深度算法实际上是递归的应用，运用递归找到二叉树的叶子各个叶子节点并加以比较，找到最“深”的那个叶子节点，即为二叉树的深度。