電子發燒友App
哈夫曼樹中的名詞意思
樹的權值：每個樹節點所在的那個數字。
路徑：兩個節點之間所經過的分支。
路徑長度： 某一路徑上的分支條數。
節點帶權路徑長度： 節點的權值*該節點的路徑長度。
樹帶權路徑長度：所有葉子節點的帶全路徑長度之和。
樹帶權路徑長度：所有葉子節點的帶全路徑長度之和。
1、基本概念
a、路徑和路徑長度
若在一棵樹中存在著一個結點序列 k1，k2，……，kj， 使得 ki是ki+1 的雙親（1《=i《j），則稱此結點序列是從 k1 到 kj 的路徑。
從 k1 到 kj 所經過的分支數稱為這兩點之間的路徑長度，它等于路徑上的結點數減1.
b、結點的權和帶權路徑長度
在許多應用中，常常將樹中的結點賦予一個有著某種意義的實數，我們稱此實數為該結點的權，（如下面一個樹中的藍色數字表示結點的權）
結點的帶權路徑長度規定為從樹根結點到該結點之間的路徑長度與該結點上權的乘積。
c、樹的帶權路徑長度
樹的帶權路徑長度定義為樹中所有葉子結點的帶權路徑長度之和，公式為：
其中，n表示葉子結點的數目，wi 和 li 分別表示葉子結點 ki 的權值和樹根結點到 ki 之間的路徑長度。
如下圖中樹的帶權路徑長度 WPL = 9 x 2 + 12 x 2 + 15 x 2 + 6 x 3 + 3 x 4 + 5 x 4 = 122
d、哈夫曼樹
哈夫曼樹又稱最優二叉樹。它是 n 個帶權葉子結點構成的所有二叉樹中，帶權路徑長度 WPL 最小的二叉樹。
如下圖為一哈夫曼樹示意圖。
哈夫曼樹的構造
根據哈弗曼樹的定義，一棵二叉樹要使其WPL值最小，必須使權值越大的葉子結點越靠近根結點，而權值越小的葉子結點越遠離根結點。
哈弗曼依據這一特點提出了一種構造最優二叉樹的方法，其基本思想如下：
下面演示了用Huffman算法構造一棵Huffman樹的過程：
假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 w1、w2、…、wn，則哈夫曼樹的構造規則為：
（1） 將w1、w2、…，wn看成是有n 棵樹的森林（每棵樹僅有一個結點）；
（2） 在森林中選出兩個根結點的權值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；
（3）從森林中刪除選取的兩棵樹，并將新樹加入森林；
（4）重復（2）、（3）步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。
如：對 下圖中的六個帶權葉子結點來構造一棵哈夫曼樹，步驟如下：
注意：為了使得到的哈夫曼樹的結構盡量唯一，通常規定生成的哈夫曼樹中每個結點的左子樹根結點的權小于等于右子樹根結點的權。
具體算法如下：
//2、根據數組 a 中 n 個權值建立一棵哈夫曼樹，返回樹根指針
struct BTreeNode* CreateHuffman（ElemType a［］， int n）
{
int i， j;
struct BTreeNode **b， *q;
b = malloc（n*sizeof（struct BTreeNode））;
for （i = 0; i 《 n; i++） //初始化b指針數組，使每個指針元素指向a數組中對應的元素結點
{
b［i］ = malloc（sizeof（struct BTreeNode））;
b［i］-》data = a［i］;
b［i］-》left = b［i］-》right = NULL;
}
for （i = 1; i 《 n; i++）//進行 n-1 次循環建立哈夫曼樹
{
//k1表示森林中具有最小權值的樹根結點的下標，k2為次最小的下標
int k1 = -1， k2;
for （j = 0; j 《 n; j++）//讓k1初始指向森林中第一棵樹，k2指向第二棵
{
if （b［j］ ！= NULL && k1 == -1）
{
k1 = j;
continue;
}
if （b［j］ ！= NULL）
{
k2 = j;
break;
}
}
for （j = k2; j 《 n; j++）//從當前森林中求出最小權值樹和次最小
{
if （b［j］ ！= NULL）
{
if （b［j］-》data 《 b［k1］-》data）
{
k2 = k1;
k1 = j;
}
else if （b［j］-》data 《 b［k2］-》data）
k2 = j;
}
}
//由最小權值樹和次最小權值樹建立一棵新樹，q指向樹根結點
q = malloc（sizeof（struct BTreeNode））;
q-》data = b［k1］-》data + b［k2］-》data;
q-》left = b［k1］;
q-》right = b［k2］;
b［k1］ = q;//將指向新樹的指針賦給b指針數組中k1位置
b［k2］ = NULL;//k2位置為空
}
free（b）; //刪除動態建立的數組b
return q; //返回整個哈夫曼樹的樹根指針
}
哈夫曼樹的在編碼中的應用
在電文傳輸中，需要將電文中出現的每個字符進行二進制編碼。在設計編碼時需要遵守兩個原則：
（1）發送方傳輸的二進制編碼，到接收方解碼后必須具有唯一性，即解碼結果與發送方發送的電文完全一樣；
（2）發送的二進制編碼盡可能地短。下面我們介紹兩種編碼的方式。
1. 等長編碼
這種編碼方式的特點是每個字符的編碼長度相同（編碼長度就是每個編碼所含的二進制位數）。假設字符集只含有4個字符A，B，C，D，用二進制兩位表示的編碼分別為00，01，10，11。若現在有一段電文為：ABACCDA，則應發送二進制序列：00010010101100，總長度為14位。當接收方接收到這段電文后，將按兩位一段進行譯碼。這種編碼的特點是譯碼簡單且具有唯一性，但編碼長度并不是最短的。
2. 不等長編碼
在傳送電文時，為了使其二進制位數盡可能地少，可以將每個字符的編碼設計為不等長的，使用頻度較高的字符分配一個相對比較短的編碼，使用頻度較低的字符分配一個比較長的編碼。例如，可以為A，B，C，D四個字符分別分配0，00，1，01，并可將上述電文用二進制序列：000011010發送，其長度只有9個二進制位，但隨之帶來了一個問題，接收方接到這段電文后無法進行譯碼，因為無法斷定前面4個0是4個A，1個B、2個A，還是2個B，即譯碼不唯一，因此這種編碼方法不可使用。
因此，為了設計長短不等的編碼，以便減少電文的總長，還必須考慮編碼的唯一性，即在建立不等長編碼時必須使任何一個字符的編碼都不是另一個字符的前綴，這宗編碼稱為前綴編碼（prefix code）
（1）利用字符集中每個字符的使用頻率作為權值構造一個哈夫曼樹；
（2）從根結點開始，為到每個葉子結點路徑上的左分支賦予0，右分支賦予1，并從根到葉子方向形成該葉子結點的編碼
例題：
假設一個文本文件TFile中只包含7個字符{A，B，C，D，E，F，G}，這7個字符在文本中出現的次數為{5，24，7，17，34，5，13}
利用哈夫曼樹可以為文件TFile構造出符合前綴編碼要求的不等長編碼
具體做法：
1. 將TFile中7個字符都作為葉子結點，每個字符出現次數作為該葉子結點的權值
2. 規定哈夫曼樹中所有左分支表示字符0，所有右分支表示字符1，將依次從根結點到每個葉子結點所經過的分支的二進制位的序列作為該
結點對應的字符編碼
3. 由于從根結點到任何一個葉子結點都不可能經過其他葉子，這種編碼一定是前綴編碼，哈夫曼樹的帶權路徑長度正好是文件TFile編碼的總長度
通過哈夫曼樹來構造的編碼稱為哈弗曼編碼（huffman code）
工商網監
評論