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

齐鲁工业大学实验报告成绩课程名称数据结构指导教师单健芳 实验日期院（系）信息学院专业班级 计科（嵌入）14-1实验地点学生姓名高晨悦 学号 同组人 无实验项目名称二义树的递归算法一、实验目的和规定.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。1 .求二叉树的结点个数，叶子结点个数，二叉树的高度,度为2的结点个数。二、实验环境微型计算机vc 6. 0三、实验内容.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。1 .求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。 四、实验环节实验内容1 .实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。2 .求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。二.程序的设计思想1实现二叉树的先序,中序与后序遍历的递归算法与非递归算法。先构造二叉树，根据先序遍历的思想，输入根后，再输入左子树，直至左子树为空则输 入上一层右字树。i f (tree;二NULL)。co u t <<t r ee->data« ""ooo top+;o S t o p = tree;tree = t r e e-> I Tree;00)e I sed o 。 o t r ee = S to p ;°top-;。 tre e = tree > r Tre e ;00)3 )vo i d InTra v e rs e (T r e e *tree) /中序遍历递归i f (t re e ! = NULL)。if (tree->ITr ee!=NULL)。 I n T rave r se (t r ee-> IT r e e)；。o c o ut< <tree->dat a <<""。 I nTra v e r s e (tree-> r Tree);。)o。eIse i f (tree->rTree!=NULL)。(。co u t<<t r ee >data<<""；I nT r a v erse (tree-> r Tr e e );O 0e I seo。 co u t<< t ree ->da t a«"")void I n Ord e rTra v er s e (T ree *t r e e )/中序遍历非递归(。Tree *D 80= NULL;o i n t top =0;o while (t r e e! =N U L L) | | (top)(tree!二 NULL)t o p+ ；D top = tree;tree = tree->ITree;3» tree = D top;O 6 O top；c out«tr e e->d a ta« "tree = tree>rTree；vo i d Pos t T r avers e (Tre e *tree) / / 后序遍历递归i f (tree!=NULL )if (t ree->ITree! =NULL)。Pos t Traverse (tree->lT re e);PostTr a verse (t ree->rTree)；。co u t«tr e e -> d ata«""；)«> o else i f (tree > r T r e e!=NUL L)。(。Post T rave r se (t r ee->rTree);。 cou t <<t r e e ->dat a << ""。1e I se。cout«tre e ->d a ta<< "；1)void LastO r derT r ave r s e (Tree * t re e )后序遍历非递归(3 Tre e * stack Ma x s iz e :NULL , *p；° p=tree；i nt t op=0F t a g= 1 , i=0, k = 0;whi I e (p! =NULL I | top)(i =1 ；。wh i Ie (p!=NULL)。s t ack+t o p =p;。p =p->ITr e e；。1i f (to p ! =0)。 p =s t ack top > r Tr e e;。if(p=NULL)(。 c o u t<< s tack top >data«""。s if ( s tack to p ! = NULL )O 0wh iIe (i)。 i f (sta c k t op !=NUL L )。if(stackt op->rTr ee!=NULL)O d 0 d 。 i f (stack top-> r Tr e e >da t a-stack top+1 >data)co u t «s t ack t o p >data«。o i =0；0 0。> 。® e I set> a od j =0 ；> oo o o o o e I s e。o i 二 0 ；,000)。 i f (t o p! =0)> 。 o p =stack t o p->rTree；e I seo p=NULL ;,01/深度函数/深度函数i n t D ep t h Tre e (Tre e * t ree)(int u, v;if (tree =NULL ) return 0;u =DepthT ree (tree ->I Tree);v = DepthT r ee (tree->rTree);i f (u>v)r e t u r n (u+1)；ret urn (v+1);)i nt L eafsTree (Tree *t r e e) /子叶个数函数i nt n um1, num2;if (tree=NULL)ret urn 0 ;else i f (t r ee->ITree=NULL&&t r ee->rTree-NULL)r e t u rn 1 ；e I se(num1 = Leaf s T re e (tre e -> I Tr e e);num 2 = L eafsTree (t r e e->rTree)； ret u rn ( n urn 1 + n um2);i n t Nod e sT r ee ( T ree *tree) / /结点个数函数i n t num 1 , n u m2;if (t r ee =NULL)return 0;i f (tr e e ->ITre e =N ULL&&tre e >r T ree=NU LL)return 1；else(nu m 1 =No d e s T ree (tree->I T r e e);num 2=NodesTree(tree ->rT ree);return (num 1 +num2+ 1 );Ii nt T woch i I d ( T re e *t r ee) 度为 2 的(i nt n=0;i f (tree二二NULL)r e tu r n (0)；i f (t r ee-> I Tree! = N ULL&&tree->rTr e e ! =NULL)retur n (T wo c h i I d (t r ee-> I Tree) +Tw o ch i I d(tree->rTr ee) +n);) ，F:杨婷结构TreeDebugTree.exe" ，F:杨婷结构TreeDebugTree.exe"00有 没有 没有有有 没没没有有有 没没没有有有 没没没有有F c C 没没cfs 、9 a f0 0 0 0 0 0 XIS X 000 0 0 d sb居s居 居 居 居 居 b b 9 项-或成，发现秋杈初叔叔一发.秘；初 add W 遍干干豆干子子机机机4 Zi： W) ： 0：Ih ?1«ll1« W) « 0It W) t 0L 有)：1)uwwf« 0 :0 历三 历二 历三=递归:a b d g c 三递归:d b g a f 三递归:d g b f s五、讨论、心得通过这次实验使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够 的，只有把所学的理论知识与实践相结合起来,从理论中得出结论,才干真正为社会服务， 从而提高自己的实际动手能力和独立思考的能力。(1)二叉树的非递归遍历是用显示栈来存储二叉树的结点指针,先序遍历时，按二叉 树前序遍历的顺序访问结点，并将结点的指针入栈，直到栈顶指针指向结点的左指针域为 空时取出栈顶指针并删除栈顶指针，访问刚取出的指针指向的结点的右指针指向的结点并 将其指针入栈，如此反复执行则为非递归操作。(2)二叉树的递归遍历：若二叉树为空,则空操作先序遍历：(a)访问根结点；(b)先序遍历左子树；(c)先序遍历右子树。中序遍历：(a)中序遍历左子树；(b)访问根结点；(c)中序遍历右子树后序遍历：(a)后序遍历左子树；(b)后序遍历右子树；(c)访问根结点。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。(1)求二叉树的叶子结点个数：先分别求得左右子树中个叶子结点的个数，再计算出 两者之和即为二叉树的叶子结点数。(2)二叉树的结点个数之和:先分别求得左子树右子树中结点之和,再计算两者之和即为所求。(3)二叉树的高度：一方面判断二叉树是否为空，若为空则此二叉树高度为0,。否 则，就先分别求出左右子树的深度进行比较，取较大的树加一即为所求。(4)二叉树的度为2的结点个数：计算有左右孩子的结点个数,即为度为2的结点个数。三.编程过程中碰到的问题及解决办法(D后续遍历的非递归函数涉及到回溯的方法，开始设计的方案想的太过于简朴，所以形 成了死循环,总是在最后的节点处不断地循环,后改成回溯后,该问题得到解决。(2 )计算二叉树中度为2的结点个数中，返回循环的时候不管根结点有没有左右子树，但 个人设计时，根总是会将自己默认为有左右子树，自行增长1.后在同学帮助下才看到自己 的这个失误。四,程序的闪光点(自我评价)1 .程序模块化,各个函数分开描述，方便观测2 .关键处有注释3 .建立二叉树时,用先序提醒输入,比较人性化。五.程序源代码(以文献为单位提供)i ncIu d e<i o s tream. h ># i n c Iude<ma I Ioc. h>def i n e Max size 100t y pe d ef stru c t T R E E o stru c t TR E E * I Tre e ;。 str uct TREE *rTree；。cha r data;void Ini t T r e e (T r e e*) ;/初始化树v o i d Cr e atT r ee (T r ee*) ;/ / 创建二叉树vo i d Pr e T rav e rse (Tree*) ; / / 先序遍历递归void PreO rde r T ra v erse (Tree*) ； /先序遍历非递归void I nTrav e rse (Tree * t r e e) ;/中序遍历递归v o i d I n OrderT r aver s e (Tree *t r ee) ;/中序遍历非递归void Post T rave rse (Tr e e *tree);/ 后序遍历递归void Las t 0 r derTrav e rse (T r ee *tree); 后序遍历非递归i nt Depth T re e (T r ee * t r e e);计算树的深度i nt L e af s Tree (Tree *tree); 计算叶子结点个数i nt N o des Tree (Tree * t re e ) ; / / 计算结点个数int Two chi ld(Tr e e*tree); 计算度为二的结点个数void m a i n ()3 i n t H, L;Tr e e tree;/® Tree m;3 I n i t T r e e (&t r ee);Cr e at T r ee (&tre e );cout”先序遍历递归为：”;3 P reTr a ve v s e (&tree) ;/先序遍历递归。cout<< ”先序遍历非递归：“；。PreOr d e r Trave r se (& t ree) ； / /先序遍历非递归。cout«end I ;cout VV”中序遍历递归为：”；1 nTravers e (&t r ee) ;/ / 中序遍历递归 coutV< ”中序遍历非递归：”;° I nO r de r Traverse (&tr e e ); 中序遍历非递归 cout« e n d I ；。c out VV”后序遍历递归为：”；。Po st Traverse (&tree)； 后序遍历递归 cout<< ”后序遍历非递归：”;。La s tO r d erT r averse (&tr e e); 后序遍历非递归 。cout<< e n d I ;c out« ”树的深度为：”；H=DepthTree(&tree)；c ou t « H «e n d I ;cout<< "叶子结点个数：”；L二Le a fsTree (&tree);c o u t<< L <<end I ;cout<< ”结点个数:"3 cout<<NodesT r ee (& t ree) «e n d I ；cout<< ”度为二的结点个数”；L=T wochi Id (&tr e e)；cout<< L « e n d I ;)voi d I n i tTree (Tree * t r ee) / /初始化树(。tree-> I Tre e=NULL;tree->rT r ee = NU LL;o t r ee->data=' 0 '1voi d Cre a t T r e e (T ree *t r ee)/创建树 (i nt n=0, m= 0, i=0;i f (tree->d a ta = = ' 0 ')。(co U t<”请输入该节点的数据：c i n> >tr e e->da t a;。(：。1<<“节点”<<上y6-“21<”是否有左子树(0：没有1：有)：c in>>n;。if (n=1)00o 。Tre e * IT r e e= (T re e *) ma I loc(sizeof (Tree);t ree->ITree= ITree;o。 I Tree> I T r e e = NULL；。I Tree ->rT ree=NULL;。 ITree-> d ata= O'；。o CreatT r ee (t r ee->I Tree);。 cout<V"节点“<<tree->d ata<<“是否有右子树(0:没有1:有)：。c i n»i ;。 i f (i二二0);eIse if(i = 1 )O 0033 Tree r T ree= (T r ee*) ma I I oc (s i zeo f (Tr e e);。o o tree->rT r e e=rT ree;。rT r ee-> ITree=NULL;o。o 。r T ree->rT ree =NUL L ;。rTree->data=' 0'。C rea t T re e (tree->r T ree);oo)® o else if (n=0)(。cout<V"节点"<<tree >dat a<<"是否有右子树(0 ：没有 1:有)："® cin>>m；。 if (m=0);o。o。eIse if (m= = 1)od®。o o Tre e *r T re e = (T r ee*)ma I Ioc (s i z e of (T r e e );。tree-> r Tree=rTree;。rTre e > I T r ee=NUL L ;。 o rTree> r Tr e e = NULL；。r T r ee-> d a ta= ' O'。 o C r eatTr e e (t r ee-> r Tre e );0 )d 0)vo i d P reT r av e rse(Tree*tree) /先序遍历递归if (t ree!二NU LL)c o u t«tre e ->dat a <<""o。i f (tr e e> I T r e e ! =NULL)。(。P r e T r av e rs e (t r e e-> I T re e );。Pr e T r ave r s e (tree->rT r e e );00)e I se if ( t ree-> r Tr e e! =NU L L)0 0。PreT r averse (t r ee> r Tree)；。)。 else;3 )void PreO rd e rTra v e r s e (T r e e *t r ee)/先序遍历非递归 (。Tree *S80=NULL);i n t top =0;wh i Ie ( (tree!=NULL)| (top)