【正文】 堆 ,付出的代價為這兩堆石子的重量之和 ,如果把這 n堆石子最后合并成 1堆石子 ,怎樣合并才能使付出的代價最小 ,求出最小的代價 . 七 、 最優(yōu)二叉樹 (哈夫曼樹 ) 顯然圖 (D)所示的合并方法付出的代價最小 :54 5*2+（ 2+4） *3+（ 6+7） *2=54 例如 n=5,重量 分別為 6。 2 4 6 5 11 6 7 13 24 (D) L=6+11+13+24=54 最優(yōu)二叉樹的定義 在具有 n個帶權葉結點的二叉樹中 ， 使所有葉結點的帶權路徑長度之和 （ 即二叉樹的帶權路徑長度 ） 為最小的二叉樹 ，稱為最優(yōu)二叉樹 （ 又稱最優(yōu)搜索樹或哈夫曼樹 ） ， 即最優(yōu)二叉樹使 （ wk—第 k個葉結點的權值； pk—第 k個葉結點的帶權路徑長度）達到最小。 最優(yōu)二叉樹的構造方法 假定給出 n個結點 ki(i=1‥ n)， 其權值分別為 wi(i=1‥ n)。 要構造以此 n個結點為葉結點的最優(yōu)二叉樹 ， 其構造方法如下： 首先 , 將 給 定 的 n 個 結 點 構 成 n 棵 二 叉 樹 的 集 合F={T1,T2,…… ,Tn}。 其中每棵二叉樹 Ti中只有一個權值為 wi的根結點 ki， 其左 、 右子樹均為空 。 然后做以下兩步 ⑴ .在 F中選取根結點權值最小的兩棵二叉樹作為左右子樹 ,構造一棵新的二叉樹 ,并且置新的二叉樹的根結點的權值為其左 、 右子樹根結點的權值之和； ⑵ .在 F中刪除這兩棵二叉樹 ,同時將新得到的二叉樹加入 F中； 重復 ⑴ 、 ⑵ ,直到在 F中只含有一棵二叉樹為止 。 這棵二叉樹便是最優(yōu)二叉樹 。 以上構造最優(yōu)二叉樹的方法稱為哈夫曼 （ huffmann） 算法 。 例如：給定五個結點 k1， k2， k3， k4， k5， 其權值分別為 1 1 1 23。 構造最優(yōu)二叉樹的過程如下： ⑴構造初始集合 F， F中各二叉樹根結點的權值分別為 16， 2，18， 16， 23（如下圖）： ⑵ 以具有權值 16及 2的根結點的兩棵二叉樹為左 、 右子樹 ， 構造一棵根權值為 18的新二叉樹 ， 并從 F中刪去這兩棵二叉樹（ 如下圖 ） ： ⑶ 以同樣的方法 ， 得到一個新二叉樹的集合 F， 其根結點的權值分別為 23， 18， 34（ 如下圖 ） ： ⑷ 又得到一個新二叉樹的集合 F， 其根結點的權值分別為34， 41（ 如下圖 ） ： ⑸ 最后得到最優(yōu)二叉樹 （ 如下圖 ） ， 其根結點的權值為 75，結點數(shù)為 2*51=9。 哈夫曼編碼 使用頻率高的采用短的的編碼 ,則總的編碼長度便可減少 . 例如 :在某通訊中只使用 abcd四種字符 ,其出現(xiàn)頻率分別為 :,。請進行哈夫曼編碼。使通訊碼盡可能的短 ,并寫出信息： bbdaac的編碼。 {3， 5， 6， 9， 12}，下列二叉樹哪個是該整數(shù)集合對應的霍夫曼（ Huffman）樹。 （ ） 已知如圖所示的哈夫曼樹，那么電文CDAA的編碼是 [ ] A 110100 B 11011100 C 010110111 D 11111100 若以 {4， 5， 6， 7,8}作為葉子結點的權值構造哈夫曼樹 ， 則其帶權路徑長度是 [ ] A 、 69 B、 70 C 、 73 D、 68 ⑥ (NOIP6)在有 N個葉子節(jié)點的哈夫曼樹中，其節(jié)點總數(shù)為（ ） B. 2N1 C. 2N+1 D. 2N 在最優(yōu)二叉樹中非葉結點的度均為 2， 因此采用順序存儲結構為宜 。 如果帶權葉結點數(shù)為 n個 ， 則最優(yōu)二叉樹的結點數(shù)為 2n1個 。 由此得出最優(yōu)二叉樹的數(shù)據(jù)類型定義 define n 葉結點數(shù)的上限； Int m=2*n1； //最優(yōu)二叉樹的結點數(shù) Struct node //結點類型 { int data； //權值 int prt,lch,rch,lth； //父指針 、 左 、 右指針和路徑長度 } wtype=array[1‥ n] of integer； {n個葉結點權值的類型 } treetype=array[1‥ m] of node； {最優(yōu)二叉樹的數(shù)組類型 } node tree[m]； //其中 tree [1‥ n]為葉結點 ,tree [n+1‥ 2n1]為中間結點 ,根為 tree [2n1] 在最優(yōu)二叉樹的順序存儲結構中前 n個結點為葉結點 。 構造最優(yōu)二叉樹的算法如下： int minn(int h)//在前 h個結點中選擇父指針為 0且權值最小的結點 { ml=∞； for(p=1。p=h。p++) if((tree[p].prt==0)amp。amp。(m1tree[p].data)) //沒有父親結點且較小的結點 {i= p。m1=tree[p].data。} return i。 } void hufm(int w[],node tree[]) { memset(tree,0,sizeof(tree))。//構造初始集合 f for(i=1。i=n。i++)cintree[i].data； for(k=n+1。k=m。k++)//構造最優(yōu)二叉樹生成 n1個新結點 { //計算 k為根的左兒子和右兒子 i= min(k1)。tree[i].prt=k。tree[k].lch= i。 j= min(k1)。 tree[j].prt=k。tree[k].rch= j。 tree[k].data= tree[i].data+tree[j].data； } bt=m； } 計算每一個葉結點的路徑長度 Void ht(int t)//通過前序遍歷計算每一個葉結點的路徑長度 { if(t==m)tree[t].lth=0。 //若結點 t為根 ,則路徑長度為 0。否則結點 t的路徑長度為其父結點的路徑長度 +1 else tree[t].lth=tree[tree[t].prt].lth+1。 if(tree[t].lch!=0){ht(tree[t].lch)。ht(tree[t].rch)。}//分別遞歸左右子樹 } 由此可見 ,葉結點 t（ 1≤t≤n） 的帶權路徑長度即為 : tree[t].lth*tree[t].data。 主 程 序 int main() { cinn。 //輸入葉節(jié)點個數(shù) bt=hufm(w,tree)。//計算最優(yōu)二叉樹 tree和根序號 bt ht(bt)。//計算每一個葉結點的路徑長度 for(i=1。i=n。i++) couttree[i].lth*tree[i].data“ ”。 //輸出每個葉節(jié)點的帶權路徑長度 return 0。 }