實(shí)驗(yàn)五_二叉樹與最優(yōu)二叉樹_09082229劉增鵬

1、實(shí)驗(yàn)5二叉樹與最優(yōu)二叉樹一、實(shí)驗(yàn)要求1、了解樹和二叉樹的特性，以及它們?cè)趯?shí)際問題中的應(yīng)用。2、掌握樹和二叉樹的實(shí)現(xiàn)方法以及它們的基本操作，學(xué)會(huì)運(yùn)用樹和二叉樹 來解決問題。二、實(shí)驗(yàn)題目1、用菜單驅(qū)動(dòng)的手法，編寫一個(gè)完整的程序，生成一棵二叉樹，求二叉樹 的高度，求二叉樹的葉子結(jié)點(diǎn)數(shù)，輸出二叉樹的所有結(jié)點(diǎn)。2、編寫一個(gè)完整的程序?qū)崿F(xiàn)，利用哈夫曼算法建立哈夫曼樹，并輸出這棵 樹中所有結(jié)點(diǎn)數(shù)據(jù)。三、算法描述二叉樹：一般常用的是動(dòng)態(tài)鏈?zhǔn)酱鎯?chǔ)，這時(shí)一般不用擔(dān)心空間溢出問題， 也不必關(guān)心存儲(chǔ)管理的細(xì)節(jié)（由系統(tǒng)完成），這使我們能用更多的精力去考慮其 他問題。在此用動(dòng)態(tài)鏈表存儲(chǔ)二叉樹。二叉鏈表是二叉樹最常用的存儲(chǔ)

2、結(jié)構(gòu)，其中每個(gè)結(jié)點(diǎn)除了存儲(chǔ)結(jié)點(diǎn)本身的 數(shù)據(jù)外，還設(shè)置兩個(gè)指針域Ichild和rchild，分別指向該結(jié)點(diǎn)的左孩子和右孩 子。這是二叉樹鏈?zhǔn)酱鎯?chǔ)的二指針形式。就像單鏈表由頭指針惟一確定一樣， 一個(gè)二義鏈表也由指向根結(jié)點(diǎn)的根指針惟一確定。為了某些運(yùn)算的方便，也可 給二義鏈表增加頭結(jié)點(diǎn)（但一般并沒有這樣做）。二叉樹的生成是指如何在內(nèi)存中建立二叉樹的存儲(chǔ)結(jié)構(gòu)。建立順序存儲(chǔ)結(jié) 構(gòu)的問題較簡單，這里僅討論如何建立二叉鏈表。要建立二叉鏈表，就需要按 照某種方式輸人二叉樹的結(jié)點(diǎn)及其邏輯信息。注意到對(duì)二叉樹遍歷時(shí)，不僅得 到了結(jié)點(diǎn)信息，而且由序列中結(jié)點(diǎn)的先后關(guān)系還可獲得一定的邏輯信息，如果 這些信息足夠，就可根

3、據(jù)遍歷序列生成相應(yīng)的二叉樹二叉樹的生成方法就是基于遍歷序列的，相當(dāng)于遍歷問題的逆問題，即由 遍歷序列反求二叉樹，這需要分析和利用二叉樹遍歷序列的特點(diǎn)。哈夫曼算法（最優(yōu)二叉樹）：在許多應(yīng)用中，常常將樹中結(jié)點(diǎn)賦予一個(gè)有某種 意義的實(shí)數(shù)，稱為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)到樹根之間的路徑長度與該結(jié)點(diǎn)權(quán)的乘積 稱為該結(jié)點(diǎn)的帶權(quán)路徑長度。樹的（外部）帶權(quán)路徑長度（Weighted Path Length），定義為樹中所有葉于結(jié)點(diǎn)的帶權(quán)路徑長度之和，通常記為：WPL=芝 wli=1其中，n表示子結(jié)點(diǎn)的數(shù)目，w和分別表示葉結(jié)點(diǎn)i的權(quán)值和它到根之間的路徑長度。在權(quán)為w1，w2,，wn的n個(gè)葉結(jié)點(diǎn)的所有二叉樹中，帶權(quán)路徑 長

4、度WPL最小的二叉樹.n（1）首先，根據(jù)給定的n個(gè)權(quán)值w1，w2，wn構(gòu)造含有n棵二叉樹的森林F=T；，T2，T ，其中每棵二叉樹T.中只有一個(gè)權(quán)值為W.的 根結(jié)點(diǎn)，沒有左右子樹。 11（2）在森林F中選出兩棵根結(jié)點(diǎn)權(quán)值最小的樹（當(dāng)這樣的樹不止兩棵樹 時(shí)，可從中任選兩棵），將這兩棵樹合并成一棵新的二叉樹。這時(shí)會(huì)增加一個(gè)新的根結(jié)點(diǎn)， 它的權(quán)取為原來兩棵樹的根的權(quán)值之和，而原來的兩棵樹就作為它的左右子樹 （誰左，誰右無關(guān)緊要）。（3）對(duì)新的森林F重復(fù)（2），直到森林F中只剩下一棵樹為止。這棵樹 便是哈大曼樹。由算法知，哈夫曼樹不一定惟一（但WPL是相同的，并且都為最?。Ｔ?因在于每次合并時(shí)，原兩

5、棵樹誰左誰右、以及候選的兩棵樹有多個(gè)時(shí)選哪兩個(gè) 等。在哈夫曼算法中，初始森林共有n棵二叉樹，每棵樹中僅有一個(gè)結(jié)點(diǎn)，它 們既是根，又是葉子。算法的第二步是將當(dāng)前森林中的兩棵根結(jié)點(diǎn)權(quán)值最小的 二叉樹合并成一棵新二叉樹。每合并一次，森林中就減少一棵樹。顯然，要進(jìn) 行nl次合并，才能使森林中二叉樹的數(shù)目由n棵減少到只剩一棵，即最終的 哈夫曼樹。另外，每合并一次都要產(chǎn)生一個(gè)新結(jié)點(diǎn)，合并n- l次共產(chǎn)生n- l個(gè)新結(jié)點(diǎn)。 由此可知，最終求得的哈大曼樹中共有n+（nl）=2n1個(gè)結(jié)點(diǎn)，其中的葉 結(jié)點(diǎn)就是初始森林中的n個(gè)孤立結(jié)點(diǎn)。在哈夫曼樹中，每個(gè)分支結(jié)點(diǎn)都是合并過程中產(chǎn)生的，它們的度為2,所 以樹中沒有度為

6、1的分支結(jié)點(diǎn)。四、程序清單#include#include#include#define M 200#define null 0#define n 8葉子結(jié)點(diǎn)數(shù)，假設(shè)為20#define m 15 結(jié)點(diǎn)總數(shù)#define max 1000typedef char Etype; /* 定義數(shù)據(jù)類型 */typedef struct BiTNode/* 定義結(jié)點(diǎn)類型 */ Etype data;struct BiTNode *lch,*rch;/*左 右子樹 */ BiTNode,*BiTree;BiTree queM;int front=0,rear=0;int count=0;BiTNode

7、*t,*p;typedef int datatype;typedef struct float weight;int parent,lchild,rchild;hftree; 結(jié)點(diǎn)類型hftree treem+1,tree2m+1;哈夫曼樹類型，數(shù)組從0號(hào)單元開始使用哈夫曼樹向量/*建立二叉樹(層次法)*/BiTNode *creat_bt1()(BiTNode *t,*p,*v20;int i,j; Etype e;printf(輸入二叉樹各結(jié)點(diǎn)的編號(hào)和對(duì) 應(yīng)的值(用空格隔開)：，scanf(%d %c”,&i,&e);while(i!=-1)(p=(BiTNode*)malloc(size

8、of(BiTNode);p-data=e;p-lch=NULL;p-rch=NULL;vi=p;if(i=1)t=p;else( j=i/2;if(i%2=0)vj-lch=p;else vj-rch=p;printf(輸入二叉樹各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值(輸入i為-1時(shí)結(jié)束)：，scanf(%d %c”,&i,&e);return(t);/先根法建立二叉樹BiTNode *creat_bt2()(BiTNode *t;char ch;fflush(stdin);scanf(%c”,&ch);if(ch=)return null;else(t=(BiTNode*)malloc(sizeof(BiT

9、Node);t-data=ch;t-lch=creat_bt2();t-rch=creat_bt2();return t;void huffman(hftree tree)( int i,j,p1,p2,kz,ky,exchange; /p1,p2 十己當(dāng) 前選的權(quán)值最小的兩棵樹根結(jié)點(diǎn)在向量T 中的下標(biāo)float sm1,sm2;for(i=1;i=n;i+)(/初始化，根結(jié)點(diǎn)(葉子)的雙親和左、右孩子指針置為-1treei.parent=0;treei.lchild = treei.rchild=0;treei.weight=0.0;printf(Hello huffman!n);print

10、f(t請(qǐng)輸入d個(gè)葉子結(jié)點(diǎn)的權(quán)值： n,n);for(i=1;i=n;i+)輸入n個(gè)葉子的權(quán)值( scanf (%f”,&treei.weight); for(i=1;i=n;i+)printf(%2.2f ”,treei.weight);printf(nn);for(i=n+1;i=m;i+)/第 i 次合并，產(chǎn)生第i棵新樹(結(jié)點(diǎn)).共進(jìn)行n-l次合并。(p1=p2=0;/此句可不要sm1=sm2=max;/max 為float型的最大值,它大于所有結(jié)點(diǎn)權(quán)值for (j=1;j=i-1;j+)從第0i-1棵樹中找兩個(gè)權(quán)值最小的根結(jié)點(diǎn)，/作為第i個(gè)生成的新樹( if (treej.parent

11、!= 0) continue;/ 不考慮已合并的點(diǎn),雙親域不為-1時(shí)就不是 根if(treej.weightsm1)/修改最小權(quán)和次小權(quán)及位置( sm2=sm1;/sml中記當(dāng)前找到的最小者權(quán)值,sm2記次小者 權(quán)值sm1= treej.weight;p2=p1; /pl 中記當(dāng) 前找到的權(quán)值最小者結(jié)點(diǎn)的下標(biāo)，/ p2記當(dāng)前權(quán)值次小者結(jié) 點(diǎn)的下標(biāo)p】=j；else if(treej.weight0;i-) printf(%4d”,i);printf(%10d: ,treei.parent);k=treei.parent;printf(%5.2f,treek.weight);printf(%10

12、d: ,treei.lchild);k=treei.lchild;printf(%5.2f,treek.weight);printf(%10d: ,treei.rchild);k=treei.rchild;printf(%5.2f,treek.weight);printf(%10.2fn,treei.weight);printf(Print end！ nn);void preorder(BiTNode *p )/* 先序遍歷二叉 樹*/ if(p) printf(%c ,p-data);preorder(p-lch);preorder(p-rch); void inorder(BiTNode

13、*p) /* 中序遍歷*/ if(p) inorder(p-lch);printf(%c ,p-data);inorder(p-rch); void postorder(BiTNode *p) /*后序遍歷 */ if(p) postorder(p-lch);postorder(p-rch);printf(%c ,p-data);void enqueue(BiTree T)( if(front!=(rear+1)%M)( rear=(rear+1)%M;querear=T;BiTree delqueue()( if(front=rear)return NULL;front=(front+1)%

14、M;return (quefront);void levorder(BiTree T)/*層次遍歷二叉樹 */( BiTree p;if(T)( enqueue(T);while(front!=rear)( p=delqueue();printf(%c ,p-data);if(p-lch!=NULL)enqueue(p-lch);if(p-rch!=NULL)enqueue(p-rch);int treedepth(BiTree bt)/*二 叉樹高度*/( int hl,hr,max1;if(bt!=NULL)( hl=treedepth(bt-lch);hr=treedepth(bt-rc

15、h);max1=(hlhr)? hl:hr;return(max1+1);else return(0);void prtbtree(BiTree bt,int level)/*打 印 */ int j;if(bt) prtbtree(bt-rch,level+1);printf(%dn,bt-data);prtbtree(bt-lch,level+1);void exchange(BiTree bt)/*交換二叉樹左右 子樹*/ BiTree p;if(bt) p=bt-lch;bt-lch=bt-rch;bt-rch=p;exchange(bt-lch);exchange(bt-rch);i

16、nt leafcount(BiTree bt) /* 葉子結(jié)點(diǎn)數(shù)*/ if(bt!=NULL) leafcount(bt-lch);leafcount(bt-rch);if(bt-lch=NULL)&(bt-rch=NUL L)count+;return(count);void paintleaf(BiTree bt)/* 葉子結(jié)點(diǎn)值 */ if(bt!=NULL)if(bt-lch=NULL&bt-rch=NULL)printf(%d ,bt-data);paintleaf(bt-lch);paintleaf(bt-rch);void print_menu()printf(主 菜單); pr

17、intf(n 1.建立二叉樹(層次發(fā))”)； printf(n 2.建立二叉樹(先根法); printf(n 3.先序遞歸遍歷二叉樹”)；printf（n 4.中序遞歸遍歷二叉樹”）；break;printf（n 5.后序遞歸遍歷二叉樹”）； printf（n 6.層次遍歷二叉樹”）； printf（n7.計(jì)算二叉樹的高度和葉子結(jié)點(diǎn)個(gè)數(shù)”）；printf（n8.建立哈夫曼樹”）；printf（n 9.打印哈夫曼樹”）；printf（n 0.打印二叉樹”）；printf（n E.結(jié)束程序運(yùn)行”）；printf（n）；case 3:if(t) printf(先序遍歷二 叉樹:，preorder(t

18、);printf(n);else printf(該二叉樹 為空!n);break;printf(n 請(qǐng)選擇：n)；char chioce_menu()( char ch;for(；)( scanf(%c”,&ch);if(chE)printf(”輸入錯(cuò)誤，重新選擇：n”); elsebreak;case 4:if(t) printf(中序遍歷 二叉樹:，inorder(t);printf(n);else printf(該二叉樹 為空!n);break;return ch；main()( char x;do( print_menu();switch(chioce_menu()(case 1:t=

19、creat_bt1();break;case 5:if(t) printf(后序遍歷 二叉樹:，postorder(t);printf(n);else printf(該二叉樹 為空!n);break;/*建立二叉樹算法*/case 2: printf（t先根遍歷 建立二叉樹：n）;printf（t 請(qǐng)輸入二 叉樹結(jié)點(diǎn)的值！ n）;printf（可以輸那 個(gè)值均為字母或（n100）字符間以回車 換行，想結(jié)束時(shí)輸多個(gè)：n）;case 6:if(t)printf(-層次遍歷二叉樹:，levorder(t);printf(n);else printf(該二叉樹 為空!n);break;t=creat_bt2();case 7:if(t)printf(二叉樹的高度為:dn”,treedepth(t);printf(二叉樹的葉 子結(jié)點(diǎn)數(shù)為:dn”,leafcount