哈夫曼樹構造
1．哈夫曼樹的定義
給定n個權值作為n個葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(huffman tree)。
2．哈夫曼樹的構造
假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分别設為 w1,w2,…,wn,則哈夫曼樹的構造規則為：
(1) 将w1,w2,…,wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；
(2) 在森林中選出兩個根結點的權值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；
(3)從森林中删除選取的兩棵樹，并将新樹加入森林；
(4)重複(2)、(3)步，直到森林中隻剩一棵樹為止，該樹即為我們所求得的哈夫曼樹。
下面給出哈夫曼樹的構造過程，假設給定的葉子結點的權分别為1,5,7,3，則構造哈夫曼樹過程如圖所示。 從圖中可知，n 個權值構造哈夫曼樹需n-1次合并，每次合并，森林中的樹數目減1，最後森林中隻剩下一棵樹，即為我們求得的哈夫曼樹。
哈夫曼構造正确性證明。
如上圖，wpl值為3×（1+3）+2×5+1×7=29.
事實上wpl值也是所有非葉子節點的和，即4+9+16=29.
這是可以證明的。
從最底層開始計算，最底層的2個葉節點的根結點的值為葉節點的和，每個根結點都為葉節點的和，也就是說，每個非葉節點的值都是它底下所有的葉節點的和。比如16=1+3+5+7，9=1+3+5。是以把4,9,16這些節點加起來，就相當于底層節點1,3加了3遍，5加了2遍，7加了1遍。即每個值加的遍數就是該值的深度。
又因為根據算法，n個葉子節點所組成的一個集合，每次取走2個最小節點，再加入一個節點，直到隻剩下最後一個節點。是以，新生成的葉子非葉子節點個數必定是n-1個。是以要保證wpl值最小，也就是保證生産的非葉子節點和最小，即生成的節點和值最小。是以每次生成的節點取最小值，即可保證，總的和值是最小的。即wpl值也是最小的。