《數(shù)據(jù)結(jié)構(gòu)與算法》實(shí)驗(yàn)指導(dǎo)與報告書

1、常熟理工學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)指導(dǎo)與報告書2017-2018學(xué)年第一學(xué)期專業(yè)：物聯(lián)網(wǎng)工程實(shí)驗(yàn)名稱：二叉樹實(shí)驗(yàn)地點(diǎn)：N6-210指導(dǎo)教師：聶盼紅計算機(jī)科學(xué)與工程學(xué)院2017精選范本，供參考!實(shí)驗(yàn)六二叉樹【實(shí)驗(yàn)?zāi)康摹?、掌握二叉樹的基本存儲表示。2、掌握二叉樹的遍歷操作實(shí)現(xiàn)方法（遞歸和非遞歸方法）3、理解并實(shí)現(xiàn)二叉樹的其他基本操作。4、掌握二叉樹的重要應(yīng)用-哈夫曼編碼的實(shí)現(xiàn)。【實(shí)驗(yàn)學(xué)時】4-6學(xué)時【實(shí)驗(yàn)預(yù)習(xí)】回答以下問題：1、二叉樹的二叉鏈表存儲表示。/*-叉樹的叉鏈表存儲表木-*/typedefstructBTNodechardata;/*結(jié)點(diǎn)數(shù)據(jù)*/structBTNode*lchild;/*

2、左孩子指針*/structBTNode*rchild;/*右孩子指針*/*BiTree;2、二叉樹的三種基本遍歷方式。/*先序遍歷二叉樹，補(bǔ)充遞歸算法*/voidPreOrder(BiTreep)if(p!=NULL);printf("%c”,p->data);/訪問根節(jié)點(diǎn)PreOrder(p->lchild);先序遍歷左子數(shù)PreOrder(p->rchild);先序遍歷右子數(shù)/*PreOrder*/*中序遍歷二叉樹，補(bǔ)充遞歸算法*/voidInOrder(BiTreep)if(p!=NULL);InOrder(p->lchild);/中序遍歷左子數(shù)prin

3、tf("%c",p->data);訪問根節(jié)點(diǎn)InOrder(p->rchild);中序遍歷右子數(shù)/*InOrder*/*后序遍歷二叉樹，補(bǔ)充遞歸算法*/voidPostOrder(BiTreep)if(p!=NULL);PostOrder(p->lchild);后序遍歷左子數(shù)PostOrder(p->rchild);后序遍歷右子數(shù)printf("%c",p->data);訪問根節(jié)點(diǎn)/*PostOrder*/3、解釋哈夫曼樹和帶權(quán)路徑長度WPL。哈夫曼樹，是指權(quán)值為W1、W2、.Wn的n個葉節(jié)點(diǎn)所構(gòu)成的二叉樹中帶權(quán)路徑長度最小

4、的二叉樹。從樹根結(jié)點(diǎn)到到該結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)上權(quán)的乘積稱為結(jié)點(diǎn)的帶權(quán)路徑長度，通常記作：WPL=2(n,i=1)WiLi【實(shí)驗(yàn)內(nèi)容和要求】1、編寫程序exp6_1.c,實(shí)現(xiàn)二叉樹的鏈?zhǔn)酱鎯盎静僮?。以下圖所示的二叉樹實(shí)現(xiàn)二叉樹的二叉鏈表存儲及基本操作，回答下列問題，補(bǔ)充完整程序，并調(diào)試運(yùn)行驗(yàn)證結(jié)果。u.1Al(1)按照先序序列建立該二叉樹。讀入的字符序列應(yīng)為：A,B,C,*,*,D,E,*,G,*,;F,*,*,*(*表示空指針)。(2)該二叉樹的三種遍歷序列：先序序列：A,B,C,D,E,G,F;中序序列：C,B,E,G,D,F,A;后序序列：C,G,E,F,D,B,A;(3)按層

5、次遍歷該二叉樹，得到的序列為：A,B,C,D,E,F,G(4)該二叉樹的深度為5。(5)該二叉樹的葉子結(jié)點(diǎn)數(shù)為：3。(畫出新二叉樹的圖)(6)交換該二叉樹所有結(jié)點(diǎn)的左右次序得到的新二叉樹為:(7)新二叉樹的三種遍歷序列分別為：先序序列：A,B,D,C,F,G,E;中序序列：D,B,F,G,C,E,A;后序序列：D,G,F,E,C,B,A;exp6_1.c參考程序如下：#include<stdio.h>#include<malloc.h>#defineMAX20/*-叉樹的叉鏈表存儲表木-*/typedefstructBTNodechardata;/*結(jié)點(diǎn)數(shù)據(jù)*/stru

6、ctBTNode*lchild;/*左孩子指針*/structBTNode*rchild;/*右孩子指針*/*BiTree;/*-非遞歸遍歷輔助隊列-*/typedefstructSqQueueBiTreedataMAX;intfront,rear;SqQueue;/*先序遍歷創(chuàng)建二叉樹*/*先序遍歷二叉樹*/*中序遍歷二叉樹*/*后序遍歷二叉樹*/voidcreateBiTree(BiTree*t);voidPreOrder(BiTreep);voidInOrder(BiTreep);voidPostOrder(BiTreep);voidRPreorder(BiTreep);/*先序遍歷的非

7、遞歸算法*/voidRInorder(BiTreep);/*中序遍歷的非遞歸算法*/voidRPostorder(BiTreep);/*后序遍歷的非遞歸算法*/intdepth(BiTreet);/*求二叉樹的深度算法*/BiTreegettreenode(charx,BiTreelptr,BiTreerptr);/*后序復(fù)制二叉樹-建立Z點(diǎn)*/BiTree copytree(BiTree t);BiTree swap(BiTree b);void ccOrder(BiTree t);int Leaves(BiTree t);void release(BiTree t);/*以后序遍歷的方式復(fù)

8、制二叉樹*/*交換二叉樹的結(jié)點(diǎn)的左右孩子*/*利用循環(huán)隊列實(shí)現(xiàn)層次遍歷*/*統(tǒng)計二叉樹葉子結(jié)點(diǎn)（遞歸）*/*釋放二叉樹*/*先序遍歷創(chuàng)建二叉樹*/voidcreateBiTree(BiTree*t)chars;BiTreeq;printf("npleaseinputdata:");s=getchar();getchar();/*扔掉存在鍵盤緩沖區(qū)的輸入結(jié)束回車符*/if(s='#')/*子樹為空則返回*/*t=NULL;return;elseq=(BiTree)malloc(sizeof(structBTNode);if(q=NULL)printf(&quo

9、t;Memoryallocfailure!");exit(0);q->data=s;*t=q;createBiTree(&q->lchild);/*遞歸建立左子樹*/createBiTree(&q->rchild);/*遞歸建立右子樹*/*createBiTree*/*先序遍歷二叉樹，補(bǔ)充遞歸算法*/voidPreOrder(BiTreep)if(p!=NULL)printf("%c”,p->data);/訪問根節(jié)點(diǎn)PreOrder(p->lchild);先序遍歷左子數(shù)PreOrder(p->rchild);先序遍歷右子數(shù)

10、/*PreOrder*/*中序遍歷二叉樹，補(bǔ)充遞歸算法*/voidInOrder(BiTreep)if(p!=NULL)InOrder(p->lchild);/中序遍歷左子數(shù)printf("%c”,p->data);/訪問根節(jié)點(diǎn)InOrder(p->rchild);中序遍歷右子數(shù)/*InOrder*/*后序遍歷二叉樹，補(bǔ)充遞歸算法*/voidPostOrder(BiTreep)if(p!=NULL)PostOrder(p->lchild);后序遍歷左子數(shù)PostOrder(p->rchild);后序遍歷右子數(shù)printf("%c”,p->

11、data);/訪問根節(jié)點(diǎn)/*PostOrder*/*先序遍歷的非遞歸算法*/voidRPreorder(BiTreep)BiTreestackMAX,q;inttop=0,i;for(i=0;i<MAX;i+)stacki=NULL;/*初始化棧*/q=p;while(q!=NULL)printf("%c",q->data);if(q->rchild!=NULL)stacktop+=q->rchild;/*右指針進(jìn)棧*/if(q->lchild!=NULL)q=q->lchild;/*順著左指針繼續(xù)向下*/elseif(top>0)

12、*/q=stack-top;/*左子樹訪問完，出棧繼續(xù)訪問右子樹結(jié)點(diǎn)elseq=NULL;/*RPreorder*/*中序遍歷的非遞歸算法*/voidRInorder(BiTreep)BiTreestackMAX,q;定義節(jié)點(diǎn)棧和搜索指針inttop=0;q=p；dowhile(q)/左鏈所有節(jié)點(diǎn)入棧stacktop+=q;q=q->lchild;if(top>0)q=stack-top;printf("%c",q->data);訪問根q=q->rchild;while(q|top!=0);/*RInorder*/*后序遍歷的非遞歸算法*/voidR

13、Postorder(BiTreep)BiTreestackMAX,q;inti,top=0,flagMAX;for(i=0;i<MAX;i+)/*初始化棧*/stacki=NULL;flagi=0;q=p;while(q!=NULL|top!=0)*/if(q!=NULL)/*當(dāng)前結(jié)點(diǎn)進(jìn)棧，先遍歷其左子樹stacktop=q;flagtop=0;top+;q=q->lchild;elsewhile(top)if(flagtop-1=0)/*遍歷結(jié)點(diǎn)白右子樹*/q=stacktop-1;q=q->rchild;flagtop-1=1;break;elseq=stack-top;

14、printf("%c",q->data);/*遍歷結(jié)點(diǎn)*/if(top=0)break;/*RPostorder*/*求二叉樹的深度算法，補(bǔ)充遞歸算法*/intdepth(BiTreet)intlc,rc;if(t=NULL)return0;若為空樹，則返回零elselc=depth(t->lchild);/遞歸求t的左子樹深度rc=depth(t->rchild);/遞歸求t的右子樹深度if(lc>rc)return(lc+1);elsereturn(rc+1);/*depth*/*建立結(jié)點(diǎn)*/BiTreegettreenode(charx,BiT

15、reelptr,BiTreerptr)BiTreet;t=(BiTree)malloc(sizeof(structBTNode);t->data=x;t->lchild=Iptr;t->rchild=rptr;return(t);/*gettreenode*/*以后序遍歷的方式遞歸復(fù)制二叉樹*/BiTreecopytree(BiTreet)BiTreenewlptr,newrptr,newnode;if(t=NULL)returnNULL;if(t->lchild!=NULL)newlptr=copytree(t->lchild);elsenewlptr=NULL

16、;if(t->rchild!=NULL)newrptr=copytree(t->rchild);elsenewrptr=NULL;newnode=gettreenode(t->data,newlptr,newrptr);return(newnode);/*copytree*/*交換二叉樹的結(jié)點(diǎn)的左右孩子*/BiTreeswap(BiTreeb)BiTreet,t1,t2;if(b=NULL)t=NULL;elset=(BiTree)malloc(sizeof(structBTNode);t->data=b->data;t1=swap(b->lchild);/

17、*遞歸交換左子樹上的結(jié)點(diǎn)*/t2=swap(b->rchild);/*遞歸交換右子樹上的結(jié)點(diǎn)*/*交換根t的左右子樹*/t->lchild=t2;t->rchild=t1;return(t);/*swap*/*利用循環(huán)隊列實(shí)現(xiàn)層次遍歷*/voidccOrder(BiTreet)BiTreep;SqQueueqlist,*q;利用循環(huán)隊列，實(shí)現(xiàn)層次遍歷q=&qlist;q->rear=0;q->front=0;初始化隊列p=t;if(p!=NULL)printf("%c”,p->data);/訪問根節(jié)點(diǎn)q->dataq->rear

18、=p;/根節(jié)點(diǎn)入隊q->rear=(q->rear+1)%MAX;/修改隊尾指針while(q->front!=q->rear)p=q->dataq->front;/出隊操作q->front=(q->front+1)%MAX;if(p->lchild!=NULL)訪問出隊節(jié)點(diǎn)的左孩子，并且入隊printf("%c",p->lchild->data);q->dataq->rear=p->lchild;q->rear=(q->rear+1)%MAX;if(p->rchild!=

19、NULL)訪問出隊節(jié)點(diǎn)的右孩子，并且入隊printf("%c",p->rchild->data);q->dataq->rear=p->rchild;q->rear=(q->rear+1)%MAX;/*ccOrder*/*統(tǒng)計二叉樹葉子結(jié)點(diǎn)，補(bǔ)充遞歸算法*/intLeaves(BiTreet)if(t=NULL)return0;if(t->lchild=NULL&&t->rchild=NULL)return1;return(Leaves(t->lchild)+Leaves(t->rchild);

20、左子數(shù)葉子節(jié)點(diǎn)加上右子數(shù)葉子結(jié)點(diǎn)/*Leaves*/*釋放二叉樹*/voidrelease(BiTreet)if(t!=NULL)release(t->lchild);release(t->rchild);free(t);/*release*/intmain()BiTreet=NULL,copyt=NULL;intselect;doprintf("n*MENU*n");printf（"1.按先序序列建立二叉樹n"）;printf（"2.遍歷二叉樹（三種遞歸方法）n"）;printf（"3.遍歷二叉樹（三種非遞歸方

21、法）n"）;printf（"4.層次遍歷二叉樹n"）;printf（"5.輸出二叉樹的深度n"）;printf（"6.統(tǒng)計二叉樹的葉子結(jié)點(diǎn)數(shù)（遞歸）n"）;printf（"7.后序遍歷方式復(fù)制一棵二叉樹n"）;printf（"8.交換二叉樹所有結(jié)點(diǎn)的左右孩子n"）;printf("0.EXIT");printf("n*MENU*n");printf("ninputchoice:");scanf("%d",&

22、amp;select);getchar();switch(select)case 1:printf（"n1-按先序序列建立二叉樹：n"）;printf（"請依次輸入結(jié)點(diǎn)序列：n"）;/BiTreegettreenode(x,&lptr,&rptr);createBiTree(&t);if(t!=NULL)printf("二叉樹創(chuàng)建成功！n");elseprintf("二叉樹未創(chuàng)建成功！n");break;case 2:printf("n2-遍歷二叉樹(三種遞歸方法)：n"

23、);printf("n先序遍歷序列：")；PreOrder；printf("n中序遍歷序列：")；InOrder(t);printf("n后序遍歷序列：")；PostOrder(t);printf("n");break;case 3:printf("n3-遍歷二叉樹(三種非遞歸方法)：n");printf("n先序遍歷的非遞歸：")；RPreorder(t);printf("n中序遍歷的非遞歸：")；RInorder；printf("n后序遍歷的

24、非遞歸：")；RPostorder(t);printf("n");break;case 4:printf("n4-層次遍歷二叉樹：n");printf("n按層次遍歷：”)；ccOrder(t);printf("n");break;case 5:printf("n5-輸出二叉樹的深度：n");printf("n二叉樹的深度：d",depth(t);printf("n");break;case 6:printf("n6-統(tǒng)計二叉樹的葉子結(jié)點(diǎn)數(shù)(遞歸

25、)：n");printf("n葉子結(jié)點(diǎn)數(shù)為：d",Leaves(t);printf("n");break;case 7:printf("n7-后序遍歷方式復(fù)制一棵二叉樹：n");copyt=copytree(t);if(copyt!=NULL)printf("n先序遞歸遍歷復(fù)制的二叉樹：")；PreOrder(copyt);elseprintf("n復(fù)制失?。?quot;);printf("n");break;case 8:printf("n8-交換二叉樹所有結(jié)點(diǎn)的

26、左右孩子：n");printf("n先序遞歸遍歷交換后的二叉樹：")；*/PreOrder(swap(t);/*如需輸出中序和后序遍歷的結(jié)果，增加調(diào)用printf("n");break;case0:release(t);/*釋放二叉樹*/break;default:break;while(select);return0;exp6_1.c實(shí)驗(yàn)結(jié)果：(1)按照先序序列建立二叉樹：xnputtIcek奉先序序冽建立二上請艘次輸入結(jié)點(diǎn)庠列.pleaseinputdata=apleaseinp”匚data=bple»£R'&q

27、uot;iripii.trdai=h.：cpleatseinputdata：1!pleaseinputdata01名足髭倍inj»iitria七%：dpleaseinputpleaeein)>utd*七鼻=itT>leaseinputd磯td：gjjleA&cliipubdatii-ttpleaseififiiitd以肥atilpleaseinputdatdi：fplDaitoxnputdaltai*1tpleaseinvutdata-ttpl匕4對修JjkpUUddCd-tt一叉洞創(chuàng)建成功I(2)該二叉樹的三種遞歸遍歷序列為:Inputchoice-2”遍后二叉

28、樹(三種遞歸方法)-a be de'jff F =c h&sdE z segG £dba(3)遍歷二叉樹(三種非遞歸方法)input chulee-3J遍歷二式樹(三種非遞歸方法)=歷歷歷遍遍遍先中后的的的力石，百逸凰劇-h_lLr.二：cgcfdba(4)層次遍歷二叉樹：inpuitchoicc：44-層次遍歷二叉樹二按層次遍歷舊如日匚£目(5)輸出二叉樹的深度£niputcliaice：=>A輸出二叉樹的深度，二叉樹的深度逐(6)統(tǒng)計二叉樹的葉子結(jié)點(diǎn)數(shù)(遞歸)XTIpULt；!JLGC=6統(tǒng)計一叉樹的葉子結(jié)點(diǎn)數(shù)(遞歸)：卜子結(jié)點(diǎn)數(shù)為：3|

29、(7)后序遍歷方式復(fù)制一棵二叉樹inpLi/tchcice：后序遍歷方式復(fù)制一棵二翼樹=先序遞歸遍歷復(fù)制的二叉樹ebcM復(fù)(8)交換二叉樹所有結(jié)點(diǎn)的左右孩子xnpotcliaice18交換二叉樹所有皓點(diǎn)的左右落子工先序遞歸遍歷交執(zhí)后的二翼樹媼京"2、編寫程序exp6_2.c,實(shí)現(xiàn)哈夫曼樹的建立和哈夫曼編碼。若有一組字符序列a,c,e,i,s,t,w,對應(yīng)的出現(xiàn)頻率為10,1,15,12,3,4,13。以此序列創(chuàng)建哈夫曼樹和哈夫曼編碼?；卮鹣铝袉栴}，補(bǔ)充完整程序，并調(diào)試運(yùn)行驗(yàn)證結(jié)果。(1) 構(gòu)造該序列的哈夫曼樹，畫出哈夫曼樹的形態(tài)。(以結(jié)點(diǎn)值左小右大的原則)T658T425T533T3

30、18e15i12w13t28a 10t4T14cls 3(2) 寫出對應(yīng)的哈夫曼編碼。a的編碼為111,c的編碼為11000,e的編碼為10,i的編碼為00,s的編碼為11001,t的編碼為1101,w的編碼為01(3) 計算編碼的WPL。WPL=3*10+5*1+2*15+2*12+5*3+4*4+2*13=146exp6_2.c程序代碼參考如下：#include<stdio.h># defineMAXVALUE10000/*定義最大權(quán)值*/# defineMAXLEAF30/*定義哈夫曼樹中口t子結(jié)點(diǎn)個數(shù)*/# defineMAXNODEMAXLEAF*2-1# defineM

31、AXBIT10/*定義哈夫曼編碼的最大長度*/typedefstruct/*哈夫曼編碼結(jié)構(gòu)*/intbitMAXBIT;intstart;HCodeType;typedefstruct/*哈夫曼樹結(jié)點(diǎn)結(jié)構(gòu)*/chardata;intweight;intparent;intIchild;intrchild;HNodeType;voidHuffmanTree(HNodeTypeHuffNode,int*hn);voidHuffmanCode(HNodeTypeHuffNode口,HCodeTypeHuffCode口,intn);voidHuffmanTree(HNodeTypeHuffNode,i

32、nt*hn)/*哈夫曼樹的構(gòu)造算法*/inti,j,m1,m2,x1,x2,n;printf("n:");scanf("%d",&n);getchar();/*輸入葉子結(jié)點(diǎn)個數(shù)*/for(i=0;i<2*n-1;i+)/*數(shù)組HuffNode初始化*/HuffNodei.parent=-1;HuffNodei.lchild=-1;HuffNodei.rchild=-1;printf("HuffNode:n");for(i=0;i<n;i+)scanf("%c,%d",&HuffNodei

33、.data,&HuffNodei.weight);/*輸入n個葉子結(jié)點(diǎn)的權(quán)值*/getchar();for(i=0;i<n-1;i+)/*構(gòu)造哈夫曼樹*/m1=m2=MAXVALUE;x1=x2=0;for(j=0;j<n+i;j+)if(HuffNodej.weight<m1&&HuffNodej.parent=-1)m2=m1;x2=x1;m1=HuffNodej.weight;x1=j；elseif(HuffNodej.weight<m2&&HuffNodej.parent=-1)m2=HuffNodej.weight;x2

34、=j;/*將找出的兩棵子樹合并為一棵子樹*/HuffNodex1.parent=n+i;HuffNodex2.parent=n+i;HuffNoden+i.weight=HuffNodex1.weight+HuffNodex2.weight;HuffNoden+i.lchild=x1;HuffNoden+i.rchild=x2;*hn=n;voidHuffmanCode(HNodeTypeHuffNode,HCodeTypeHuffCode,intn)/*生成哈夫曼編碼*/HCodeTypecd;inti,j,c,p;for(i=0;i<n;i+)/*求每個葉子結(jié)點(diǎn)的哈夫曼編碼*/cd.start=n-1;c=i;p=HuffNodec.parent;while(p!=-1)/*由葉