哈夫曼樹的存儲結構

1. 最優二叉樹

最優二叉樹概念

．樹的路徑長度 樹的路徑長度是從樹根到樹中每一結點的路徑長度之和 在結點數目相同的二叉樹中 完全二叉樹的路徑長度最短

．樹的帶權路徑長度(Weighted Path Length of Tree 簡記為WPL) 結點的權 在一些應用中 賦予樹中結點的一個有某種意義的實數 結點的帶權路徑長度 結點到樹根之間的路徑長度與該結點上權的乘積 樹的帶權路徑長度(Weighted Path Length of Tree) 定義為樹中所有葉結點的帶權路徑長度之和 通常記為 其中 n表示葉子結點的數目w _{i和l i分別表示葉結點k i的權值和根到結點ki之間的路徑長度 樹的帶權路徑長度亦稱為樹的代價}

．最優二叉樹或哈夫曼樹 在權為wl w … wn的n個葉子所乎困構成的所有二叉樹中 帶權路徑長度最小(即代價最小)的二叉樹稱為最優二叉樹或哈夫曼樹 【例】給定 個葉子結點a b c和d 分別帶權 和 構造如下圖所示的三棵二叉樹(還有許多棵) 它們的帶權路徑長度分別為 (a)WPL= * + * + * + * = (b)WPL= * + * + * + * = (c)WPL= * + * + * + * = 其中(c)樹的WPL最小 可以驗證 它就是哈夫曼樹

注意 ① 葉子上的權值均相同時 完全二叉樹一定是最優二叉樹 否則完全二叉樹不一定是最優二叉樹 ② 最優二叉樹中 權越大的葉子離根越近 ③ 最優二叉樹的形態不唯一 WPL最小

構造最優二叉樹

．哈夫曼演算法 哈夫曼首先給出了對於給定的葉子數目及其權值構造最優二叉樹的方法 故稱其為哈夫曼演算法 其基本思想是 ( )根據給定的n個權值w _{l w … wn構成n棵二叉樹的森林F={T T … T n} 其中每棵二叉樹T i中都只有一個權值為w i的根結點 其左右子樹均空 ( )在森林F中選出兩棵根結點權值最小的樹(當這樣的樹不止兩棵樹時 可以從中任選兩棵) 將這兩棵樹合並成一棵新樹 為了保證新樹仍是二叉樹 需要增加一個新結點作為新樹的根 並將所選的兩棵樹的根分別作為新根的左右孩子(誰左 誰右無關緊要) 將這兩個孩子的權值之和作為新樹根的權值 ( )對新的森林F重復( ) 直到森林F中只剩下一棵樹為止 這棵樹便是哈夫曼樹 用哈夫曼演算法構造哈夫曼樹的過程見【動畫演示】 注意 ① 初始森林中的n棵二叉樹 每棵樹有一個孤立的結點 它們既是根 又是葉子② n個葉子的哈夫曼樹要經過n 次合並 產生n 個新結點 最終求得的哈夫曼樹 *** 有 n 個結點 ③ 哈夫曼樹是嚴格的二叉樹 沒有度數為 的分支結點 ．哈夫曼樹的存儲結構及哈夫曼演算法的實現 （ ） 哈夫曼樹的存儲結構 用一個大小為 n 的向量來存儲哈夫曼樹中的結點 其存儲結構為 #define n //葉子數目 #define m *n //樹中結點總數 typedef struct { //結點類型 float weight //權值 不妨設權值均大於零 int lchild rchild parent //左右孩歲橡念子及雙親指針 }HTNode typedef HTNode HuffmanTree[m] //HuffmanTree是向量類型 注意 因為C語言數組的下界為 故用 表示空指針 樹中某結點的lchild rchild和parent不等於 時 它們分別是該結點的左 右孩子和雙親結點在向量中的下標 這里設置parent域有兩個作用 其一是使查找某結點的雙親變得簡單 其二是可通過判定parent的值是否為 來區分根與非根結點}

（ ）哈夫曼演算法的簡要描述 在上述存儲結構上實現的哈夫曼演算法可如跡大致描述為(設T的類型為HuffmanTree) ( )初始化 將T[ ．．m ]中 n 個結點里的三個指針均置為空(即置為 ) 權值置為 ( )輸人 讀人n個葉子的權值存於向量的前n個分量(即T[ ．．n ])中 它們是初始森林中n個孤立的根結點上的權值 ( )合並 對森林中的樹共進行n 次合並 所產生的新結點依次放人向量T的第i個分量中(n≤i≤m ) 每次合並分兩步 ①在當前森林T[ ．．i ]的所有結點中 選取權最小和次小的兩個根結點[p ]和T[p ]作為合並對象 這里 ≤p p ≤i ② 將根為T[p ]和T[p ]的兩棵樹作為左右子樹合並為一棵新的樹 新樹的根是新結點T[i] 具體操作 將T[p ]和T[p ]的parent置為i 將T[i]的lchild和rchild分別置為p 和p 新結點T[i]的權值置為T[p ]和T[p ]的權值之和 注意 合並後T[pl]和T[p ]在當前森林中已不再是根 因為它們的雙親指針均已指向了T[i] 所以下一次合並時不會被選中為合並對象 哈夫曼演算法模擬演示過程【參見動畫模擬】

（ ）哈夫曼演算法的求精 void CreateHuffmanTree(HuffmanTree T) {//構造哈夫曼樹 T[m ]為其根結點 int i p p InitHuffmanTree(T) //將T初始化 InputWeight(T) //輸入葉子權值至T[ ．．n ]的weight域 for(i=n i<m i++){//共進行n 次合並 新結點依次存於T[i]中 SelectMin(T i &p &p ) //在T[ ．．i ]中選擇兩個權最小的根結點 其序號分別為p 和p T[p ] parent=T[p ] parent=i TIi] child=p //最小權的根結點是新結點的左孩子 T[j] rchild=p //次小權的根結點是新結點的右孩子 T[i] weight=T[p ] weight+T[p ] weight } // end for }上述演算法中調用的三個函數【參見練習】 【例】以 個權值 為例 執行CreateHuffmanTree求最優二叉樹的過程【參見動畫模擬】

2. 哈夫曼演算法中頻度建樹應該用什麼排序

最優二叉樹概念

1．樹的路徑長度
樹的路徑長度是從樹根到樹中每一結點的路徑長度之和。在結點數目相同的二叉樹中，完全二叉樹的路徑長度最短。

2．樹的帶權路徑長度(Weighted Path Length of Tree，簡記為WPL)
結點的權：在一些應用中，賦予樹中結點的一個有某種意義的實數。
結點的帶權路徑長度：結點到樹根之間的路徑長度與該結點上權的乘積。
樹的帶權路徑長度(Weighted Path Length of Tree)：定義為樹中所有葉結點的帶權路徑長度之和，通常記為：
【數據結構】樹：哈夫曼樹及其應用 - 八月照相館 - 八月照相館
其中：

n表示葉子結點的數目
wi和li分別表示葉結點ki的權值和根到結點ki之間的路徑長度。
樹的帶權路徑長度亦稱為樹的代價。

3．最優二叉樹或哈夫曼樹
在權為wl，w2，…，wn的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最小

構造最優二叉樹

1．哈夫曼演算法
哈夫曼首先給出了對於給定的葉子數目及其權值構造最優二叉樹的方法，故稱其為哈夫曼演算法。其基本思想是：
(1)根據給定的n個權值wl，w2，…，wn構成n棵二叉樹的森林F={T1，T2，…，Tn}，其中每棵二叉樹Ti中都只有一個權值為wi的根結點，其左右子樹均空。
(2)在森林F中選出兩棵根結點權值最小的樹(當這樣的樹不止兩棵樹時，可以從中任選兩棵)，將這兩棵樹合並成一棵新樹，為了保證新樹仍是二叉樹，需要增加一個新結點作為新樹的根，並將所選的兩棵樹的根分別作為新根的左右孩子(誰左，誰右無關緊要)，將這兩個孩子的權值之和作為新樹根的權值。
(3)對新的森林F重復(2)，直到森林F中只剩下一棵樹為止。這棵樹便是哈夫曼樹。
用哈夫曼演算法構造哈夫曼樹的過程見【動畫演示】。
注意：
① 初始森林中的n棵二叉樹，每棵樹有一個孤立的結點，它們既是根，又是葉子
② n個葉子的哈夫曼樹要經過n-1次合並，產生n-1個新結點。最終求得的哈夫曼樹中共有2n-1個結點。
③ 哈夫曼樹是嚴格的二叉樹，沒有度數為1的分支結點。

2．哈夫曼樹的存儲結構及哈夫曼演算法的實現
（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]，所以下一次合並時不會被選中為合並對象。