2023年数据结构实验报告二叉树的实现与遍历.pdf

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

1、 数据结构第六次实验报告学生姓名学生班级学生学号指导老师一、实验内容1）采用二叉树链表作为存储结构，完毕二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。2）输出树的深度，最大元，最小元。二、需求分析遍历二叉树一方面有三种方法，即先序遍历，中序遍历和后序遍历。递归方法比较简朴，一方面获得结点指针假如指针不为空，且有左子，从左子递归到下一层，假如没有左子，从右子递归到下一层，假如指针为空，则结束一层递归调用。直到递归所有结束。下面重点来讲述非递归方法：一方面介绍先序遍历：先 序 遍 历 的 顺 序 是 根 左 右，也就是说先访问根结点然后访问其左子再然后访问其右子。

2、具体算法实现如下：假如结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子,假如结点的指针为空，表达左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。再次介绍中序遍历：中 序 遍 历 的 顺 序 是 左 根 右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下:假如结点指针不为空，结点入栈，指针指向其左子，假如指针为空，表达左子树访问完毕，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循环直至结点指针和栈均为空，遍历结束。最后介绍后序遍历：后序遍历的顺

3、序是左右 根，后序遍历是比较难的一种，一方面需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是一方面访问根结点,假如结点的指针不为空，根结点入栈，与之相应的标志位也随之入标志位栈，并赋值0,表达该结点的右子还没有访问，指针指向该结点的左子，假如结点指针为空，表达左子访问完毕，父结点出栈，与之相应的标志位也随之出栈，假如相应的标志位值为0,表达右子树还没有访问，指针指向其右子,父结点再次入栈，与之相应的标志位也入栈，但要给标志位赋值为1,表达右子访问过。假如相应的标志位值为1,表达右子树已经访问完毕，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空,遍

4、历结束。三、具体设计源代码：#include#de f in e MAX 100/表达栈的最大容量#de fine FULL 9 9/表达栈满#defin e EMPTY-1 表达栈空t y p e de f s t r uct Tn ode 定义结点（char d a ta;/存储结点数据st r u c tTnod e*left;/定义结点左子指针str u c t T n o de*r i gh t；/定义右子指针）Tno d c,*Pnode;声明T n ode类型的变量和指针typed e f st r u ct S t ack/定义栈P n od e pno d eM AX;存放数

5、据。i nt p;栈顶指针Stack,*P s ta c k;/定 义 Sta c k 类型的变量和指针vo i d Push(Pst a ck p stack P node pnodc)/入栈p s t ack-p+;pstac k-pno d epsta c k-p=pn o de;/赋值)Pnode P o p(P st a ck pst a ck)/出栈(re t urn p s ta c kp n ode p s t ack-p-；1Pnod e T o p(P sta c k p s tac k)看 栈顶元素(retur n p s t a c k pn o d e p s t a

6、 c k-p;int Isem p ty(Pstac k p s ta c k)/栈判空(if(p s tac k p=EMPTY)r etum 1 ；oel s e r e t u rn 0;)i nt Is f ull(P sta c k psta c k)栈满(o i f(p s ta c k-p=FULL)return 1 ;elsere t u r n 0;vo i d Init s tack(Ps t ack psta c k)初始化栈op stack-p=E M PTY:)v oid Ini t t n od e(Pn o d e root,Pnode le f t,Pnode

7、r i ght,ch a r data)/初始化结点(ro o t left=1 ef t;r o o t r ight=r i ght;ro o t-d ata=da I a;)void PreorderR(Pnode p r o o t)递归先序遍历算法(i f(pr o o t)(。叩 r intf(%2c,pr o o t-da t a);P r e o r de r R(pro o t-left);Preor d erR(proot-right);)v o i d In o rdcrR(Pnodc p r oot)递归中序遍历算法(if(pro o t)o。InorderR(p r

8、oo t-le f t);pr i n t f(%2cH,p r oot-d a t a);I nor d erR(proot-r i g h t)；)v o id Po s tord e rR(P node pro o t)/递归后序遍历算法(i f(proot)(o Pos t orderR(proot-1 e ft);8Pos t or d e r R(p roo t rig h t);p rintf(%2c,p ro o t d a t a);。)v o id P r eo r d e rI(Pnode p r o ot,P s t ack p s tack)/非递归先序遍历算法(I

9、ni t stack(pstack);/初始化栈wh i Ie(p root|!I s e mp t y(ps t ac k)假如栈空并且结点指针空，则结束循环(。i f(p r oot)00。叩ri n tf(%2c,p ro o t-d a t a)；。i f(Isful 1 (p s t a c k)/假如栈满不能执行入栈操作8(。printf(栈满，不能执行入栈操作!！”)；r eturn；O d O IPush(psta c k,p r oot);/入栈。叩ro o t=p r oo t 1 eft;/指针指向左子09els e 6if(1 sempty(pstack)栈空时不能出栈

10、(-p ri ntf(栈空，不能执行出栈操但！”)；。r e t urn；00 I。ap r oot=P o p(ps ta c k);/执行出栈操作。叩roo t二p r ool r ig h i;/指针指向右子0)v o id I n o rd e r I(Pno d e proot,P s lack pstack)非递归中序遍历算法(Ini t stack(pstack);/初始化栈wh i le(pro o t I|!Isempty(pstack)/循环结束条件(Mf(p ro o t)od|。对 f(Isf u 1 1 (ps t ac k)6 o|。“pri nt f(栈满，不能执

11、行入栈操作！)；aoorct u rn;Odd Push(p s tack,proot);/执行入栈操作。proo t=pr o ot-1 e f t;/指针指向左子。else 。时 f(Is e mp t y(pst a ck)。(。pr i n t f(栈空，不能执行出栈操作！!*,)；g r etu r n;0)。pr o o t=Pop(p s lack);出栈。叩r i ntf(%2c,p r oot-da t a);/打印数据p r oot=p ro o t-ri g hl;指针指向右子。)voi d P o stor d erI(Pno d e proot,Pstack p st

12、 a ck)/非递归后续遍历算法(i n t fla gs M A X；定义标志位栈in t p=-1 ;/初始化标志位栈。i nt flag;/存放标志位 Ini t s tack(p s t ack);初 女 台化栈 w h ile(proot|!Is e m p t y(p sta c k)循环结束条件。i f(pr o ot)i f(Is f ull(pstack)0。printf(栈 满，不能执行入栈操作!)；。retur n;6)。fl a gs+p=0;/标志位置0,并入栈P u sh(pst a ck,p root)；/结点入栈。p ro o t=proot-le f t;指针

13、指向左子)e 1 seproo t=Pop(pst a c k)：指针出栈。f 1 ag=flag s p-;/相应标志位出栈i f(fla g=0)假如标志位为0 表达右子尚未访问过00。口 a g=1;将标志位置1 ,右子己访问f la g s(+p=f la g ;标志位入栈。Push(p s t a ck,p r oot);/结点入栈M 叩 o ot=proot-right；/指针指向右子0)。else0。printf(H%2 c,p r oo t d a ta);打印数据皿pro oi=N U L L；/将结点指针置空)0)void m a i n ()T n o d e A,B,C

14、,D,E,F,G；声明结点变量 S t a c k s t a c k：/声明栈 I n i 1 1 n o d e(&A,&B,&C,A);/初始化结点I n i t t n o d e(&B,N ULL,&D/B);o I n i t t n o d e(&C,&E,&F/C);4 n i t t n o d e(&D,N U L L ,N UL L；D);I n i t t n o d e(&E,N U L L,N U L L,E);“n i t m o d e (&F,&G,N U L L；F *);I n i t t n(x l e(&G,N ULL,N ULL,G*);叩r i n

15、 t f (你定义的树的结构是:n”)；/*一下是调用相应的函数输出遍历结果*/p r i n t f (MA(B(D)C (E F (G)n”)；p r i n t f (=下面是遍历结果=、n )；叩 r i n l f(=递归先序遍历：=nu);o P r c o r d e r R(&A);o p r i n t f(n”)；p r i n t f(=非递归先序遍历：=n )；o P r e o r d e r I (&A ,&s t a c k);p r i n t f(u n )；p r i =-=二I弟1rJJj；=n I n o r d e r R (&A);p r i n t

16、 f(nM);o p r i n t f(=非递归中序遍历：=n);In o rdcr I(&A,&s t ack);pri n tf(n )；p r i n tf(n=递归后序遍历:=n );Posto r d erR(&A)：pr i n tf (nH);pr i n tf(u=非递归后序遍历：=n)；P o st o r d erI(&A,&s tack);p r i n t f(n);)五、碰到的问题及解决办法这部分我重要碰到如下两个问题，其内容和解决方法如下所列：执行程序时程序停止运营，其效果如图：解决方法：看到程序停止运营，推测也许的因素：碰到死循环、参数设立不合理或者结构体没有造

17、好。一方面对结构体进行了检查，各个成员声明正常无误，在对程序进行调试,程序正常跳出循环，因此最也许是自定义函数的参数设立的不合理，因此对调用的自定义函数进行相应的改动，将参数由具体类型改为指针类型后，程序正常运营。程序不断的输出同一个结点的数据，其效果入图:06C:UsersWFLDesktopsomethingS蝎结孙二叉网的遍历二叉词的遍历Debugmyprogra.1胆pDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD-DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD

18、DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDfcDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD

19、DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD

20、DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDPDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD

21、DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDPDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD

22、DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD解决方法:分析运营结果可知,第一不断的输出证明碰到了死循环，第二输出的是同一个结点的数据,表达指针没有按预期进行指向，一方面对程序进行调试,发现程序没有添加循环结束条件，添加循环

23、结束条件后，只能输出树的部分结点的数据，对标志位进行修改后，程序运营正常,也能对的输出遍历结果。六、心得体会通过这次作业真的受益匪浅，感触良多：，一方面，要提高编程能力，必须多动手，多实践，而不是仅仅局限在书本上，更不能眼高手低。眼高手低，懒得动手,这就犯了编程人员的大忌。大一我们开始接触C 语言，这是我们接触到的第i种编程语言，但是当时徒有对编程的爱好，却没有付诸行动，动手少，结果考试险过，通过这次作业，我再次看了 C语言课本，边看边写代码，理解快，印象深刻，思维也活跃许多，状态也好,真正的意识到，编程能力需要靠实践来提高。当自己写出意想的程序后，真的有些成就感。再 者，在吴老师的指导和规定

24、下，我们改掉了很多的编程坏习惯的同时也养成了良好的编程习惯，另一方面我们态度端正了很多，认真完毕好每一项任务，这样无形中提高了对自己的规定，同时也增强了我们的动手能力和编程能力。七、附录运营结果截图。.，C:UsersWFLDesktopsomethingS唬 细 班 叉 舶 州 二 叉 闵 皎 SDebugmyprogra.I I 回 IB辂你定义的树的结构是,IA(B(D)C(E F(G)3=下面是遍历结果=递归先序遍历:=A B D C E F G=非递归先序遍历，=A B D C E F G=递归中序遍历：=B D A E C G F=非递归中序遍历，=B D A E C G F=递归后序遍历：=D B E G F C A二二二=二=二=三 E 递归后序遍历=D B E G F C APress any key to continue