数据结构二叉树综合实验报告

计算机科学与工程学院武汉理工大学计算机科学与工程学院数据结构实验报告2专业班智能01实验场所机电大楼四楼419室学生学号指导教师学生姓名实验时间第12周第14周第2周实验项目树性结构的综合使用实验类别操作性() 验证性() 设计性() 综合()其他() 实验的目的和要求1 .实现追溯二叉树前序、中序和后序的递归算法和非递归算法。2 .求二叉树的节点数、叶节点数、二叉树的高度、度为2的节点数。成绩评定表类别评分标准分数得分合计乘机积极上班，遵守纪律认真完成设计任务三十分报告质量操作规范，功能正确完全填写，表现收获70分说明：评审员：日期： 20年月日实验内容1 .实验内容1 .实现追溯二叉树前序、中序和后序的递归算法和非递归算法。2 .求二叉树的节点数、叶节点数、二叉树的高度、度为2的节点数。2 .程序设计思想实现一种追溯一二叉树前序、中序和后序的递归算法和非递归算法。先构筑二叉树，根据先到的思想输入根，然后输入左子树直到左子树变空。(1)二叉树的非递归扫描在显示堆栈中存储二叉树的节点指针，先扫描时，按照二叉树前扫描的顺序访问节点，将节点的指针放入堆栈，取堆栈的顶点指针直到堆栈的顶点指针指向节点的左指针字段为止删除堆栈顶点指针，访问刚取出后指针指向的节点右指针指向的节点，将其放入堆栈后，重复非递归操作。(2)二叉树的递归扫描：二叉树为空时空操作第一次扫描：(a )访问根节点；(b )按顺序横穿左子树；(c )按顺序横穿右子树。中间导线测量：(a )按中等顺序横断左子树；(b )访问根节点(c )按顺序巡视右子树推迟：(a )后遍历左子树；(b )稍后巡视右子树(c )访问根节点。2 .求二叉树的节点数、叶节点数、二叉树的高度、度为2的节点数。(1)求二叉树的叶节点数：分别求左右子树的叶节点数，计算其和为二叉树的叶节点数。(2)二叉树的节点数之和：首先求出左子树右子树的节点之和，计算其和。(3)二叉树的高度：首先判断二叉树是否为空，如果为空，则将该二叉树的高度设为0。 否则，首先分别求出左右子树的深度进行比较，再加上较大的树来求出。(4)二叉树的度为2的节点数：计算有左右孩子的节点数，度为2的节点数。实验内容数数儿。3 .编程过程中遇到的问题和解决办法(1)后续扫描的非递归函数涉及背轨道的方法，但是由于开始设计的方案太简单，形成死循环并且始终在最后一个节点重复，改变背轨道后，该问题得到解决。(2)计算二叉树的中度为2的节点数的话，回到循环时，根节点有没有左右的子树没有关系，但是个人设计时，根据总是把自己作为有左右的子树的默认值，自己增加1 .之后被同学帮助才看到自己的错误。4 .程序闪光点(自我评估)1 .程序被模块化，各函数分别描述，观察容易2 .重点有评论3 .制作二叉树时，首先提示输入，人性化。5 .程序源代码(以文件为单位提供)#include#include#define Maxsize 100typedef结构树结构树* l树；结构树*树；char data；Tree；void init树(树* ) /初始化树void创建树(树* ) /制作二叉树void PreTraverse(Tree* ) /递归顺序遍历void PreOrderTraverse(Tree* ) : /首先非递归扫描void InTraverse(Tree *tree) /中序遍历递归void in order traverse (tree * tree )/中序遍历非递归void PostTraverse(Tree *tree) /循环递归voidalastordertraverse (tree * tree )/非递归递归int DepthTree(Tree *tree) /计算树的深度int LeafsTree(Tree *tree) /计算叶节点数int NodesTree(Tree *tree) /计算节点数int Twochild(Tree*tree) /计算度为2的节点数void main ()装模作样int H，l；树状结构；/Tree m；init tree (树)创建树(树)cout 最初的扫描递归是： PreTraverse(tree) /递归顺序遍历cout首先循环非递归：PreOrderTraverse(tree) /首先非递归扫描coutlTree=NULL；tree-rTree=NULL；树数据=0；以下称为创建void创建树(树*树)装模作样int n=0，m=0，i=0；if (树数据=0)装模作样cout 请输入此节点的数据： ；cintree-data；以下称为cout 节点 data 中是否有左子树(0:无1 :有):；cinn；if(n=1)装模作样tree * LD tree=(tree * ) malloc (sizeof (tree ) )故障诊断树=故障诊断树；LD树- LD树=空；l树-树=空；l树数据=0；创建树(树- l树)cout节点 data 是否有右子树(0:无1 :有):；cini；if(i=0)else if(i=1)装模作样tree * rtree=(tree * ) malloc (sizeof (tree ) )树-树=树；rTree-lTree=NULL；rTree-rTree=NULL；rTree-data=0；创建树(树状结构)以下称为以下称为else if(n=0)装模作样cout节点 data 是否有右子树(0:无1 :有):；cinm；if(m=0)else if(m=1)装模作样tree * rtree=(tree * ) malloc (sizeof (tree ) )树-树=树；rTree-lTree=NULL；rTree-rTree=NULL；rTree-data=0；创建树(树状结构)以下称为以下称为以下称为void PreTraverse(Tree*tree)/首先遍历递归装模作样tree！=NULL )装模作样coutdata ；if (树- l树！=NULL )装模作样预览树(tree-l tree )预览树(tree-rtree )以下称为else if (树-树！=NULL )装模作样预览树(tree-rtree )以下称为else；以下称为以下称为voidpreordertraverse (tree * tree )/首先遍历非递归的装模作样Tree *S80=NULL；int top=0；while，tree！=null| (顶部) )装模作样tree！=NULL )装模作样coutdata ；top；Stop=tree；tree=tree-lTree；以下称为else装模作样tree=Stop；第- -；tree=tree-rTree；以下称为以下称为以下称为void InTraverse(Tree *tree)/中序遍历递归装模作样tree！=NULL )装模作样if (树- l树！=NULL )装模作样入侵故障(tree-l tree )coutdata ；入侵树(tree-rtree )以下称为else if (树-树！=NULL )装模作样coutdata ；入侵树(tree-rtree )以下称为elsecoutdata ；以下称为以下称为voidinordertraverse (tree * tree )/中序遍历非递归装模作样Tree *D80=NULL；int top=0；while，tree！=null| (顶部) )装模作样tree！=NULL )装模作样top；Dtop=tree；tree=tree-lTree；以下称为else装模作样tree=Dtop；第- -；coutdata ；tree=tree-rTree；以下称为以下称为以下称为void PostTraverse(Tree *tree)/在后面遍历递归装模作样tree！=NULL )装模作样if (树- l树！=NULL )装模作样开机自检故障诊断树开机自检树(tree-rtree )coutdata ；以下称为else if (树-树！=NULL )装模作样开机自检树(tree-rtree )coutdata ；以下称为elsecoutdata ；以下称为以下称为voidalastordertraverse (tree * tree )/后序不递归装模作样Tree *stackMaxs