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

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

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

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

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

6、; int findpath(int i) / 計算葉結點到根的路徑長度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);/ 創建最優二叉樹 for (i=1; i=n; i+) / 計算各葉結點到根的距離pathi = findpath(i);sum = 0;for (i=1; i=n; i+) / 累加每個葉節點的帶權路徑長度sum += hti.data*pathi;cout sum endl; return 0;測試數據：輸入：57 5 2 4 6輸出：543、哈夫曼編碼使用頻率高的采用短的的編碼,則總的編碼長度便可減少.例如:在某通訊中只使用abcd四種字符,其出現頻率分別為:0.4,0.3,0.2,0.1。請進行哈夫曼編碼。使通訊碼盡可能的短 并寫出信息：bbdaac的編碼。1.給定一個整數集合3，5，6，9，12，下列二叉樹哪個是該整數集合對應的霍夫曼（Huffman）樹。 （ ）2、已知如圖所示的哈夫曼樹，那么電文CDAA的編碼是 A 110100 B 11011100 C 010110111 D 11111100 3、若以4，5，6，7