2023年数据结构树和二叉树实验报告.docx

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

1、数据结构课程实验报告实验名称树和二叉树实验序号5实验日期姓名院系班级学号专业指导教师成绩教师评语一、实验目的和规定（1）掌握树的相关概念，涉及树、结点的度、树的度、分支结点、叶子结点、儿子结点、双亲结点、树的 深度、森林等定义。（2）掌握树的表达，涉及树形表达法、文氏图表达法、凹入表达法和括号表达法等。（3 ）掌握二叉树的概念，涉及二叉树,、满二叉树和完全二叉树的定义。（4）掌握二叉树的性质。（5 ）重点掌握二叉树的存储结构，涉及二叉树顺序存储结构和链式存储结构。（6）重点掌握二叉树的基本运算和各种遍历算法的实现。（7）掌握线索二叉树的概念和相关算法的实现。（8）掌握哈夫曼树的定义、哈夫曼树的

2、构造过程和哈夫曼编码产生方法。（9）掌握并查集的相关概念和算法。（10）灵活掌握运用二叉树这种数据结构解决一些综合应用问题。二、实验项目摘要1 .编写一程序，实现二叉树的各种基本运算，并在此基础上设计一个主程序完毕如下功能：（1）输出二叉树b;（2）输出H结点的左、右孩子结点值；（3）输出二叉树b的深度；（4）输出二叉树b的宽度；（5）输出二叉树b的结点个数；（6）输出二叉树b的叶子结点个数。2 .编写一程序，实现二叉树的先序遍历、中序遍历和后序遍历的各种递归和非递归算法，以及层次遍历的 算法。三、实验预习内容二叉树存储结构，二叉树基本运算（创建二叉树、寻找结点、找孩子结点、求高度、输出二叉树

3、）00。)void P ostOr d e r 1 (BTNode * b ) (BTN o de * S t M a xSi z e;aB T No d e *p;i nt flag, t op=- 1 ;0。i f (b!=NULL)(8do(。w h ile (b!=NU LL)。g top+；S t to p = b ;ob =blchi 1 d；p=NULL;3fla g = 1; a0 。while (top! =-l & & f 1 ag)01g ob=S t to p ;goo o i f ( b -r c h ild=p)o00 “in t f(%c data);0 top；

4、oao op=b；0。ooo gelse00|go b =br c hild?gf 1 a g =0；a00 o b)。 w h i 1 e ( t op! =-l); rintf(n); )void Lcve 1 Ordcr(BTNo d c *b) BTNo d e * p；B TNode *quMaxS i z e ；。int f r o nt,r e ar; f r o nt= r ear=- 1 ;r e ar+； 3gqurea r =b;wh i 1 e (fron t ! =r e ar) 。 f ront=(fron t +l)%Max S ize; p =qufro n t

5、; p rintf( %c ,r, p -d ala)；i f(p- 1 child!=NULL ) rear=(re a r+ 1 )%M a xSize;。qur ear =p- 1 chil d ; if (p-rchild!=NULL) rea r =(rea r +1)%MaxSize;。叫 u rear= p -rc h i I d ;)vo i d ma i n ()(oBTN ode *b;Create B TNode (b, A ( B (D,E(H(J, K ( L , M(,N ),C(F, G(,I)*);叩rintf(二叉树 b:)； D i spBTNode(b);

6、pr i n tf(n);叩r in t f(先序遍历序列:n )；sprint f (递归算法:);PreO r de r(b) ；p r intf( n);prinlf(非递归算法:);PreOrderl (b);P r i nt f (中序遍历序列:n)；。P rint f (递归算法门;InO法er(b);prin t f(n)；叩rintf(非递归算法:);InOr d er 1( b )；sprint f (后序遍历序列:n);p r i n tf(递归算法：);PostOrder(b); p ri n tf ( ii );p r int f (非递归算法：)；PostO rdcr

7、 1(b);pri n if (“层次遍历序列：”);Lev e 10 r de r (b);printf ( n n)；1注：空间不够，可以增长页码。三、实验结果与分析7-1# i nclu d e # i n elude #d e fin e MaxS i ze 1 0 0typed e f c ha r El e mT y pe;typedef str u ct no d e(E1 e mType dat a ： st r u c t n ode s t r u ct node *r c h ild? BTNode；void C r ca t c B TNod e (BTNo d c *

8、& b , c har * s t r) (oB T Node *S t MaxSiz e ,*p= N ULL； i nt t o p =l,k, j=0；c har ch；b=NU L L gch=strj;while (ch != 0 。 switch( c h)。(o c ase ( :top+： St top = p ； k=l ； break;- wcase ) : t o p -;br e a k ;case , : k =2; b r eak;3 dcfault:p=( BTNod e 火)ma 1 loc(s i z e of(BTNode)； p-lc h i 1 d =p

9、- r chi 1 d=NULL; (b=NULL)00 o(k)p - d ata=ch：i fa b =p; oooel s eg switc hoo a gK：ase 1 :Stto p lchild=p； bre a k;g 。 case 2 ： Sttop-rc h i 1 d= p ;b r ea k ;o do|oo。0 j+; ch= s tr|jj;。)BT N ode * FindNo d e( B TNode *b Ele mType x) B TNode *p;i f (b=NULL)。 r e (u r n NULL; e Ise i f (b-data=x) r e

10、 turn b;else(p = F i ndNode (b-lch i ld,x)；。if (p! =NULL)g return p；else。 re t u m F i ndN o de(b- r c h i Id, x)； )BTNodc *Lc h ildNode(BTNod e *p) re t u r n p-lchil d ;)BTNode *Rch i 1 dNod e(B TNode *p)re t u r n p-rc h i Id;1i n t BT NodeDepth (BT N ode *b) (int 1 c h ilddep,rc h i 1 d d e p ;i

11、f (b=NULL)”et urn ( 0 )； g 。 e 1 se。 1c h i 1 d dep=B TNo deDept h (b- 1 c hi 1 d);。 rch i lddep=BTNodeD e p t h (brc h i Id);。retu r n ( 1 childdepr c h i Id d ep)? (Ichi 1 ddep+1): (rchildd e p +1)； 。)v oid D i s p B TN ode(BTNodc * b)，i f(b!=NULL)0 oprintf(% c ,bda t a )；oi f (b- 1 ch i Id! =NULL

12、| I b-rch i Id! = NULL) 。printf( ()；0 oDi s pBTNod e (b- 1 ch i Id);g。i f (b -rchild ! =NULL)p r i n tf(,);。D i spBTNode (brchild)；g printf();0)1in t BTWid t h(BTN o de *b)(st r u c t(痴 n t Ino；。BTNodc *p；。 Q u M a x S i ze；int front,r ear; 。i n t 1 n um,ma x , i , n ;of r o n t =rear= 0 if(b !=NULL

13、)。r ear+;Qu r earl, p = b gQurea r .lno=l ；/while (rear!=fro n t)。0 ofront+; b =Q u f rontl.p； 。 In u m=Q u front, in o ;if(b- 1 child!=NULL)g000 。r ea r +;。Qu rear .p=blch i 1 d;。Q u rea r . 1 no= 1 n um+1;008 i f (b-rch i Id! =NULL) (。 re a r +；o 。Qurear.p=b-rchild;Qurear.ln o =ln u m+1;00 。3 max=

14、0： lnum = 1; i =1 ；gw h i 1 e (i=rear)0 ( n=0;g w h i 1 e ( i m a x ) ni a x = n ;0 Iretu r n max:0)e Ise ret u rn 0：Iini Nod es(BTNode *b)in t numl, n u m2;i f (b=NULL)or e t u r n 0;e 1 se i f(b-lch i ld=NULL& b-r c hild=NULL) return 1;el s enum Nod e s(b-l c hild);num 2 =N o des (b-rchi Id);r e t

15、urn ( n um 1 +nuni2+ 1 );int L e afNod e s (BTN ode *b)i nt num I,num 2 ；i f(b=NULL)return 0;e 1 se if (b-l c h i 1 d = N U LL & b-r c hi 1 d=N ULL) ret urn 1;cis en uml=LeafN o de s (b-l c hild)；n u m 2 =LeafNo d e s(b- r c hild); ret u rn (numl+num 2 )；)void mai n () (BTNode *b,* p, * Ip, *rp；;Cre

16、ateBTNode(b, A(B(D,E (H(J.K(L, M(,N) ),C(F,G(, I)； opr i nt f (输出二叉树:)；Di s p BTNod e (b);p r in t f( n 0 );oprinlf(H结点门;叩=F i n d Nod e (b/ H);。i f(p!=NULL) ( lp=L child Node( p ); if ( 1 p!=NULL)。pr i n t f(左孩子为 c , lp-data)； elseprintf(无左孩子)： rp= Rch i IdNode(p);。if (rp ! =NULL) 叩rinlf(右孩子为c”,rp-

17、 d at a ); else。printf(“无右孩子)；。叩 r intf (n );prin t f (二叉树 b 的深度:%d n,BTNo deD e pt h (b);print f (二叉树 b 的宽度：%dnBTWid t h(b);op rinif (二叉树 b 的结点个数:dn，Nodes (b);prin t f (二叉树 b 的叶子结点个数：%dn, Lea fNod e s(b); )7-2# i n c lude # i nc 1 ud e #d e fin e Max Size 1 0 0type def c h ar E lemType; typede f s

18、t ruct n ode oElemTypc data?ast r u ct node * 1 ch i Id； str u ct no d c *r c hild;。 BTN ode;void CreateBTNode (BTN o de * & b ,cha r * s tr) (B T Nod e * StMax S ize,* p = N ULL;i n t top= 1 ， k,j=O;cha r ch；b =NULL; goch=strj：whi 1 e (c h !=0)oswitc h (ch)cas e (： top+4- ； S t t o pj=p;k=l; brca k

19、 ；M a se )： top-;b r e ak;ca s e :k=2; b re a k;3 de f ault： p= (BTNode * )mall o c(si z eof( B T No d e);p- d at a =ch; p -)ch i ld=p-rchild=NULL;，i f(b=NULL)。 b =p;g e Ise 。gOO6 3。 swi t ch(k)o do gc ase o p lchild= P ;b r eak;g s case 2:Stt o p J-rchi 1 d =p;b r e ak;000 o02 。j +:sc h =strj;0) )v

20、oid DispB T Node (BTNod e * b )，if(b!二NULL)(printf(%c, b -dat a );if (b- 1 child!=NULL| b-rch i ld!=NULL) p rintf (“(”)；DispBTNode(b-lchild)； oooif(b- r ch i ld!=NULL) pri n tf(J);Di s p BTNode (b- r child);00 pr i nt f ( 11 );0)void Pr e Ord e r(B TNo d e *b) (if(b!=NULL)gprintf (% c , b -d ata);wP

21、reO r d e r (b-l c hil d );r eO r d e r(b- r chil d );)voi d PreOr d erl ( B TNod e *b) o BTNode *StMaxS i z e ,* p ;i nt t o p= 1;i f (b! =NUL L) top+; ggS t ( o p=b; while (top-lP =St t op： t op-;prinlf(%c ,p-da t a);if (p- rchi 1 d!=NULL) top+;S t t o p = p-rc h ild;0 o|if (p-lch i ld!=NULL)t o p

22、+；S t to p =p-lchild； 000 0 print f ( n);1void I n 0 rder(B T N o d e *b)i f (b! =NU LL)InOrdcr(b-l c hi 1 d);8P r i ntf(M%c ,bdata); I nOrdcr( b -r c hi 1 d)Iv o id I n Orde r l(BTNo d e * b )aBTNode * St MaxSize,*p;int t op=- 1 ；。i f(b!=NULL)( P = b ; while ( t o p I | | p! = NULL) (whi 1 e (p! =NULL) 4 O p +；S t top = p ;p=p-lchild；0) i f ( t op I)000 12P=St to pj;gg t o p -o 叩 r int f ( % c , p d a ta); wp=p-rc h i 1 d;38 print f(n);)1void P o stO r d e r(BTNode *b)(i f(b!=NULL)0 03 Po s tOr d e r(blchild);0Po s 10 r d er( b -r c h ild);pr i nt f (% c n,b-da t a);