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

数据结构课程实验报告实验名称树和二叉树实验序号5实验日期姓名院系班级学号专业指导教师成绩教师评语一、实验目的和规定（1）掌握树的相关概念，涉及树、结点的度、树的度、分支结点、叶子结点、儿子结点、双亲结点、树的 深度、森林等定义。（2）掌握树的表达，涉及树形表达法、文氏图表达法、凹入表达法和括号表达法等。（3 ）掌握二叉树的概念，涉及二叉树,、满二叉树和完全二叉树的定义。（4）掌握二叉树的性质。（5 ）重点掌握二叉树的存储结构，涉及二叉树顺序存储结构和链式存储结构。（6）重点掌握二叉树的基本运算和各种遍历算法的实现。（7）掌握线索二叉树的概念和相关算法的实现。（8）掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码产生方法。（9）掌握并查集的相关概念和算法。（10）灵活掌握运用二叉树这种数据结构解决一些综合应用问题。二、实验项目摘要1 .编写一程序，实现二叉树的各种基本运算，并在此基础上设计一个主程序完毕如下功能：（1）输出二叉树b;（2）输出H结点的左、右孩子结点值；（3）输出二叉树b的深度；（4）输出二叉树b的宽度；（5）输出二叉树b的结点个数；（6）输出二叉树b的叶子结点个数。2 .编写一程序，实现二叉树的先序遍历、中序遍历和后序遍历的各种递归和非递归算法，以及层次遍历的 算法。三、实验预习内容二叉树存储结构，二叉树基本运算（创建二叉树、寻找结点、找孩子结点、求高度、输出二叉树）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 =b>lchi 1 d；p=NULL;3fla g = 1; a®0 。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；oao op=b；0。ooo gelse00|go b =b>r c hild?g»f 1 a g =0；a°°00 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;® 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);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 1(b);pri n if (“层次遍历序列：”);Lev e 10 r de r (b);printf ( n n")；1注：空间不够，可以增长页码。三、实验结果与分析7-1# i nclu d e <s t d i o.h># i n elude <malloc. h >#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 *& 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 g«ch=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-> 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 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 ;if (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 (b>rc h i Id);。«retu r n ( 1 childdep>r 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 " ,b>da t a )；oi f (b-> 1 ch i Id! =NULL| 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 (b>rchild)；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)。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=b>lch 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=0： lnum = 1; i =1 ；gw h i 1 e (i<=rear)0 (° n=0;g w h i 1 e ( i <= r ear && Qui .lno=ln u m)001go0n+;i+;0 )®®lnum=Qui J . 1 no;gif (n>m a x ) ni a x = n ;0 I«retu 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 turn ( 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；;»CreateBTNode(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-> d at a );« else。printf(“无右孩子")；。叩 r intf ("n ");prin t f ("二叉树 b 的深度:%d n",BTNo deD e pt h (b);print f ("二叉树 b 的宽度：%dn'BTWid 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 < s tdi o ,h># i nc 1 ud e <malloc.h>#d e fin e Max Size 1 0 0type def c h ar E lemType; typede f s 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 ；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) )void 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);wPreO 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>-l>P =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+；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 ",b>data);« 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(b>lchild);0Po s 10 r d er( b ->r c h ild);pr i nt f ("% c n,b->da t a);