数据结构二叉树综合实验报告(共14页)

1、精选优质文档-倾情为你奉上武 汉 工 程 大 学计算机科学与工程学院数据结构实验报告2专业班级智能01实验地点机电大楼4 楼 419 机房学生学号指导教师学生姓名实验时间第 12 周第14 周 星期2 实验项目树性结构的综合使用实验类别操作性（） 验证性（ ） 设计性（ ） 综合性（ ） 其它（ ）实验目的及要求1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。成 绩 评 定 表类 别评 分 标 准分值得分合 计上机表现积极出勤、遵守纪律认真完成设计任务30分报告质量操作规范、功能正确填写完整、体现收获70分说明：

2、 评阅教师： 日 期： 20 年 月 日实 验 内 容一实验内容1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。二程序的设计思想1实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。先构造二叉树，根据先序遍历的思想，输入根后，再输入左子树，直至左子树为空则输入上一层右字树。（1）二叉树的非递归遍历是用显示栈来存储二叉树的结点指针，先序遍历时，按二叉树前序遍历的顺序访问结点，并将结点的指针入栈，直到栈顶指针指向结点的左指针域为空时取出栈顶指针并删除栈顶指针，访问刚取出的指针指向的结点的右指针指向的结点并将其指针

3、入栈，如此反复执行则为非递归操作。（2）二叉树的递归遍历：若二叉树为空，则空操作先序遍历：（a）访问根结点； （b）先序遍历左子树；（c）先序遍历右子树。中序遍历 ： （a）中序遍历左子树； （b）访问根结点；（c）中序遍历右子树后序遍历： （a）后序遍历左子树； （b）后序遍历右子树； （c）访问根结点。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。（1）求二叉树的叶子结点个数：先分别求得左右子树中个叶子结点的个数，再计算出两者之和即为二叉树的叶子结点数。（2）二叉树的结点个数之和：先分别求得左子树右子树中结点之和，再计算两者之和即为所求。（3）二叉树的高度：首先判断

4、二叉树是否为空，若为空则此二叉树高度为0,。否则，就先分别求出左右子树的深度进行比较，取较大的树加一即为所求。（4）二叉树的度为2的结点个数：计算有左右孩子的结点个数，即为度为2的结点个实 验 内 容数。三编程过程中遇到的问题及解决办法（1）后续遍历的非递归函数涉及到回溯的方法，开始设计的方案想的太过于简单，所以形成了死循环，总是在最后的节点处不停地循环，后改成回溯后，该问题得到解决。（2）计算二叉树中度为2的结点个数中，返回循环的时候不论根结点有没有左右子树，但个人设计时，根总是会将自己默认为有左右子树，自行增加1.后在同学帮助下才看到自己的这个失误。四程序的闪光点(自我评价)1.程序模块化

5、，各个函数分开描述，方便观察2.关键处有注释3.建立二叉树时，用先序提示输入，比较人性化。 五程序源代码(以文件为单位提供)#include<iostream.h>#include<malloc.h>#define Maxsize 100typedef struct TREEstruct TREE *lTree;struct TREE *rTree;char data;Tree;void InitTree(Tree*);/初始化树void CreatTree(Tree*);/创建二叉树void PreTraverse(Tree*);/先序遍历递归void PreOrde

6、rTraverse(Tree*);/先序遍历非递归void InTraverse(Tree *tree);/中序遍历递归void InOrderTraverse(Tree *tree);/中序遍历非递归void PostTraverse(Tree *tree);/后序遍历递归void LastOrderTraverse(Tree *tree);/后序遍历非递归int DepthTree(Tree *tree);/计算树的深度int LeafsTree(Tree *tree);/计算叶子结点个数int NodesTree(Tree *tree);/计算结点个数int Twochild(Tree*

7、tree);/计算度为二的结点个数void main()int H,L;Tree tree;/Tree m;InitTree(&tree);CreatTree(&tree);cout<<"先序遍历递归为:"PreTraverse(&tree);/先序遍历递归cout<<"先序遍历非递归:"PreOrderTraverse(&tree);/先序遍历非递归cout<<endl;cout<<"中序遍历递归为:"InTraverse(&tree);/中序遍

8、历递归cout<<"中序遍历非递归:"InOrderTraverse(&tree);/中序遍历非递归cout<<endl;cout<<"后序遍历递归为:"PostTraverse(&tree);/后序遍历递归cout<<"后序遍历非递归:"LastOrderTraverse(&tree);/后序遍历非递归cout<<endl; cout<<"树的深度为:" H=DepthTree(&tree);cout<&

9、lt;H<<endl;cout<<"叶子结点个数:"L=LeafsTree(&tree); cout<<L<<endl;cout<<"结点个数："cout<<NodesTree(&tree)<<endl;cout<<"度为二的结点个数"L=Twochild(&tree);cout<<L<<endl;void InitTree(Tree *tree)/初始化树tree->lTree=NUL

10、L;tree->rTree=NULL;tree->data='0'void CreatTree(Tree *tree)/创建树int n=0,m=0,i=0;if(tree->data='0')cout<<"请输入该节点的数据："cin>>tree->data;cout<<"节点"<<tree->data<<"是否有左子树（0：没有 1：有）："cin>>n;if(n=1)Tree *lTree=(Tr

11、ee*)malloc(sizeof(Tree);tree->lTree=lTree;lTree->lTree=NULL;lTree->rTree=NULL;lTree->data='0'CreatTree(tree->lTree);cout<<"节点"<<tree->data<<"是否有右子树（0：没有 1：有）："cin>>i;if(i=0);else if(i=1)Tree *rTree=(Tree*)malloc(sizeof(Tree);tree-

12、>rTree=rTree;rTree->lTree=NULL;rTree->rTree=NULL;rTree->data='0'CreatTree(tree->rTree);else if(n=0)cout<<"节点"<<tree->data<<"是否有右子树（0：没有 1：有）："cin>>m; if(m=0);else if(m=1)Tree *rTree=(Tree*)malloc(sizeof(Tree);tree->rTree=rTree;

13、rTree->lTree=NULL;rTree->rTree=NULL;rTree->data='0'CreatTree(tree->rTree);void PreTraverse(Tree*tree)/先序遍历递归if(tree!=NULL)cout<<tree->data<<" "if(tree->lTree!=NULL)PreTraverse(tree->lTree);PreTraverse(tree->rTree);else if(tree->rTree!=NULL)Pre

14、Traverse(tree->rTree);else;void PreOrderTraverse(Tree *tree)/先序遍历非递归Tree *S80=NULL;int top =0;while (tree!=NULL)|(top)if (tree!=NULL)cout<<tree->data<<" "top+;Stop = tree; tree = tree->lTree;elsetree = Stop;top-;tree = tree->rTree;void InTraverse(Tree *tree)/中序遍历递归i

15、f(tree!=NULL)if(tree->lTree!=NULL)InTraverse(tree->lTree);cout<<tree->data<<" "InTraverse(tree->rTree);else if(tree->rTree!=NULL)cout<<tree->data<<" "InTraverse(tree->rTree);elsecout<<tree->data<<" "void InOrde

16、rTraverse(Tree *tree)/中序遍历非递归Tree *D80=NULL;int top =0;while (tree!=NULL)|(top)if (tree!=NULL)top+;Dtop = tree; tree = tree->lTree;elsetree = Dtop;top-;cout<<tree->data<<" "tree = tree->rTree;void PostTraverse(Tree *tree)/后序遍历递归if(tree!=NULL)if(tree->lTree!=NULL)Pos

17、tTraverse(tree->lTree);PostTraverse(tree->rTree);cout<<tree->data<<" "else if(tree->rTree!=NULL)PostTraverse(tree->rTree);cout<<tree->data<<" "elsecout<<tree->data<<" "void LastOrderTraverse(Tree *tree)/后序遍历非递归Tre

18、e *stackMaxsize=NULL,*p;p=tree;int top=0,tag=1,i=0,k=0;while(p!=NULL | top)i=1;while(p!=NULL)stack+top=p;p=p->lTree;if(top!=0)p=stacktop->rTree;if(p=NULL)cout<<stacktop->data<<" "if(stacktop!=NULL)while(i)if(stacktop!=NULL)if(stacktop->rTree!=NULL)if(stacktop->rT

19、ree->data=stacktop+1->data)cout<<stacktop->data<<" "elsei=0;elsei=0;elsei=0;if(top!=0)p=stacktop->rTree;elsep=NULL;int DepthTree(Tree *tree) /深度函数 int u,v; if (tree=NULL) return 0; u=DepthTree(tree->lTree); v=DepthTree(tree->rTree); if (u>v) return (u+1); return (v+1); int LeafsTree(Tree *tree)/子叶个数函数 int num1,num2; if(tree=NULL) return 0; else if(tree->lTree=NULL&