2023年遍历二叉树递归非递归实验报告.docx

实验报告课程名称数据结构实验名称二叉树的遍历日期2023/05/30学生学号B 1 10502 2 6姓名枯天蝎班级B11050 2实验目的：掌握二叉树的结构特性，掌握用指针类型描述、遍历二叉树的运算。实验条件：电脑一台v C+6.0实验内容与算法思想：内容：P2 13 实习题1建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序、 和后序），打印输出遍历结果。基本规定如下：从键盘接受输入线序序列，以二叉链表作为存储结构，建立二叉树（以先序 来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。规 定采用递归和非递归两种方法实现。算法思想：定义二叉树结构体类型时，也定义了一个顺序栈结构体类型，用以辅助完 毕二叉树的非递归遍历。由键盘输入二叉树先序序列，用扩展线序序列函数接受并创建二叉链表。遍历前先判断二叉树是否为空，若为空，执行空操作；否则依次执行各遍历 函数相应操作。先序遍历算法思想，先访问根节点，然后按先序遍历左子树，再按先序遍历 右子树。中序遍历算法思想，先按中序遍历左子树，再访问根节点，然后按中序访问 右子树。后序遍历算法思想，先按后序遍历左子树，接着按中序遍历右子树，然后访 问根节点。o p r i n tf("%c " ,p->d a t a);q=p；。 p= P op(&s, p );。叩二 NULL;)®els e p=p>rch i 1 d;)void m a i n ()(print f (”先序序列创建二又树n");s cqst a ck s：®s.t o p=- 1 ;bitre e root；ocrc a tcbitrcc(&r o o t );叩rintf("先序遍历序列:n");pre orderl(r o o t, s );pr i ntf ("n ")；printf ("中序遍历序列:n ");i n o r derl( r ool,s);sprint f( " n ")；°pr i n t f("后序遍历序列:n");p o st o r derl(roo t );运营结果:递归算法:非递归算法:ABC.DE先序递归遍历序列：A B C D E G F中序递归遍历序列：B C D E G F A后序递归遍历序列：B C D E G F APress any key to continueABCDE先后遍历序列;ABCDEGF步序遍历序列;CBEGDFA后序遍历序列：CGEFDBAPress any key to continue实验总结（结论或问题分析）:通过实验，加深了对c语言特别是函数调用部分的结识和掌握。没有找到在实验运营结果上明确区分递归算法实现的遍历和非递归算法实 现的遍历的方法。实验成绩任课教师署名张红霞附：源程序：递归算法程序# i n cl u de <std i o.h>#incki d e <stdl i b.h># inc 1 u de <m a Hoc. h ># define maxsize 1 0 0# dcfinc FALSE 0# define T RUE 1t ypcdef s t ruct n ode/二叉树结构体类型定义»cha r data;struct node *lch i Id； s t ru c t no d e *rc h i Id;bitn ode ,*bit r ee；产扩展先序序列创建二叉链表* /v o id cte a te b itree( b it r ee *bt)(char ch;ch=getcha r ();“f (ch= )*bt=NULL;elseU*bt=(b i t ree)malloc(sizeof (bitnode);<«(*b t )->dat a =c h ；oc t eat e bi t re e (&( ( * bl) ->lchild);。 ct e a t e b i t r ee (& (*bt)>rc h i I d );/*先序递归遍历*/void pre o r der(b i t r ee r oo t)(o i f (root! = N U L L)print f ( " % c ", r oot-> d ata);。 preorder(roo t ->lchild);2P r eorder (roo t > r c h i Id)；/火中序递归遍历*/vo i d inord e r(b i t r ee ro o t)(i f(ro o t ! = N ULL)(。 p re o rdcr(root->lc h il d );<«pr i n t f( " %c ",root->data);op r c o rdc r (root>rchild);)/*后序递归遍历*/v oid post o r de r (bi t r ee r o ot)i f (roo t ! =NULL)(p r eorder( roo t->lchild);pre orde r (roo t -> r c hild);gprintf("%c ",roo t >da t a );)void mai n ()b it r e e bt;c tc a tcbi t re e (&b t )：pr i n t f ("先序递归遍历序列：n");。p rcor d cr (bt);p r i ntf ("n");P rint f ("中序递归遍历序列:n");®inor d er(bt)；p i n tf ( " n")；op r i ntf ("后序递归遍历序列：n ")；»p o s t o r der( b t)；print f ("n ");非递归算法程序# i n cl u d e <stdi o . h># i n clu d e <st d 1 i b. h ># i n elude <m a Hoc. h>#def i n e FALSE0#d e f i ne TRUE 1#de f ine max size 100二叉树结构体定义I y ped e f st r u c t n ode。c h ar d a ta;® s tr u ct n o de *lch i 1 d ;®stru c t n o d e * r c hild; bitnode, * b itre e ；type d cf s t r u c t顺序栈结构体定义(bi t rc e elem maxsi z c；i n t lop; s e q s ta c k;int pus h ( s cqstack *s,bi t ree x)/ /入栈if( s ->top=ma x s izc-1)r et u rn (FA LSE);s ->t o p+;s ->elem s ->top =x;retu r n ( T R UE);)b i t ree pop(s e qsta c k *s,b i tree x) / / 出栈(。i f(s-> t op=-1) r elum NULL；else0x=s->elems->top;s->to P -» r eturn x;)int gettop (seq s tack *s, b i tre e *x)读取栈顶元素® i f( s > t o p = 1) r e t u r n FAL S E;els e。2* x =s->elems-> t op;r e turn TRUE;。)v oid c r eatebit r ee (bitreet )扩展先序序列创建二叉链表(。c harch;ch=g e tchar();。i f (ch=-.' )*bt=NULL;el s e(* b t=(bi t ree)m a I 1 oc (sizeo f (b i t nod e );(*bt) -> d ata=ch;createbi t r e e (& (*b t )-> 1 chi 1 d)；ac r e a t ebi t ree(&(* b t)->rchil d );void p reord e r 1 ( b itree r o o t ,s e qst a c k s)/ /先序遍历ebitnode *p;op=root;while(p!=NULL|! (s.top=-l)»whilc(p!=NU L L)p r i n t f ("% c " ,p-> d at a );叩ush(& s ,p);p =p-> 1 chil d ;i f(!(s. top=-1) p=pop(& s ,p)； p=p->rch i id；中序遍历vo i d inorder I (bit r ee r oot,seqs t ack s )®bit n ode *p;5. t op= 1®p=root；whi 1 e(p! =NULL|!(s.t o p=-l)«if( p !=NUL L)-叩 u s h (& s , p)；p =p-> 1 child;°l3 p =pop(&s,p);2。p rin t f("%c*', p ->da t a);。 p=p->r c hild;2。)v oid postorde r 1 (bitree r 0 ot)后序遍历(b i tno d e * p,*q;®seqsta c k s;»q=NULL;»p=ro o t;s.to p =-l;/ / prin t f( 0 % c H,p->dala)；*wh ile( p !=NULL|! (s. top=1)wh i le(p! =NULL)(o push(&s, p ) ; p=p-> 1 child；。)if(!(s.to p =-l)° g et t op(& s ,&p);f (p-> r child= N U L L) I | (p->rchild= q )°