資料結構系列 - 哈夫曼樹
1．樹的路徑長度
樹的路徑長度是從樹根到樹中每一結點的路徑長度之和。在結點數目相同的二叉樹中，完全二叉樹的路徑長度最短。2．樹的帶權路徑長度(Weighted Path Length of Tree，簡記為WPL)
結點的權：在一些應用中，賦予樹中結點的一個有某種意義的實數。
結點的帶權路徑長度：結點到樹根之間的路徑長度與該結點上權的乘積。
樹的帶權路徑長度(Weighted Path Length of Tree)：定義為樹中所有葉結點的帶權路徑長度之和，通常記為：
其中：
n表示葉子結點的數目
w i 和l i 分別表示葉結點k i 的權值和根到結點k i 之間的路徑長度。
樹的帶權路徑長度亦稱為樹的代價。
3．最優二叉樹或哈夫曼樹
在權為w l ，w 2 ，…，w n 的n個葉子所構成的所有二叉樹中，帶權路徑長度最小(即代價最小)的二叉樹稱為 最優二叉樹 或 哈夫曼樹 。【例】給定4個葉子結點a，b，c和d，分別帶權7，5，2和4。構造如下圖所示的三棵二叉樹(還有許多棵)，它們的帶權路徑長度分別為：
(a)WPL=7*2+5*2+2*2+4*2=36
(b)WPL=7*3+5*3+2*1+4*2=46
(c)WPL=7*1+5*2+2*3+4*3=35
其中(c)樹的WPL最小，可以驗證，它就是哈夫曼樹。
注意：
① 葉子上的權值均相同時，完全二叉樹一定是最優二叉樹，否則完全二叉樹不一定是最優二叉樹。
② 最優二叉樹中，權越大的葉子離根越近。
③ 最優二叉樹的形態不唯一，WPL最小。
4．哈夫曼演算法
哈夫曼首先給出了對於給定的葉子數目及其權值構造最優二叉樹的方法，故稱其為哈夫曼演算法。其基本思想是：(1)根據給定的n個權值w l ，w 2 ，…，w n 構成n棵二叉樹的森林F={T 1 ，T 2 ，…，T n }，其中每棵二叉樹T i 中都只有一個權值為w i 的根結點，其左右子樹均空。
(2)在森林F中選出兩棵根結點權值最小的樹(當這樣的樹不止兩棵樹時，可以從中任選兩棵)，將這兩棵樹合併成一棵新樹，為了保證新樹仍是二叉樹，需要增加一個新結點作為新樹的根，並將所選的兩棵樹的根分別作為新根的左右孩子(誰左，誰右無關緊要)，將這兩個孩子的權值之和作為新樹根的權值。
(3)對新的森林F重複(2)，直到森林F中只剩下一棵樹為止。這棵樹便是哈夫曼樹。
注意：
① 初始森林中的n棵二叉樹，每棵樹有一個孤立的結點，它們既是根，又是葉子
② n個葉子的哈夫曼樹要經過n-1次合併，產生n-1個新結點。最終求得的哈夫曼樹中共有2n-1個結點。
③ 哈夫曼樹是嚴格的二叉樹，沒有度數為1的分支結點。
5．哈夫曼樹的儲存結構及哈夫曼演算法的實現
（1） 哈夫曼樹的儲存結構
用一個大小為2n-1的向量來儲存哈夫曼樹中的結點，其儲存結構為：
#define n 100 //葉子數目
#define m 2*n-1//樹中結點總數
typedef struct { //結點型別
float weight； //權值，不妨設權值均大於零
int lchild，rchild，parent； //左右孩子及雙親指標
}HTNode；
typedef HTNode HuffmanTree[m]； //HuffmanTree是向量型別
注意：
因為C語言陣列的下界為0，故用-1表示空指標。樹中某結點的lchild、rchild和parent不等於-1時，它們分別是該結點的左、右孩子和雙親結點在向量中的下標。
這裡設定parent域有兩個作用：其一是使查詢某結點的雙親變得簡單；其二是可通過判定parent的值是否為-1來區分根與非根結點。
（2）哈夫曼演算法的簡要描述
在上述儲存結構上實現的哈夫曼演算法可大致描述為(設T的型別為HuffmanTree)：
(1)初始化
將T[0．．m-1]中2n-1個結點裡的三個指標均置為空(即置為-1)，權值置為0。
(2)輸人
讀人n個葉子的權值存於向量的前n個分量(即T[0．．n-1])中。它們是初始森林中n個孤立的根結點上的權值。
(3)合併
對森林中的樹共進行n-1次合併，所產生的新結點依次放人向量T的第i個分量中(n≤i≤m-1)。每次合併分兩步：
①在當前森林T[0．．i-1]的所有結點中，選取權最小和次小的兩個根結點[p1]和T[p2]作為合併物件，這裡0≤p1，p2≤i-1。
② 將根為T[p1]和T[p2]的兩棵樹作為左右子樹合併為一棵新的樹，新樹的根是新結點T[i]。具體操作：
將T[p1]和T[p2]的parent置為i，
將T[i]的lchild和rchild分別置為p1和p2
新結點T[i]的權值置為T[p1]和T[p2]的權值之和。
注意：
合併後T[pl]和T[p2]在當前森林中已不再是根，因為它們的雙親指標均已指向了T[i]，所以下一次合併時不會被選中為合併物件。
（3）哈夫曼演算法的求精
void CreateHuffmanTree(HuffmanTree T)
{//構造哈夫曼樹，T[m-1]為其根結點
int i，p1，p2；
InitHuffmanTree(T)； //將T初始化
InputWeight(T)； //輸入葉子權值至T[0．．n-1]的weight域
for(i=n；i<m；i++){//共進行n-1次合併，新結點依次存於T[i]中
SelectMin(T，i-1，&p1，&p2)；
//在T[0．．i-1]中選擇兩個權最小的根結點，其序號分別為p1和p2
T[p1].parent=T[p2].parent=i；
TIi].1child=p1； //最小權的根結點是新結點的左孩子
T[j].rchild=p2； //次小權的根結點是新結點的右孩子
T[i].weight=T[p1].weight+T[p2].weight；
} // end for
}
6． 編碼和解碼
資料壓縮過程稱為編碼。即將檔案中的每個字元均轉換為一個惟一的二進位制位串。資料解壓過程稱為解碼。即將二進位制位串轉換為對應的字元。
7． 等長編碼方案和變長編碼方案
給定的字符集C，可能存在多種編碼方案。
（1） 等長編碼方案
等長編碼方案將給定字符集C中每個字元的碼長定為[lg|C|]，|C|表示字符集的大小。
【例】設待壓縮的資料檔案共有100000個字元，這些字元均取自字符集C={a，b，c，d，e，f}，等長編碼需要三位二進位制數字來表示六個字元，因此，整個檔案的編碼長度為300000位。
（2）變長編碼方案
變長編碼方案將頻度高的字元編碼設定短，將頻度低的字元編碼設定較長。
【例】設待壓縮的資料檔案共有100000個字元，這些字元均取自字符集C={a，b，c，d，e，f}，其中每個字元在檔案中出現的次數(簡稱頻度)見表6.5。
表6.5 字元編碼問題
-----------------------------------------------------------------
字元 a b c d e f
頻度（單位：千次） 45 13 12 16 9 5
定長編碼 000 001 010 011 100 101
變長編碼 0 101 100 111 1101 1100
-----------------------------------------------------------------
根據計算公式：
(45*1+13*3+12*3+16*3+9*4+584)*1000=224000
整個檔案被編碼為224000位，比定長編碼方式節約了約25％的儲存空間。
注意：
變長編碼可能使解碼產生二義性。產生該問題的原因是某些字元的編碼可能與其他字元的編碼開始部分(稱為字首)相同。
【例】設E、T、W分別編碼為00、01、0001，則解碼時無法確定資訊串0001是ET還是W。
8． 字首碼方案
對字符集進行編碼時，要求字符集中任一字元的編碼都不是其它字元的編碼的字首，這種編碼稱為字首(編)碼。
注意：
等長編碼是字首碼
9．最優字首碼
平均碼長或檔案總長最小的字首編碼稱為最優的字首碼。最優的字首碼對檔案的壓縮效果亦最佳。
Line"/>
其中：
p i 為第i個字元得概率，
l i 為碼長
【例】若將表6.5所示的檔案作為統計的樣本，則a至f六個字元的概率分別為0.45，0.13，0.12，0.16，0.09，0.05，對變長編碼求得的平均碼長為2.24，優於定長編碼(平均碼長為3)。
利用哈夫曼樹很容易求出給定字符集及其概率(或頻度)分佈的最優字首碼。哈夫曼編碼正是一種應用廣泛且非常有效的資料壓縮技術。該技術一般可將資料檔案壓縮掉20％至90％，其壓縮效率取決於被壓縮檔案的特徵。
10． 具體做法
（1）用字元c i 作為葉子，p i 或f i 做為葉子c i 的權，構造一棵哈夫曼樹，並將樹中左分支和右分支分別標記為0和1；（2）將從根到葉子的路徑上的標號依次相連，作為該葉子所表示字元的編碼。該編碼即為最優字首碼（也稱哈夫曼編碼）。
11． 哈夫曼編碼為最優字首碼
由哈夫曼樹求得編碼為最優字首碼的原因：
① 每個葉子字元c i 的碼長恰為從根到該葉子的路徑長度l i ，平均碼長(或檔案總長)又是二叉樹的帶權路徑長度WPL。而哈夫曼樹是WPL最小的二叉樹，因此編碼的平均碼長(或檔案總長)亦最小。
② 樹中沒有一片葉子是另一葉子的祖先，每片葉子對應的編碼就不可能是其它葉子編碼的字首。即上述編碼是二進位制的字首碼。
12． 求哈夫曼編碼的演算法
（1）思想方法
給定字符集的哈夫曼樹生成後，求哈夫曼編碼的具體實現過程是：依次以葉子T[i](0≤i≤n-1)為出發點，向上回溯至根為止。上溯時走左分支則生成程式碼0，走右分支則生成程式碼1。
注意：
① 由於生成的編碼與要求的編碼反序，將生成的程式碼先從後往前依次存放在一個臨時向量中，並設一個指標start指示編碼在該向量中的起始位置（start初始時指示向量的結束位置）。
② 當某字元編碼完成時，從臨時向量的start處將編碼複製到該字元相應的位串bits中即可。
③ 因為字符集大小為n，故變長編碼的長度不會超過n，加上一個結束符'\0'，bits的大小應為n+1。
（2）字符集編碼的儲存結構及其演算法描述
typedef struct {
char ch； //儲存字元
char bits[n+1]； //存放編碼位串
}CodeNode；
typedef CodeNode HuffmanCode[n]；
void CharSetHuffmanEncoding(HuffmanTree T，HuffmanCode H)
{//根據哈夫曼樹T求哈夫曼編碼表H
int c，p，i;//c和p分別指示T中孩子和雙親的位置
char cd[n+1]； //臨時存放編碼
int start； //指示編碼在cd中的起始位置
cd[n]='\0'； //編碼結束符
for(i=0，i<n，i++){ //依次求葉子T[i]的編碼
H[i].ch=getchar()；//讀入葉子T[i]對應的字元
start=n； //編碼起始位置的初值
c=i； //從葉子T[i]開始上溯
while((p=T[c].parent)>=0){//直至上溯到T[c]是樹根為止
//若T[c]是T[p]的左孩子，則生成程式碼0；否則生成程式碼1
cd[--start]=(T[p).1child==C)?'0'：'1'；
c=p； //繼續上溯
}
strcpy(H[i].bits，&cd[start])； //複製編碼位串
}//endfor
}//CharSetHuffmanEncoding
有了字符集的哈夫曼編碼表之後，對資料檔案的編碼過程是：依次讀人檔案中的字元c，在哈夫曼編碼表H中找到此字元，若H[i].ch=c，則將字元c轉換為H[i].bits中存放的編碼串。
對壓縮後的資料檔案進行解碼則必須藉助於哈夫曼樹T，其過程是：依次讀人檔案的二進位制碼，從哈夫曼樹的根結點(即T[m-1])出發，若當前讀人0，則走向左孩子，否則走向右孩子。一旦到達某一葉子T[i]時便譯出相應的字元H[i].ch。然後重新從根出發繼續譯碼，直至檔案結束。