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

《2023年数据结构二叉树的递归算法实验报告.docx》由会员分享，可在线阅读，更多相关《2023年数据结构二叉树的递归算法实验报告.docx（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、齐鲁工业大学实验报告成绩课程名称数据结构指导教师单健芳 实验日期院（系）信息学院专业班级 计科（嵌入）14-1实验地点学生姓名高晨悦 学号 同组人 无实验项目名称二义树的递归算法一、实验目的和规定.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。1 .求二叉树的结点个数，叶子结点个数，二叉树的高度,度为2的结点个数。二、实验环境微型计算机vc 6. 0三、实验内容.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。1 .求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。 四、实验环节实验内容1 .实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。2 .求二叉

2、树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。二.程序的设计思想1实现二叉树的先序,中序与后序遍历的递归算法与非递归算法。先构造二叉树，根据先序遍历的思想，输入根后，再输入左子树，直至左子树为空则输 入上一层右字树。i f (tree;二NULL)。co u t 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)

3、 /中序遍历递归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 dat a r Tree);。)o。eIse i f (tree-rTree!=NULL)。(。co u tdata r Tr e e );O 0e I seo。 co u tda 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!

4、 =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 outtr e e-d a ta tree = treerTree；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 ttr e e - d

5、ata；) o else i f (tree r T r e e!=NUL L)。(。Post T rave r se (t r ee-rTree);。 cou t dat a d a taITr e e；。1i f (to p ! =0)。 p =s t ack top r Tr e e;。if(p=NULL)(。 c o u tdata;。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 T

6、r 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 =

7、DepthT r ee (tree-rTree);i f (uv)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 (

8、 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

9、) 度为 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.exe00有 没有 没有有有 没没没有有有 没没没有有有 没没没有有F c C 没没cfs 、9 a f0 0 0 0 0 0 XIS X 000 0 0 d

10、sb居s居 居 居 居 居 b b 9 项-或成，发现秋杈初叔叔一发.秘；初 add W 遍干干豆干子子机机机4 Zi： W) ： 0：Ih ?1ll1 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)二叉树的非递归遍历是用显示栈来存储二叉树的结点指针,先序遍历时，按二

11、叉 树前序遍历的顺序访问结点，并将结点的指针入栈，直到栈顶指针指向结点的左指针域为 空时取出栈顶指针并删除栈顶指针，访问刚取出的指针指向的结点的右指针指向的结点并 将其指针入栈，如此反复执行则为非递归操作。(2)二叉树的递归遍历：若二叉树为空,则空操作先序遍历：(a)访问根结点；(b)先序遍历左子树；(c)先序遍历右子树。中序遍历：(a)中序遍历左子树；(b)访问根结点；(c)中序遍历右子树后序遍历：(a)后序遍历左子树；(b)后序遍历右子树；(c)访问根结点。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。(1)求二叉树的叶子结点个数：先分别求得左右子树中个叶子结点的个

12、数，再计算出 两者之和即为二叉树的叶子结点数。(2)二叉树的结点个数之和:先分别求得左子树右子树中结点之和,再计算两者之和即为所求。(3)二叉树的高度：一方面判断二叉树是否为空，若为空则此二叉树高度为0,。否 则，就先分别求出左右子树的深度进行比较，取较大的树加一即为所求。(4)二叉树的度为2的结点个数：计算有左右孩子的结点个数,即为度为2的结点个数。三.编程过程中碰到的问题及解决办法(D后续遍历的非递归函数涉及到回溯的方法，开始设计的方案想的太过于简朴，所以形 成了死循环,总是在最后的节点处不断地循环,后改成回溯后,该问题得到解决。(2 )计算二叉树中度为2的结点个数中，返回循环的时候不管根

13、结点有没有左右子树，但 个人设计时，根总是会将自己默认为有左右子树，自行增长1.后在同学帮助下才看到自己 的这个失误。四,程序的闪光点(自我评价)1 .程序模块化,各个函数分开描述，方便观测2 .关键处有注释3 .建立二叉树时,用先序提醒输入,比较人性化。五.程序源代码(以文献为单位提供)i ncIu d e# i n c Iudedef 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

14、(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

15、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

16、r ee (&tre e );cout”先序遍历递归为：”;3 P reTr a ve v s e (&tree) ;/先序遍历递归。cout ”先序遍历非递归：“；。PreOr d e r Trave r se (& t ree) ； / /先序遍历非递归。coutend 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 Traver

17、se (&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 coutNodesT r ee (& t ree) e n d I ；cout ”度为二的结点个数”；L=T wochi Id (&tr e e)；cout I Tre e

18、=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 tr e e-da t a;。(：。1“节点”上y6-“21n;。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 re

19、e=NULL;。 ITree- d ata= O；。o CreatT r ee (t r ee-I Tree);。 coutV节点“d atarT 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)(。coutV节点dat am；。 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

20、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 ttre e -dat a 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)