壹.基本術語
1.路徑和路徑長度
如果有節點序列K1，K2、...，kj在壹棵樹上，這樣KJ就是KJ+1(1 < = I & lt；j)，節點序列稱為從k1到kj的路徑(例如，從樹中的壹個節點到它的壹個祖先或它的壹個後代的壹系列連續的節點序列稱為路徑)。因為樹中每個節點只有壹個父節點，所以它是兩個節點之間的唯壹路徑，從k1到kj的分支數稱為這兩點之間的路徑長度。等於節點數-1。
如:從節點A到節點j的節點順序
列為a，b，e，j。
路徑長度為3。
8 10
4 5 3
2.節點權重和加權路徑長度
如果根據需要給樹中的壹個節點賦予壹個具有壹定意義的實數，則稱為該節點的權，該節點的加權路徑長度定義為從根節點到該節點的路徑長度乘以該節點的權的乘積。
3.樹的加權路徑長度
樹的加權路徑長度定義為樹中所有葉節點的加權路徑長度之和，通常記錄為:
n
WPL=∑ wili wi和li分別表示葉節點ki和ki到的權重。
I=1根節點的路徑長度
比如上圖中的WPL =(4+5+3)* 3+(8+10)* 2 = 72。
4.霍夫曼樹
哈夫曼樹，也稱最優二叉樹，是由n個加權葉節點組成的所有二叉樹中，加權路徑長度WPL最短的二叉樹。
比如有4個葉子節點A、B、C、D，權重分別為9、4、5、2，可以形成3棵不同的二叉樹(當然也可以形成更多的二叉樹)，如下圖所示:
9 4 5 2 WPL=(9+4+5+2)*2=40
四
2
5 9
WPL=(9+5)*3+2*2+4*1=50
四
2
5 9
WPL=(9+5)*3+2*2+4*1=50
九
五
4 2
WPL=9*1+5*2+(2+4)*3=37
可以證明最後壹棵二叉樹是霍夫曼樹。
第二，構建霍夫曼樹
1.把N個葉節點做成獨立的N棵二叉樹，每棵二叉樹只有壹個根節點。
2.選擇兩個權重最小的二叉樹合並成壹個二叉樹，用這兩個二叉樹的權重之和作為這個二叉樹的權重，來抵消原來的兩個二叉樹。
3.重復2，直到只剩下壹棵二叉樹。
比如有6個權重分別為3，6，8，5，2，2的加權葉節點，構造壹棵霍夫曼樹，計算WPL的結果。
1.構建6棵二叉樹
3 6 8 5 2 2
選擇兩個權重最小的二叉樹組成二叉樹。
2 2合並權重為4。
3 6 8 5
3 6 8 5 4
2 2
選擇兩個權重最小的二叉樹組成二叉樹。
7 6 8 5
三
2 2
選擇兩個權重最小的二叉樹組成二叉樹。
7 11 8
三
5 6
2 2
選擇兩個權重最小的二叉樹組成二叉樹。
15 11
八
5 6
三
2 2
選擇兩個權重最小的二叉樹組成壹棵二叉樹(最終的霍夫曼樹)
八
5 6
三
2 2
WPL =(2+2)* 4+3 * 3+(5+6+8)* 2 = 16+9+38 = 63
作業:P221/9