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

武汉工程大学计算机科学与工程学院《数据结构》实验报告[2]专业班级智能01实验地点机电大楼4楼419机房学生学号指导教师学生姓名实验时间第12周~第14周星期2实验项目树性结构的综合使用实验类别操作性（）验证性（）设计性（）综合性（√）其它（）实验目的及要求1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律认真完成设计任务30分报告质量操作规范、功能正确填写完整、体现收获70分说明：评阅教师：日期：20年月日实验内容计算机科学与工程学院《数据结构》实验报告2一．实验内容1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。二．程序的设计思想1实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。先构造二叉树，根据先序遍历的思想，输入根后，再输入左子树，直至左子树为空则输入上一层右字树。（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.后在同学帮助下才看到自己的这个失误。四．程序的闪光点(自我评价)1.程序模块化，各个函数分开描述，方便观察2.关键处有注释3.建立二叉树时，用先序提示输入，比较人性化。五．程序源代码(以文件为单位提供)#includeiostream.h#includemalloc.h#defineMaxsize100typedefstructTREE{structTREE*lTree;structTREE*rTree;chardata;}Tree;voidInitTree(Tree*);//初始化树voidCreatTree(Tree*);//创建二叉树voidPreTraverse(Tree*);//先序遍历递归voidPreOrderTraverse(Tree*);//先序遍历非递归voidInTraverse(Tree*tree);//中序遍历递归voidInOrderTraverse(Tree*tree);//中序遍历非递归voidPostTraverse(Tree*tree);//后序遍历递归voidLastOrderTraverse(Tree*tree);//后序遍历非递归intDepthTree(Tree*tree);//计算树的深度计算机科学与工程学院《数据结构》实验报告4intLeafsTree(Tree*tree);//计算叶子结点个数intNodesTree(Tree*tree);//计算结点个数intTwochild(Tree*tree);//计算度为二的结点个数voidmain(){intH,L;Treetree;//Treem;InitTree(&tree);CreatTree(&tree);cout先序遍历递归为:;PreTraverse(&tree);//先序遍历递归cout先序遍历非递归:;PreOrderTraverse(&tree);//先序遍历非递归coutendl;cout中序遍历递归为:;InTraverse(&tree);//中序遍历递归cout中序遍历非递归:;InOrderTraverse(&tree);//中序遍历非递归coutendl;cout后序遍历递归为:;PostTraverse(&tree);//后序遍历递归cout后序遍历非递归:;LastOrderTraverse(&tree);//后序遍历非递归coutendl;cout树的深度为:;H=DepthTree(&tree);coutHendl;cout叶子结点个数:;计算机科学与工程学院《数据结构》实验报告5L=LeafsTree(&tree);coutLendl;cout结点个数：;coutNodesTree(&tree)endl;cout度为二的结点个数;L=Twochild(&tree);coutLendl;}voidInitTree(Tree*tree)//初始化树{tree-lTree=NULL;tree-rTree=NULL;tree-data='0';}voidCreatTree(Tree*tree)//创建树{intn=0,m=0,i=0;if(tree-data=='0'){cout请输入该节点的数据：;cintree-data;}cout节点tree-data是否有左子树（0：没有1：有）：;cinn;if(n==1){Tree*lTree=(Tree*)malloc(sizeof(Tree));tree-lTree=lTree;计算机科学与工程学院《数据结构》实验报告6lTree-lTree=NULL;lTree-rTree=NULL;lTree-data='0';CreatTree(tree-lTree);cout节点tree-data是否有右子树（0：没有1：有）：;cini;if(i==0);elseif(i==1){Tree*rTree=(Tree*)malloc(sizeof(Tree));tree-rTree=rTree;rTree-lTree=NULL;rTree-rTree=NULL;rTree-data='0';CreatTree(tree-rTree);}}elseif(n==0){cout节点tree-data是否有右子树（0：没有1：有）：;cinm;if(m==0);elseif(m==1){Tree*rTree=(Tree*)malloc(sizeof(Tree));tree-rTree=rTree;rTree-lTree=NULL;rTree-rTree=NULL;计算机科学与工程学院《数据结构》实验报告7rTree-data='0';CreatTree(tree-rTree);}}}voidPreTraverse(Tree*tree)//先序遍历递归{if(tree!=NULL){couttree-data;if(tree-lTree!=NULL){PreTraverse(tree-lTree);PreTraverse(tree-rTree);}elseif(tree-rTree!=NULL){PreTraverse(tree-rTree);}else;}}voidPreOrderTraverse(Tree*tree)//先序遍历非递归{Tree*S[80]={NULL};inttop=0;while((tree!=NULL)||(top)){计算机科学与工程学院《数据结构》实验报告8if(tree!=NULL){couttree-data;top++;S[top]=tree;tree=tree-lTree;}else{tree=S[top];top--;tree=tree-rTree;}}}voidInTraverse(Tree*tree)//中序遍历递归{if(tree!=NULL){if(tree-lTree!=NULL){InTraverse(tree-lTree);couttree-data;InTraverse(tree-rTree);}elseif(tree-rTree!=NULL){couttree-data;计算机科学与工程学院《数据结构》实验报告9InTraverse(tree-rTree);}elsecouttree-data;}}voidInOrderTraverse(Tree*tree)//中序遍历非递归{Tree*D[80]={NULL};inttop=0;while((tree!=NULL)||(top)){if(tree!=NULL){top++;D[top]=tree;tree=tree-lTree;}else{tree=D[top];top--;couttree-data;tree=tree-rTree;}}}voidPostTraverse(Tree*tree)//后序遍历递归{计算机科学与工程学院《数据结构》实验报告10if(tree!=NULL){if(tree-lTree!=NULL){PostTraverse(tree-lTree);PostTraverse(tree-rTree);couttree-data;}elseif(tree-rTree!=NULL){PostTraverse(tree-rTree);couttree-data;}elsecouttree-data;}}voidLastOrderTraverse(Tree*tree)//后序遍历非递归{Tree*stack[Maxsize]={NULL},*p;p=tree;inttop=0,tag=1,i=0,k=0;while(p!=NULL||top){i=1;while(p!=NULL){stack[++top]=p;p=p-lTree;}计算机科学与工程学院《数据结构》实验报告11if(top!=0)p=stack[top]-rTree;if(p==NULL){coutstack[top--]-data;if(stack[top]!=NULL){while(i){if(stack[top]!=NULL){if(stack[top]-rTree!=NULL){if(stack[top]-rTree-data==stack[top+1]-data)coutstack[top--]-data;elsei=0;}elsei=0;}elsei=0;}}if(top!=0)p=stack[top]-rTree;elsep=NULL;}计算机科学与工程学院《数据结构》实验报告12}}intDepthTree(Tree*tree)//深度函数{intu,v;if(tree==NULL)return0;u=DepthTree(tree-lTree);v=DepthTree(tree-rTree);if(uv)return(u+1);return(v+