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

齐鲁工业大学实验报告成绩课程名称数据结构指导教师单健芳实验日期院（系）信息学院专业班级计科（嵌入）14-1实验地点学生姓名高晨悦学号同组人无实验项目名称二义树的递归算法一、实验目的和规定.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。.求二叉树的结点个数，叶子结点个数，二叉树的高度,度为2的结点个数。二、实验环境微型计算机vc6.0三、实验内容.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。四、实验环节实验内容.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。二.程序的设计思想1实现二叉树的先序,中序与后序遍历的递归算法与非递归算法。先构造二叉树，根据先序遍历的思想，输入根后，再输入左子树，直至左子树为空则输入上一层右字树。if(tree;二NULL)。。cout<<tree->data«"";oootop++;oS[top]=tree;tree=tree->ITree;00)eIsedo{。otree=S[top];°top-;。tree=tree—>rTree;00)3})voidInTraverse(Tree*tree)//中序遍历递归if(tree!=NULL)。。if(tree->ITree!=NULL)。InTraverse(tree->ITree)；。ocout<<tree->data<<"";。InTraverse(tree->rTree);。)o。eIseif(tree->rTree!=NULL)。(。。cout<<tree—>data<<""；InTraverse(tree->rTree);O0}eIseo。cout<<tree->data«"";)}voidInOrderTraverse(Tree*tree)//中序遍历非递归(。Tree*D[80]={NULL};ointtop=0;owhile((tree!=NULL)||(top))(tree!二NULL)top++；D[top]=tree;tree=tree->ITree;3»tree=D[top];O6Otop；cout«tree->data«"tree=tree—>rTree；voidPostTraverse(Tree*tree)//后序遍历递归if(tree!=NULL)if(tree->ITree!=NULL)。PostTraverse(tree->lTree);PostTraverse(tree->rTree)；。cout«tree->data«""；)«>oelseif(tree—>rTree!=NULL)。(。。PostTraverse(tree->rTree);。cout<<tree->data<<"";。1eIse。。cout«tree->data<<"；1)voidLastOrderTraverse(Tree*tree)〃后序遍历非递归(3Tree*stack[Maxsize]:{NULL},*p；°p=tree；inttop=0Ftag=1,i=0,k=0;whiIe(p!=NULLI|top)(i=1；。whiIe(p!=NULL)。。stack[++top]=p;。。p=p->ITree；。1if(top!=0)。p=stack[top]—>rTree;。if(p==NULL)(。cout<<stack[top—]—>data«"";。sif(stack[top]!=NULL)O0{whiIe(i)。{。if(stack[top]!=NULL)。{。。。if(stack[top]->rTree!=NULL)Od0d{。if(stack[top]->rTree—>data-stack[top+1]—>data)cout«stack[top—]—>data«。oi=0；00。}。。®eIset>aodj=0；ooo}oooeIse。。。oi二0；,0}00)。if(top!=0)。op=stack[top]->rTree；eIseop=NULL;,0}1//深度函数//深度函数//深度函数intDepthTree(Tree*tree)//深度函数intu,v;if(tree==NULL)return0;u=DepthTree(tree->ITree);v=DepthTree(tree->rTree);if(u>v)return(u+1)；return(v+1);)intLeafsTree(Tree*tree)//子叶个数函数{intnum1,num2;if(tree==NULL)return0;elseif(tree->ITree==NULL&&tree->rTree-NULL)return1；eIse(num1=LeafsTree(tree->ITree);num2=LeafsTree(tree->rTree)；return(nurn1+num2);intNodesTree(Tree*tree)//结点个数函数intnum1,num2;if(tree==NULL)return0;if(tree->ITree==NULL&&tree—>rTree==NULL)return1；else(num1=NodesTree(tree->ITree);num2=NodesTree(tree->rTree);return(num1+num2+1);]IintTwochiId(Tree*tree)〃度为2的(intn=0;if(tree二二NULL)return(0)；if(tree->ITree!=NULL&&tree->rTree!=NULL)

return(TwochiId(tree->ITree)+TwochiId(tree->rTree)+n);)■，F:■，F:杨婷结构\Tree\Debug\Tree.exe"■，F:杨婷结构\Tree\Debug\Tree.exe"00有没有没有有有没没没有有有没没没有有有没没没有有FcC没没cfs、、9af000000—XISX••00000dsb■，F:杨婷结构\Tree\Debug\Tree.exe"00有没有没有有有没没没有有有没没没有有有没没没有有FcC没没cfs、、9af000000—XISX••00000dsb居s居居居居居bb9项-或成，发现—秋杈初叔叔一发.秘；初addW遍干干豆干^子子机机机4Zi：W)：0：：Ih?1«ll1«W)«0ItW)t0L有)：1))u

wwf«0:0历三历二历三=递归:abdgc三递归:dbgaf三递归:dgbfs通过这次实验使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来,从理论中得出结论,才干真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。(1)二叉树的非递归遍历是用显示栈来存储二叉树的结点指针,先序遍历时，按二叉树前序遍历的顺序访问结点，并将结点的指针入栈，直到栈顶指针指向结点的左指针域为空时取出栈顶指针并删除栈顶指针，访问刚取出的指针指向的结点的右指针指向的结点并将其指针入栈，如此反复执行则为非递归操作。(2)二叉树的递归遍历：若二叉树为空,则空操作先序遍历：(a)访问根结点；(b)先序遍历左子树；(c)先序遍历右子树。中序遍历：(a)中序遍历左子树；(b)访问根结点；(c)中序遍历右子树后序遍历：(a)后序遍历左子树；(b)后序遍历右子树；(c)访问根结点。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。(1)求二叉树的叶子结点个数：先分别求得左右子树中个叶子结点的个数，再计算出两者之和即为二叉树的叶子结点数。(2)二叉树的结点个数之和:先分别求得左子树右子树中结点之和,再计算两者之和即为所求。(3)二叉树的高度：一方面判断二叉树是否为空，若为空则此二叉树高度为0,。否则，就先分别求出左右子树的深度进行比较，取较大的树加一即为所求。(4)二叉树的度为2的结点个数：计算有左右孩子的结点个数,即为度为2的结点个数。三.编程过程中碰到的问题及解决办法(D后续遍历的非递归函数涉及到回溯的方法，开始设计的方案想的太过于简朴，所以形成了死循环,总是在最后的节点处不断地循环,后改成回溯后,该问题得到解决。(2)计算二叉树中度为2的结点个数中，返回循环的时候不管根结点有没有左右子树，但个人设计时，根总是会将自己默认为有左右子树，自行增长1.后在同学帮助下才看到自己的这个失误。四,程序的闪光点(自我评价).程序模块化,各个函数分开描述，方便观测.关键处有注释.建立二叉树时,用先序提醒输入,比较人性化。五.程序源代码(以文献为单位提供)incIude<iostream.h>incIude<maIIoc.h>defineMaxsize100typedefstructTREE{ostructTREE*ITree;。structTREE*rTree；。chardata;voidInitTree(Tree*);//初始化树voidCreatTree(Tree*);//创建二叉树voidPreTraverse(Tree*);//先序遍历递归voidPreOrderTraverse(Tree*)；//先序遍历非递归voidInTraverse(Tree*tree);//中序遍历递归voidInOrderTraverse(Tree*tree);//中序遍历非递归voidPostTraverse(Tree*tree);//后序遍历递归voidLast0rderTraverse(Tree*tree);〃后序遍历非递归intDepthTree(Tree*tree);〃计算树的深度intLeafsTree(Tree*tree);〃计算叶子结点个数intNodesTree(Tree*tree);//计算结点个数intTwochild(Tree*tree);〃计算度为二的结点个数voidmain(){3intH,L;Treetree;//®Treem;3InitTree(&tree);CreatTree(&tree);cout＜〈”先序遍历递归为：”;3PreTravevse(&tree);//先序遍历递归。cout<<”先序遍历非递归：“；。PreOrderTraverse(&tree)；//先序遍历非递归。cout«endI;coutVV”中序遍历递归为：”；nTraverse(&tree);//中序遍历递归coutV<”中序遍历非递归：”;°InOrderTraverse(&tree);〃中序遍历非递归cout«endI；。coutVV”后序遍历递归为：”；。PostTraverse(&tree)；〃后序遍历递归cout<<”后序遍历非递归：”;。LastOrderTraverse(&tree);〃后序遍历非递归。cout<<endI;cout«”树的深度为：”；H=DepthTree(&tree)；cout«H«endI;cout<<"叶子结点个数：”；L二LeafsTree(&tree);cout<<L<<endI;cout<<”结点个数:";3cout<<NodesTree(&tree)«endI；cout<<”度为二的结点个数”；L=TwochiId(&tree)；cout<<L«endI;)voidInitTree(Tree*tree)//初始化树(。tree->ITree=NULL;tree->rTree=NULL;otree->data='0';1voidCreatTree(Tree*tree)//创建树(intn=0,m=0,i=0;if(tree->data=='0')。(…coUt<〈”请输入该节点的数据：cin>>tree->data;。(：。1^<<“节点”<<上y6-“21④〈<”是否有左子树(0：没有1：有)：cin>>n;。if(n==1)00{o。Tree*ITree=(Tree*)maIloc(sizeof(Tree));tree->ITree=ITree;o。ITree—>ITree=NULL；。。ITree->rTree=NULL;。ITree->data=O'；。。oCreatTree(tree->ITree);。。cout<V"节点“<<tree->data<<“是否有右子树(0:没有1:有)：。cin»i;。。if(i二二0);eIseif(i==1)O0{033Tree・rTree=(Tree*)maIIoc(sizeof(Tree));。。ootree->rTree=rTree;。。rTree->ITree=NULL;o。o。rTree->rTree=NULL;。。rTree->data='0';。CreatTree(tree->rTree);oo))®oelsei