《2023年数据结构二叉树的递归算法实验报告.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构二叉树的递归算法实验报告.pdf（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、齐鲁工业大学实验报告 成 绩课程名称 数据结构 指导教师 单健芳 实验日期院（系）信息学院 专业班级 计 科（嵌入）1 4-1 实验地点学生姓名 高晨悦 学号 同组人 _ _ _ _ _ _ _ 无实验项目名称 二叉树的递归算法一、实验目的和规定1 ,实现二叉树的先序,中序与后序遍历的递归算法与非递归算法。2.求二叉树的结点个数，叶子结点个数，二叉树的高度,度为2的结点个数。二、实验环境微型计算机vc 6.0三、实验内容1 ,实现二叉树的先序,中序与后序遍历的递归算法与非递归算法。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度 为 2 的结点个数。四、实验环节实睑内容1.实现二叉树的先
2、序,中序与后序遍历的递归算法与非递归算法。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度 为 2 的结点个数。程序的设计思想1 实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。先构造二叉树，根据先序遍历的思想，输入根后，再输入左子树，直至左子树为空则输入上一层右字树。(1)二叉树的非递归遍历是用显示栈来存储二叉树的结点指针,先序遍历时，按二叉树前序遍历的顺序访问结点，并将结点的指针入栈，直到栈顶指针指向结点的左指针域为空时取出栈顶指针并删除栈顶指针，访问刚取出的指针指向的结点的右指针指向的结点并将其指针入栈，如此反复执行则为非递归操作。(2)二叉树的递归遍历：若二叉树为空，则空
3、操作先序遍历：(a)访问根结点；(b)先序遍历左子树；(c)先序遍历右子树。中序遍历：(a)中序遍历左子树；(b)访问根结点；(c)中序遍历右子树后序遍历：(a)后序遍历左子树；(b)后序遍历右子树；(c)访问根结点。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。(1)求二叉树的叶子结点个数：先分别求得左右子树中个叶子结点的个数，再计算出两者之和即为二叉树的叶子结点数。(2)二叉树的结点个数之和：先分别求得左子树右子树中结点之和,再计算两者之和即为所求。(3)二叉树的高度：一方面判断二叉树是否为空，若为空则此二叉树高度为0,。否则，就先分别求出左右子树的深度进行比较，取
4、较大的树加一即为所求。(4)二叉树的度为2的结点个数：计算有左右孩子的结点个数，即为度为2的结点个数。三.编程过程中碰到的问题及解决办法(1)后续遍历的非递归函数涉及到回溯的方法，开始设计的方案想的太过于简朴，所以形成了死循环,总是在最后的节点处不断地循环,后改成回溯后,该问题得到解决。(2 )计算二叉树中度为2的结点个数中，返回循环的时候不管根结点有没有左右子树，但个人设计时，根总是会将自己默认为有左右子树，自行增长1 .后在同学帮助下才看到自己的这个失误。四.程序的闪光点(自我评价)1 .程序模块化,各个函数分开描述，方便观测2.关键处有注释3 .建立二叉树时,用先序提醒输入,比较人性化。
5、五.程序源代码(以文献为单位提供)#i nc I u d e#i n c I ud e#d e f i n e M a x s i z e 1 0 0t y pe d e f stru c t T R E E。stru c t TR E E*I Tre e ;。str uc t TREE*rTre e；。c h a r d a t a;T re e ;v oi d I ni t T r e e (T r e e*);/初始化树v o i d C r e a tT r e e (T r e e*);/创建二叉树v o i d P r e T ra v e rse (Tre e*);/先序遍历递归
6、v oi d P re O rd e r T ra v e rse (Tre e*)；/先序遍历非递归v o i d I nTra v e rse (Tre e *t r e e);中序遍历递归v o i d I n O rd e rT r a v e r s e (Tre e *t r e e)；/中序遍历非递归v oi d P ost T ra v e rse (Tr e e *tre e);/后序遍历递归v oi d L a s t 0 r d e rTra v e rse(T r e e *tre e)；后序遍历非递归i nt D e pth T re e (T r e e *t r
7、e e);计算树的深度i nt L e a f s Tre e (Tre e *tre e);计算叶子结点个数i nt N o d e s Tre e (Tre e *t re e );/计算结点个数i nt Two c h i I d (T r e e*tre e);计算度为二的结点个数v oi d m a i n()(。i n t H ,L;Tr e e tre e;。Tre e m;e I ni t T r e e (&t r e e);C r e a t T r e e (&tre e );c o u t”先序遍历递归为：”；b P reTr a ve r s e(&tree);先序遍
8、历递归匕c o u t 先序遍历非递归:;。PreOr d e r Trave r se(&t ree)；/先序遍历非递归。coutend I;c o u t V V”中序遍历递归为：“；I nTravers e(&t r ee);/中序遍历递归coutV”中序遍历非递归：”；。InO r de r Traverse(&tr e e)；中序遍历非递归cout e n d I；o c o u tV V”后序遍历递归为：”；o Po st T r a v e r s e (&tre e)；后序遍历递归cout”后序遍历非递归：”;。La s tO r d erT r averse(&tr e e)
9、；后序遍历非递归。cout e n d I;c o u t “树的深度为：”；H=DepthTree(&tree)；c ou t H e n d I;cout“叶子结点个数：”;L二Le a fsTree(&tre e);c o u t L end I;cou t”结点个数:；b coutNodesT r ee(&t ree)e n d I；cout”度为二的结点个数”；L二T wochi Id(&tr e e)；c o u t I T r e e=NULL;tre e-rT r ee=NU LL;。t r e e-d a ta=0 1;)voi d Cre a t T r e e(T ree
10、*t r ee)/创建树(i nt n=0,m=0,i=0;i f(tre e-d a ta =O)0 co 请输入该节点的数据：”；c i n t r e eda t a;0（：。111：“节点”5 6 6-2 3 n;。if (n=1)。Tre e*IT r e e=(T re e*)ma I loc(sizeof(T re e);t ree-ITree=ITree;I Tree I T r e e=NDLL；。I T ree-rTree=NULL;ITree-d ata=,O；。o CreatT r ee(t r ee-I T ree);0co u t V“节点d a ta rT r e
11、 e二rT r e e;o rT r e e-ITree二 N ULL;r T ree-rT r e e =NUL L;00rTree一 data=0;o C rea t T re e(tree-r T ree)0 0)o e ls e if (n 0 )(。co u t V节点 d a t a 是否有右子树(0：没 有1 :有)：”;b cinm；。if (m二 二0);e。e I se i f (m=1)0 0 3。o o Tre e*r T re e-(T r ee*)ma I I oc(s i z e of(T r e e);。3 tree-r Tree=rTree;。rTre e I
12、 T r ee二NUL L;o。o rTree r Tr e e=NULL；or T r e e-d a ta=0,;。o C r eatTr e e(t r e e-r Tre e);0 0)vo i d P re T r av e rse(Tree*tree)/先序遍历递归if (t ree!=NU L L)1c o u t t r e e-dat a I T r e e!=NULL)0。P r e T r a v e r s e (t r e e-I T re e);。Pr e T r ave r s e(tre e-rT r e e);00)else i f (t ree-r Tr e
13、 e!=NU L L)e b 3 PreT r averse(t r ee-r T re e)；0)。else;0)void PreO rd e rTra v e r s e(T r e e*t r e e)/先序遍历非递归(。Tree*S80=NULL;i n t to p =0;wh i Ie(tre e!二NULL)|(top)i f (tre e!=N UL L)。o c o u t d a ta”;。t o p+;。S t o p =tre e;tre e =t r e e-I Tre e;e I se (36 te e 二 S to p ;b tO p；。tre e =tr e e
14、 r Tre e ;00)0)1v o i d I nTra v e rs e (T r e e *tre e)/中序遍历递归i f (t re e !=N UL L)，o i f (tre e-I Tr e e!=N UL L)I n T ra v e r se (t r e e-I T r e e)；。c o ut d a t a r Tre e);0。o e I se i f (tre e-rTre e!=N UL L)。(o。c o u t d a ta r Tr e e );O 0 e I se。c o u t d a t an;)v oi d I n O rd e rTra v e
15、 r s e (T re e *t r e e )中序遍历非递归(o Tre e *D 8 0 =N UL L);。i n t top=0;。wh i l e (tre e!=N UL L)|(top)i f (t r e e!=NULL)t o p+；。D to p=tree;t r e e =tree-IT ree;0。e I se。o t r e e =D t o p ;0 0 0 t o P-；e。c o u t tr e e-d a ta n；t r e e =tre e rTree；0 0 0)vo i d Pos t T r avers e(Tre e*tree)/后序遍历递归(
16、i 千(tre e!二N U LL)i f (t ree I Tree!=N ULL)。P os t Tra v e rse(tre e-l T re e);P ostTr a v e rse (t re e-rTre e)；c o u ttr e e -d a taH”；)。e l s e i f (tre e r T r e e!二 N UL L)0。P ost T r a v e r se (t r e e-rTre e);。c ou t d a t a d a ta IT r e e；)i f(to p!=0)p=s t ack to p r Tr e e;if (p=NULL)c o
17、 u t d a ta nif (s tack to p !=NULL)(whi Ie(i)3 (凸 i f (sta c k t o p !=NULL)。(。e i f(s t a c k t o p _ rT r e e!=NULL)o d o (e if (s ta c k to p-r Tr e e da t a二二stack top+1 data)。oo co u t s t a ckt o p d a ta ;e l s eo i-0；OOO 0 )b b b a e I se0 0 0 0 。i=0；0 0 0 。o o e I s e0 6 0 0 0 i 0；0 0 0 0
18、。i f (t o p!=0)匕 匕 o p=stack t o p-rT ree；3匕b e I seo p=NULL;0 0 )i n t Dep t h Tre e(Tre e*t ree)(in t u,v;if (t r e e =N U LL)return 0;/深度函数u=DepthT r e e (tree-1 T r e e);v =D e pth T r e e (tre e-rTre e);i f (u v)r e t u r n (u+1)；re t urn(v+1);)i nt L e a f sTre e(Tre e *t r e e)/子叶个数函数(i nt n
19、um1,num2;i f (tre e=N UL L)r e t urn 0 ;e l se i f (t r e e-I Tre e =N UL L&t r e e-rTre e-N UL L)re turn 1 ；e I se(num1 =L e a f s T re e (tre e -I Tr e e);num 2 =L e a f sTre e (t r e e-rTre e)；re t u rn(n um 1 +n um 2);i n t N od e sT r e e (T re e *tre e)/结点个数函数i n t num 1 ,n u m2;i f (t r e e =
20、N U L L)re turn 0;i f (tr e e-I Tre e =N U L L&t r e e r T re e=N U L L)re turn 1；e l s e|n u m 1=N o d e s T re e (tre e-I T r e e);num 2=N o d e s T r e e(t r e e -rT re e);re turn(num 1 +n u m 2+1 );i nt T woc h i I d (T re e *t r e e)度为 2 的(i nt n=0;i f (tre e二 二N UL L)r e tu r n(0)；i f (t r e e
21、-I Tre e!=N UL L&tre e-rTr e e !=N UL L)n=1 ;re tur n(T wo c h i I d (t r e e-I Tre e)+Tw o c h i l d(t r e e-r T r e e)+n);*reeDebugT ree.exebbgadd333dyd/d/6r5r a-6n_三_ _L/二1001001100100.历历历扁扁直X7S1/S1/7XJZ有有有有有有有有有有有有有:.先中后1111111111111ssa有有有没没没有有有没没没有有有没没没有有fC没没Cg.000F:s000000dgb居居居居居bb9左孽右右蓼右右上防防有限,有有有有有有InrflnrlnplnpunFlnr，不恭否否不攀呆呆日 1点否否正位否否专bA-ddbxggaxKI T道I T节节请节节节道I T道I-P节节通K犬中有没有没00004第5噜21五、讨论、心得通过这次实验使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来,从理论中得出结论,才干真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。