1、石子合并問(wèn)題 有n堆石子,每堆有一個(gè)重量,每次把2堆石子合并成1堆,付出的代價(jià)為這兩堆石子的重量之和,如果把這n堆石子最后合并成1堆石子,怎樣合并才能使付出的代價(jià)最小,求出最小的代價(jià).每堆石子的位置可以調(diào)換.八、最優(yōu)二叉樹(哈夫曼樹)顯然圖(D)所示的合并方法付出的代價(jià)最小:54 例如n=5,重量 分別為7、5、2、4、6。246511671324L=6+11+13+24=541、最優(yōu)二叉樹的定義在具有n個(gè)帶權(quán)葉結(jié)點(diǎn)的二叉樹中，使所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和（即二叉樹的帶權(quán)路徑長(zhǎng)度）為最小的二叉樹，稱為最優(yōu)二叉樹（又稱最優(yōu)搜索樹或哈夫曼樹），即最優(yōu)二叉樹使（wk第k個(gè)葉結(jié)點(diǎn)的權(quán)值；pk第k個(gè)葉

2、結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度）達(dá)到最小。 2、最優(yōu)二叉樹的構(gòu)造方法 假定給出n個(gè)結(jié)點(diǎn)ki(i=1n)，其權(quán)值分別為wi(i=1n)。要構(gòu)造以此n個(gè)結(jié)點(diǎn)為葉結(jié)點(diǎn)的最優(yōu)二叉樹，其構(gòu)造方法如下： 首先，將給定的n個(gè)結(jié)點(diǎn)構(gòu)成n棵二叉樹的集合F=T1，T2，Tn。其中每棵二叉樹Ti中只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)ki，其左、右子樹均為空。然后做以下兩步 在F中選取根結(jié)點(diǎn)權(quán)值最小的兩棵二叉樹作為左右子樹，構(gòu)造一棵新的二叉樹，并且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和； 在F中刪除這兩棵二叉樹，同時(shí)將新得到的二叉樹加入F中；重復(fù)、，直到在F中只含有一棵二叉樹為止。這棵二叉樹便是最優(yōu)二叉樹。以上構(gòu)造最優(yōu)二

3、叉樹的方法稱為哈夫曼（huffmann）算法。 例如：給定五個(gè)結(jié)點(diǎn)k1，k2，k3，k4，k5，其權(quán)值分別為16、2、18、16、23。構(gòu)造最優(yōu)二叉樹的過(guò)程如下：構(gòu)造初始集合F，F(xiàn)中各二叉樹根結(jié)點(diǎn)的權(quán)值分別為16，2，18，16，23（如下圖）： 最后得到最優(yōu)二叉樹（如下圖），其根結(jié)點(diǎn)的權(quán)值為75，結(jié)點(diǎn)數(shù)為2*5-1=9。在最優(yōu)二叉樹中非葉結(jié)點(diǎn)的度均為2，因此采用順序存儲(chǔ)結(jié)構(gòu)為宜。如果帶權(quán)葉結(jié)點(diǎn)數(shù)為n個(gè)，則最優(yōu)二叉樹的結(jié)點(diǎn)數(shù)為2n-1個(gè)。由此得出最優(yōu)二叉樹的數(shù)據(jù)類型定義const int LEAF = 100+1;/葉結(jié)點(diǎn)數(shù)的上限const int MAXN = 2*LEAF;/最優(yōu)二叉樹的結(jié)

4、點(diǎn)數(shù)const int INF = 99999999;struct node int data;/結(jié)點(diǎn)的權(quán)值int prt, lch, rch;/父指針、左、右孩子指針;node htMAXN;/ht1.htn為葉結(jié)點(diǎn)，htn+1.ht2n-1為中間結(jié)點(diǎn)，根為ht2n-1 int n,m;/n 為讀入的葉結(jié)點(diǎn)數(shù)，m 為總結(jié)點(diǎn)數(shù)int pathLEAF; /葉結(jié)點(diǎn)到根的路徑長(zhǎng)度在最優(yōu)二叉樹的順序存儲(chǔ)結(jié)構(gòu)中前n個(gè)結(jié)點(diǎn)為葉結(jié)點(diǎn)。構(gòu)造最優(yōu)二叉樹的算法如下：int findmin(int i)/在前i個(gè)結(jié)點(diǎn)中選擇父指針為0且權(quán)值最小結(jié)點(diǎn)的位置int j, k, min;min = INF;for (j=

5、1; j=i; j+)if ( (htj.prt = 0) & (htj.data n;/ 讀入葉結(jié)點(diǎn)數(shù)for (i=1; i hti.data;m = 2*n -1; / 計(jì)算總結(jié)點(diǎn)數(shù)for (i=n+1; i=m; i+)j = findmin(i-1); /找第1個(gè)權(quán)值最小的結(jié)點(diǎn)htj.prt = i; /父指針指向ik = findmin(i-1); /找第2個(gè)權(quán)值最小的結(jié)點(diǎn)htk.prt = i; /父指針指向ihti.data = htj.data + htk.data; /計(jì)算結(jié)點(diǎn)i 的權(quán)值hti.lch = j; /處理i 的左右孩子指針hti.rch = k;root = m

6、; int findpath(int i) / 計(jì)算葉結(jié)點(diǎn)到根的路徑長(zhǎng)度int j, k;j = i; k=0;while (htj.prt !=0)k+;j = htj.prt;return k;主程序: int main() int i , rt, sum; build(rt);/ 創(chuàng)建最優(yōu)二叉樹 for (i=1; i=n; i+) / 計(jì)算各葉結(jié)點(diǎn)到根的距離pathi = findpath(i);sum = 0;for (i=1; i=n; i+) / 累加每個(gè)葉節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度sum += hti.data*pathi;cout sum endl; return 0;測(cè)試數(shù)據(jù)：輸入：57 5 2 4 6輸出：543、哈夫曼編碼使用頻率高的采用短的的編碼,則總的編碼長(zhǎng)度便可減少.例如:在某通訊中只使用abcd四種字符,其出現(xiàn)頻率分別為:0.4,0.3,0.2,0.1。請(qǐng)進(jìn)行哈夫曼編碼。使通訊碼盡可能的短 并寫出信息：bbdaac的編碼。1.給定一個(gè)整數(shù)集合3，5，6，9，12，下列二叉樹哪個(gè)是該整數(shù)集合對(duì)應(yīng)的霍夫曼（Huffman）樹。 （ ）2、已知如圖所示的哈夫曼樹，那么電文CDAA的編碼是 A 110100 B 11011100 C 010110111 D 11111100 3、若以4，5，6，7