数据结构二叉树的递归算法实验报告

.数据结构二叉树的递归算法实验报告整理文档整理文档.整理文档齐鲁工业大学实验报告成绩课程名称数据结构指导教师单健芳实验日期院（系）信息学院专业班级计科（嵌入）14-1实验地点学生姓名高晨悦学号201403071007同组人无实验项目名称二叉树的递归算法一、实验目的和要求1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。二、实验环境微型计算机vc6.0三、实验内容1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。四、实验步骤一．实验内容1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。二．程序的设计思想数据结构二叉树的递归算法实验报告全文共20页，当前为第1页。1实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。数据结构二叉树的递归算法实验报告全文共20页，当前为第1页。先构造二叉树，根据先序遍历的思想，输入根后，再输入左子树，直至左子树为空则输入上一层右字树。（1）二叉树的非递归遍历是用显示栈来存储二叉树的结点指针，先序遍历时，按二叉树前序遍历的顺序访问结点，并将结点的指针入栈，直到栈顶指针指向结点的左指针域为空时取出栈顶指针并删除栈顶指针，访问刚取出的指针指向的结点的右指针指向的结点并将其指针入栈，如此反复执行则为非递归操作。（2）二叉树的递归遍历：若二叉树为空，则空操作先序遍历：（a）访问根结点；（b）先序遍历左子树；（c）先序遍历右子树。中序遍历：（a）中序遍历左子树；（b）访问根结点；（c）中序遍历右子树后序遍历：（a）后序遍历左子树；（b）后序遍历右子树；（c）访问根结点。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。（1）求二叉树的叶子结点个数：先分别求得左右子树中个叶子结点的个数，再计算出两者之和即为二叉树的叶子结点数。（2）二叉树的结点个数之和：先分别求得左子树右子树中结点之和，再计算两者之和即为所求。（3）二叉树的高度：首先判断二叉树是否为空，若为空则此二叉树高度为0,。否则，就先分别求出左右子树的深度进行比较，取较大的树加一即为所求。（4）二叉树的度为2的结点个数：计算有左右孩子的结点个数，即为度为2的结点个数。数据结构二叉树的递归算法实验报告全文共20页，当前为第2页。数据结构二叉树的递归算法实验报告全文共20页，当前为第2页。（1）后续遍历的非递归函数涉及到回溯的方法，开始设计的方案想的太过于简单，所以形成了死循环，总是在最后的节点处不停地循环，后改成回溯后，该问题得到解决。（2）计算二叉树中度为2的结点个数中，返回循环的时候不论根结点有没有左右子树，但个人设计时，根总是会将自己默认为有左右子树，自行增加1.后在同学帮助下才看到自己的这个失误。四．程序的闪光点(自我评价)1.程序模块化，各个函数分开描述，方便观察2.关键处有注释3.建立二叉树时，用先序提示输入，比较人性化。五．程序源代码(以文件为单位提供)#include<iostream.h>#include<malloc.h>#defineMaxsize100typedefstructTREE{ structTREE*lTree; structTREE*rTree; chardata;}Tree;数据结构二叉树的递归算法实验报告全文共数据结构二叉树的递归算法实验报告全文共20页，当前为第3页。voidInitTree(Tree*);//初始化树voidCreatTree(Tree*);//创建二叉树voidPreTraverse(Tree*);//先序遍历递归voidPreOrderTraverse(Tree*);//先序遍历非递归voidInTraverse(Tree*tree);//中序遍历递归voidInOrderTraverse(Tree*tree);//中序遍历非递归voidPostTraverse(Tree*tree);//后序遍历递归voidLastOrderTraverse(Tree*tree);//后序遍历非递归intDepthTree(Tree*tree);//计算树的深度intLeafsTree(Tree*tree);//计算叶子结点个数intNodesTree(Tree*tree);//计算结点个数intTwochild(Tree*tree);//计算度为二的结点个数voidmain(){ intH,L; Treetree;// Treem;数据结构二叉树的递归算法实验报告全文共20页，当前为第4页。 InitTree(&tree);数据结构二叉树的递归算法实验报告全文共20页，当前为第4页。 CreatTree(&tree); cout<<"先序遍历递归为:"; PreTraverse(&tree);//先序遍历递归 cout<<"先序遍历非递归:"; PreOrderTraverse(&tree);//先序遍历非递归 cout<<endl;cout<<"中序遍历递归为:"; InTraverse(&tree);//中序遍历递归 cout<<"中序遍历非递归:"; InOrderTraverse(&tree);//中序遍历非递归 cout<<endl; cout<<"后序遍历递归为:"; PostTraverse(&tree);//后序遍历递归 cout<<"后序遍历非递归:"; LastOrderTraverse(&tree);//后序遍历非递归 cout<<endl;cout<<"树的深度为:";数据结构二叉树的递归算法实验报告全文共20页，当前为第5页。数据结构二叉树的递归算法实验报告全文共20页，当前为第5页。 cout<<H<<endl; cout<<"叶子结点个数:"; L=LeafsTree(&tree);cout<<L<<endl; cout<<"结点个数："; cout<<NodesTree(&tree)<<endl; cout<<"度为二的结点个数"; L=Twochild(&tree); cout<<L<<endl;}voidInitTree(Tree*tree)//初始化树{ tree->lTree=NULL; tree->rTree=NULL; tree->data='0';}数据结构二叉树的递归算法实验报告全文共20页，当前为第6页。voidCreatTree(T数据结构二叉树的递归算法实验报告全文共20页，当前为第6页。{ intn=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=(Tree*)malloc(sizeof(Tree)); tree->lTree=lTree; lTree->lTree=NULL; lTree->rTree=NULL; lTree->data='0'; CreatTree(tree->lTree);数据结构二叉树的递归算法实验报告全文共20页，当前为第7页。数据结构二叉树的递归算法实验报告全文共20页，当前为第7页。 cin>>i; 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：有）："; cin>>m;数据结构二叉树的递归算法实验报告全文共20页，当前为第8页。数据结构二叉树的递归算法实验报告全文共20页，当前为第8页。 elseif(m==1) { Tree*rTree=(Tree*)malloc(sizeof(Tree)); tree->rTree=rTree; rTree->lTree=NULL; rTree->rTree=NULL; rTree->data='0'; CreatTree(tree->rTree); } }}voidPreTraverse(Tree*tree)//先序遍历递归{ if(tree!=NULL) { cout<<tree->data<<""; if(tree->lTree!=NULL)数据结构二叉树的递归算法实验报告全文共20页，当前为第9页。数据结构二叉树的递归算法实验报告全文共20页，当前为第9页。 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)) { if(tree!=NULL)数据结构二叉树的递归算法实验报告全文共20页，当前为第10页。数据结构二叉树的递归算法实验报告全文共20页，当前为第10页。 cout<<tree->data<<""; top++; S[top]=tree;tree=tree->lTree; } else { tree=S[top]; top--; tree=tree->rTree; } }}voidInTraverse(Tree*tree)//中序遍历递归{ if(tree!=NULL)数据结构二叉树的递归算法实验报告全文共20页，当前为第11页。数据结构二叉树的递归算法实验报告全文共20页，当前为第11页。 if(tree->lTree!=NULL) { InTraverse(tree->lTree); cout<<tree->data<<""; InTraverse(tree->rTree); } elseif(tree->rTree!=NULL) { cout<<tree->data<<""; InTraverse(tree->rTree); } else cout<<tree->data<<""; }}voidInOrderTraverse(Tree*tree)//中序遍历非递归{数据结构二叉树的递归算法实验报告全文共20页，当前为第12页。数据结构二叉树的递归算法实验报告全文共20页，当前为第12页。 inttop=0; while((tree!=NULL)||(top)) { if(tree!=NULL) { top++; D[top]=tree;tree=tree->lTree; } else { tree=D[top]; top--; cout<<tree->data<<""; tree=tree->rTree; } }数据结构二叉树的递归算法实验报告全文共20页，当前为第13页。}数据结构二叉树的递归算法实验报告全文共20页，当前为第13页。voidPostTraverse(Tree*tree)//后序遍历递归{ if(tree!=NULL) { if(tree->lTree!=NULL) { PostTraverse(tree->lTree); PostTraverse(tree->rTree); cout<<tree->data<<""; } elseif(tree->rTree!=NULL) { PostTraverse(tree->rTree); cout<<tree->data<<""; } else cout<<tree->data<<"";数据结构二叉树的递归算法实验报告全文共20页，当前为第14页。 }数据结构二叉树的递归算法实验报告全文共20页，当前为第14页。}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; } if(top!=0) p=stack[top]->rTree; if(p==NULL)数据结构二叉树的递归算法实验报告全文共20页，当前为第15页。 {数据结构二叉树的递归算法实验报告全文共20页，当前为第15页。 cout<<stack[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) cout<<stack[top--]->data<<""; else i=0; } else i=0; }数据结构二叉树的递归算法实验报告全文共20页，当前为第16页。 else数据结构二叉树的递归算法实验报告全文共20页，当前为第16页。 i=0; } } if(top!=0) p=stack[top]->rTree; else p=NULL; } }}intDepthTree(Tree*tree)//深度函数{intu,v;if(tree==NULL)return0;u=DepthTree(tree->lTree);v=DepthTree(tree->rTree);if(u>v)数据结构二叉树的递归算法实验报告全文共20页，当前为第17页。 return(u+1);数据结构二叉树的递归算法实验报告全文共20页，当前为第17页。return(v+1);}intLeafsTree(Tree*tree)//子叶个数函数{intnum1,num2;if(tree==NULL)return0;elseif(tree->lTree==NULL&&tree->rTree==NULL)return1;else{num1=LeafsTree(tree->lTree);num2=LeafsTree(tree->rTr