壹、 基本術語
1. 路徑與路徑長度
若在壹棵樹中存在壹個結點序列 k1, k2, …., kj ，使得kj是kj+1的雙親（1<=i<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最小的二叉樹。
例如：有四個葉結點a，b，c，d，分別帶權為9，4，5，2，可以構成三棵不同的二叉樹（當然可以構成更多的二叉樹）見下圖：
9 4 5 2 WPL=（9+4+5+2）*2=40
4
2
5 9
WPL=（9+5）*3+2*2+4*1=50
4
2
5 9
WPL=（9+5）*3+2*2+4*1=50
9
5
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 2 合並權值為4
3 6 8 5
3 6 8 5 4
2 2
選出兩個權值最小的二叉樹的組成壹棵二叉樹
7 6 8 5
3
2 2
選出兩個權值最小的二叉樹的組成壹棵二叉樹
7 11 8
3
5 6
2 2
選出兩個權值最小的二叉樹的組成壹棵二叉樹
15 11
8
5 6
3
2 2
選出兩個權值最小的二叉樹的組成壹棵二叉樹（最終的哈夫曼樹）
8
5 6
3
2 2
WPL=（2+2）*4+3*3+（5+6+8）*2=16+9+38=63
作業：P221/9