(12)哈夫曼樹及其應用

1、第六章 （續(xù)） 哈夫曼樹及其應用 設有設有1000010000個學生某門課程的考試成績的分布如個學生某門課程的考試成績的分布如 下表所示：下表所示： 一、問題的提出一、問題的提出 分數(shù)05960697079 808990100 學生比例數(shù)0.050.150.400.300.10 學生成績數(shù)據(jù)分布情況表 *問題：現(xiàn)在要編寫程序依次根據(jù)每個學生的成績 打印出該學生的成績等級。 分數(shù)05960697079 808990100 學生比例數(shù)0.050.150.400.300.10 學生成績數(shù)據(jù)分布情況表 方法方法1： a60 打印打印bad“ yes a70 no 打印打印pass yes a80 no

2、 打印打印general yes a90 no 打印打印good yes 打印打印 excellent no5%的學生的學生 15%的學生的學生 40%的學生的學生 30%的學生的學生 10%的學生的學生 共做31500 次比較 讀取一個學生成績a 循環(huán)一萬次 i=1 i=10000 N 結束結束 i = i+1 分數(shù)05960697079 808990100 學生比例數(shù)0.050.150.400.300.10 學生成績數(shù)據(jù)分布情況表 方法方法2： a80 打印打印bad yes a90 no yes no a70 yes no a60 yes no 打印打印 “good 打印打印 excel

3、lent 打印打印pass 打印打印general 5%的學生的學生15%的學生的學生 40%的學生的學生 30%的學生的學生 10%的學生的學生 讀取一個學生成績a 循環(huán)一萬次 i=1 i=10000 N 結束結束 分數(shù)05960697079 808990100 學生比例數(shù)0.050.150.400.300.10 學生成績數(shù)據(jù)分布情況表 方法方法2： a80 打印打印bad yes a90 no yes no a70 yes no a60 yes no 打印打印 “good 打印打印 excellent 打印打印pass 打印打印general 5%的學生的學生15%的學生的學生 40%的學

4、生的學生 30%的學生的學生 10%的學生的學生 共做22000 次比較 讀取一個學生成績a 循環(huán)一萬次 i=1 i=10000 N 結束結束 思考：如何找到一棵最優(yōu)的判斷樹使得編寫 出來的程序的運行時間是最高效的？ 1. 1.哈夫曼樹的哈夫曼樹的有關概念有關概念 結點的路徑長度：結點的路徑長度： 從根結點沿某條路徑到某結點途中所經(jīng)歷的弧的條數(shù)從根結點沿某條路徑到某結點途中所經(jīng)歷的弧的條數(shù) 稱為該結點的路徑長度。稱為該結點的路徑長度。 二、哈夫曼樹及其應用二、哈夫曼樹及其應用 樹的路徑長度：樹的路徑長度： 從根結點到每一個葉子結點的路徑長度之和。從根結點到每一個葉子結點的路徑長度之和。 樹的帶

5、權路徑長度樹的帶權路徑長度(WPL)： 樹中所有葉子結點的帶權路徑長度之和稱為樹的帶權樹中所有葉子結點的帶權路徑長度之和稱為樹的帶權 路徑長度。路徑長度。 結點的帶權路徑長度：結點的帶權路徑長度： 某結點的路徑長度與該結點上的權值的乘積稱為該結某結點的路徑長度與該結點上的權值的乘積稱為該結 點的帶權路徑長度。點的帶權路徑長度。 1. 1.哈夫曼樹的哈夫曼樹的有關概念有關概念 二、哈夫曼樹及其應用二、哈夫曼樹及其應用 實例：實例：已知某二叉樹的四個葉子結點已知某二叉樹的四個葉子結點 a,b,c,d 分別帶權分別帶權7，5，2，4，則可構造出有如下幾，則可構造出有如下幾 種不同形式的二叉樹：種不同

6、形式的二叉樹： a a a 7 7 7 b 5 b 5c 2 d 4 c 2 d 4 b 5 c 2 d 4 樹的帶權路徑長度為： WPL=2*7+2*5+2*2+2*4=36 樹的帶權路徑長度為： WPL=2*4+3*7+3*5+1*2=46 樹的帶權路徑長度為： WPL=1*7+2*5+3*2+3*4=35 1. 1.哈夫曼樹的哈夫曼樹的有關概念有關概念 二、哈夫曼樹及其應用二、哈夫曼樹及其應用 哈夫曼樹的定義： 設有n個葉子結點的二叉樹，其第i個 葉子結點的權值為wi(i=1,2,3,.n),且第i個 葉子結點的路徑長度為li ,則使 WPL=wi*li最小的二叉樹稱為“最優(yōu) 二叉樹”或

7、稱為“哈夫曼樹”。 i=1 n n 2. 2.哈夫曼樹的哈夫曼樹的求解過程求解過程 二、哈夫曼樹及其應用二、哈夫曼樹及其應用 問題： 已知n個葉子的權值為w1,w2,.wn，構 造一棵最優(yōu)二叉樹。 2. 2.哈夫曼樹的哈夫曼樹的求解過程求解過程 二、哈夫曼樹及其應用二、哈夫曼樹及其應用 方法： 步驟步驟1:構造一個具有構造一個具有n棵二叉樹的森林棵二叉樹的森林F=T1,T2,.,Tn， 其中其中Ti是只有一個根結點且根結點的權值為是只有一個根結點且根結點的權值為wi的二叉樹。的二叉樹。 步驟步驟2:在在F中選取兩棵其根結點的權值最小的二叉樹，從中選取兩棵其根結點的權值最小的二叉樹，從F 中刪除

8、這兩棵樹，并以這兩棵二叉樹為左右子樹構造一棵中刪除這兩棵樹，并以這兩棵二叉樹為左右子樹構造一棵 新的二叉樹添加到新的二叉樹添加到F中，該新的二叉樹的根結點的權值為中，該新的二叉樹的根結點的權值為 其左右孩子二叉樹的根結點的權值之和。其左右孩子二叉樹的根結點的權值之和。 步驟步驟3:判斷判斷F中是否只有唯一的一棵二叉樹。若是，則求中是否只有唯一的一棵二叉樹。若是，則求 解過程結束；否則，轉步驟解過程結束；否則，轉步驟2。 2. 2.哈夫曼樹的哈夫曼樹的求解過程求解過程 二、哈夫曼樹及其應用二、哈夫曼樹及其應用 實例：已知有5個葉子結點的權值分別為：5 , 15 , 40 , 30 , 10 ；試

9、畫出一棵相應的哈夫曼樹。 a 40 b 30 c 5 d 10 e 15 15 2. 2.哈夫曼樹的哈夫曼樹的求解過程求解過程 二、哈夫曼樹及其應用二、哈夫曼樹及其應用 實例：已知有5個葉子結點的權值分別為：5 , 15 , 40 , 30 , 10 ；試畫出一棵相應的哈夫曼樹。 a 40 b 30 c 5 d 10 e 15 15 2. 2.哈夫曼樹的哈夫曼樹的求解過程求解過程 二、哈夫曼樹及其應用二、哈夫曼樹及其應用 實例：已知有5個葉子結點的權值分別為：5 , 15 , 40 , 30 , 10 ；試畫出一棵相應的哈夫曼樹。 a 40 b 30 c 5 d 10 e 1515 30 2.

10、 2.哈夫曼樹的哈夫曼樹的求解過程求解過程 二、哈夫曼樹及其應用二、哈夫曼樹及其應用 實例：已知有5個葉子結點的權值分別為：5 , 15 , 40 , 30 , 10 ；試畫出一棵相應的哈夫曼樹。 a 40 b 30 c 5 d 10 e 1515 30 60 2. 2.哈夫曼樹的哈夫曼樹的求解過程求解過程 二、哈夫曼樹及其應用二、哈夫曼樹及其應用 實例：已知有5個葉子結點的權值分別為：5 , 15 , 40 , 30 , 10 ；試畫出一棵相應的哈夫曼樹。 a 40 b 30 c 5 d 10 e 1515 30 60 100 3.3.哈夫曼編碼哈夫曼編碼 二、哈夫曼樹及其應用二、哈夫曼樹及

11、其應用 等長編碼： 以英文字符編碼為例，一般英文字符編碼是采 用7位二進制數(shù)編碼（ASCII碼）。7位二進制數(shù)可 以為27個不同的英文字符編碼。 下面為討論問題簡單起見，假設被編碼的字符 集中只有4個（即22個）不同字符，故只要兩位二 進制數(shù)即可完成編碼。 設這4個不同的字符為A，B，C，D，則可進行 等長編碼如下： 3.3.哈夫曼編碼哈夫曼編碼 二、哈夫曼樹及其應用二、哈夫曼樹及其應用 等長編碼： 設這4個不同的字符為A，B，C，D，則可進行 等長編碼如下： 3.3.哈夫曼編碼哈夫曼編碼 二、哈夫曼樹及其應用二、哈夫曼樹及其應用 等長編碼： 設這4個不同的字符為A，B，C，D，則可進行 等長

12、編碼如下： A: 00 B: 01 C: 10 D: 11 則對于電文“ABACCDA”的二進制電碼為： 00010010101100 總長為14位 譯碼時，兩位一分進行譯碼，可唯一得到電文： ABACCDA 。 3.3.哈夫曼編碼哈夫曼編碼 二、哈夫曼樹及其應用二、哈夫曼樹及其應用 壓縮編碼： 即采用不等長的編碼方案，將“高頻字符”的 編碼設計得盡可能短一些，把最長的編碼留給“低 頻字符”。 例如：對于剛才的4個字符的編碼問題，可以按如 下不等長編碼方案進行編碼： A: 0 B: 00 C: 1 D: 01 問題：譯碼時可能出現(xiàn)多意性，即譯碼不唯一： 則對于電文“ABACCDA”的二進制電碼

13、為： 000011010 總長為9位 3.3.哈夫曼編碼哈夫曼編碼 二、哈夫曼樹及其應用二、哈夫曼樹及其應用 壓縮編碼： 例如：對于剛才的4個字符的編碼問題，可以按如 下不等長編碼方案進行編碼： A: 0 B: 00 C: 1 D: 01 問題：譯碼時可能出現(xiàn)多意性，即譯碼不唯一： 則對于電文“ABACCDA”的二進制電碼為： 000011010 總長為9位 3.3.哈夫曼編碼哈夫曼編碼 二、哈夫曼樹及其應用二、哈夫曼樹及其應用 壓縮編碼： 例如：對于剛才的4個字符的編碼問題，可以按如 下不等長編碼方案進行編碼： A: 0 B: 00 C: 1 D: 01 問題：譯碼時可能出現(xiàn)多意性，即譯碼不

14、唯一。 則對于電文“ABACCDA”的二進制電碼為： 000011010 總長為9位 如000011010中的前4個0的譯碼會有如下幾種不 同譯碼： 0000AAAA；0000ABA；0000BB 思考：如何解 決這一問題？ 問題的關鍵在于編碼 是否為無前綴編碼。 3.3.哈夫曼編碼哈夫曼編碼 二、哈夫曼樹及其應用二、哈夫曼樹及其應用 無前綴壓縮編碼（既哈夫曼編碼）： *思想：利用哈夫曼樹設計出來的不等長的編碼方 案一定是無前綴的。 *方法： 步驟1：將各字符按照其“出現(xiàn)頻率”的統(tǒng)計數(shù)字安排 一個“權值”并作為“葉子”，然后求出相應的哈夫曼樹； 步驟2：樹中各結點到其左孩子的邊上的權值設為0、

15、到 其右孩子的邊上的權值設為1（即所謂左0右1）； 步驟3：從根開始到“葉子”所經(jīng)歷的邊上的數(shù)值的序 列即為該“葉子”所對應的字符的編碼。 三、實例三、實例 已知某通信用電文僅由A、B、C、D這4個字符構成， 其出現(xiàn)的頻率分別為：8、4、6、2，請給出它們的哈夫 曼編碼，要求寫出相應的哈夫曼樹。 解：根據(jù)哈夫曼算法，求得哈夫曼樹如下： 20 812 2 66 4 B D A C 0 1 01 01 從根開始到葉子得各字 符的哈夫曼編碼如下： A :0 B:100 C:11 D:101 則對于電文“ABACCDA”的二 進制電碼為： 0100011111010 總長為13位 三、實例三、實例 補

16、充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 李趙孫周鄭吳王錢A 0 1 2 3 4 5 6 7 8 9 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李趙孫周鄭吳王錢A 0 1 2 3 4 5 6 7 8 9 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李趙 8 孫周鄭吳王錢A 0 1 2 3 4 5 6 7 8 9 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李趙 8 孫周鄭吳王錢 3A 0 1 2 3 4 5 6 7 8 9 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李趙 8 孫 1 周鄭吳王錢 3A 0 1 2 3 4 5

17、 6 7 8 9 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李 4 趙 8 孫 1 周鄭吳王錢 3A 0 1 2 3 4 5 6 7 8 9 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李 4 趙 8 孫 1 周 6 鄭吳王錢 3A 0 1 2 3 4 5 6 7 8 9 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李 4 趙 8 孫 1 周 6 鄭吳 5 王錢 3A 0 1 2 3 4 5 6 7 8 9 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王錢 3A 0 1 2

18、 3 4 5 6 7 8 9 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 9 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 9 在“孫”的前面插入一個 “史”： 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 9 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3 史A 0 1 2 3

19、4 5 6 7 8 9 在“孫”的前面插入一個 “史”： 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 9 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3 史A 0 1 2 3 4 5 6 7 8 9 在“孫”的前面插入一個 “史”： 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 9 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0

20、 錢 3 史 3A 0 1 2 3 4 5 6 7 8 9 在“孫”的前面插入一個 “史”： 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 9 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3 史 3A 0 1 2 3 4 5 6 7 8 9 在“孫”的前面插入一個 “史”： 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 9 2 李 4 趙 8

21、 孫 1 周 6 鄭 7 吳 5 王 0 錢 3 史 3A 0 1 2 3 4 5 6 7 8 9 在“孫”的前面插入一個 “史”： 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 9 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8 9 在“孫”的前面插入一個 “史”： 刪除“周”時表的變化： 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8 9 三、

22、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 9 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8 9 在“孫”的前面插入一個 “史”： 刪除“周”時表的變化： 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8 9 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3

23、 4 5 6 7 8 9 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8 9 在“孫”的前面插入一個 “史”： 刪除“周”時表的變化： 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8 9 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 9 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8

24、 9 在“孫”的前面插入一個 “史”： 刪除“周”時表的變化： 2 李 6 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8 9 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 9 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8 9 在“孫”的前面插入一個 “史”： 刪除“周”時表的變化： 2 李 6 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3

25、A 0 1 2 3 4 5 6 7 8 9 總結：靜態(tài)鏈表在插入和刪除時一般不需要移動元素，僅需要修改 指針即可。但在申請存儲空間時需要一次性申請足夠大的空間。 三、實例三、實例 補充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表 2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 9 靜態(tài)鏈表的結構類型定義： #defined MAXSIZE 1000 / 鏈表的最大尺寸 Typedef struct StaticListNode ElemType data ; /存放表中元素的值 int next ; /指示后繼元素的存放位置 StaticList

26、Node, StaticLinkList MAXSIZE ; /定義一個數(shù)組 四、構造哈夫曼樹并求四、構造哈夫曼樹并求n個字符的哈夫曼編碼之程序個字符的哈夫曼編碼之程序 1.哈夫曼樹的結點的物理結構： weightparentlchildrchild Typedef struct HTNode unsigned int weight ; unsigned int parent, lchild, rchild ; HTNode , * HuffmanTree ; /該指針用以申請數(shù)組時作為數(shù)組名 2.結點物理結構的C語言定義： 例如： 7 7 0 05600 2500 4500 6 634 a

27、7 b 5 c 2 d 4 11 725 6 11 18 18016 1 2 3 4 5 6 7 HT 哈夫曼樹HT的存儲結構如下(HT為HuffmanTree類型)： HT是一個HTNode類型的一維數(shù)組，用以存放m個結點元 素(m=2n-1,其中n為葉子個數(shù))；即采用靜態(tài)二叉鏈表存放 哈夫曼樹；故HT可以用如下語句為其申請空間： HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); 其中 0號單元未用，從HT1開始存放樹的結點 四、構造哈夫曼樹并求四、構造哈夫曼樹并求n個字符的哈夫曼編碼之程序個字符的哈夫曼編碼之程序 1.哈夫曼樹的結點的物理結構：

28、 weightparentlchildrchild typedef char * * HaffmanCode ; / HaffmanCode是指向一個 字符型數(shù)組的指針類型 3.用n個字符型數(shù)組存放n個葉子的哈夫曼編碼 這n個字符數(shù)組的頭指針HCi(1in)分 別指向一個字符型數(shù)組的首地址，又構 成一個指針類型的一維數(shù)組； “0“1“1“0“ “0” “1 “ “0 “ “0” . . . . “0“0“1“1“1“ “0” HC1 HC2 HCn . . . . 則n個字符串數(shù)組的頭指針HCi(1 in)可以如此定義： HC=(HuffmanCode)malloc(n+1)*sizeof(c

29、har *); HCi = (char *)malloc(編碼長度+1)*sizeof(char); 四、構造哈夫曼樹并求四、構造哈夫曼樹并求n個字符的哈夫曼編碼之程序個字符的哈夫曼編碼之程序 4.構造哈夫曼樹的程序之實現(xiàn)： 算法思想： 例如： a 7 b 5 c 2 d 4 6 11 18 7 0 0 05000 2000 4000 0 00000000000 1 2 3 4 5 6 7 HT 其哈夫曼樹HT的存儲結構的初始情況如下： 針對第i個結點(n+1i2n-1,n=4為葉子結點的個數(shù))，在 1i-1號結點中為第i個結點尋找兩個兒子結點(該兩個兒子 應該是i-1個節(jié)點中無父親且權值最小

30、的兩個結點) 四、構造哈夫曼樹并求四、構造哈夫曼樹并求n個字符的哈夫曼編碼之程序個字符的哈夫曼編碼之程序 4.構造哈夫曼樹的程序之實現(xiàn)： 算法思想： 例如： a 7 b 5 c 2 d 4 6 11 18 7 0 0 05000 2500 4500 6 03400000000 1 2 3 4 5 6 7 HT 其哈夫曼樹HT的存儲結構的初始情況如下： 針對第i個結點(n+1i2n-1,n=4為葉子結點的個數(shù))，在 1i-1號結點中為第i個結點尋找兩個兒子結點(該兩個兒子 應該是i-1個節(jié)點中無父親且權值最小的兩個結點) 四、構造哈夫曼樹并求四、構造哈夫曼樹并求n個字符的哈夫曼編碼之程序個字符的

31、哈夫曼編碼之程序 4.構造哈夫曼樹的程序之實現(xiàn)： 算法思想： 例如： a 7 b 5 c 2 d 4 6 11 18 7 0 0 05600 2500 4500 6 634 11 0250000 1 2 3 4 5 6 7 HT 其哈夫曼樹HT的存儲結構的初始情況如下： 針對第i個結點(n+1i2n-1,n=4為葉子結點的個數(shù))，在 1i-1號結點中為第i個結點尋找兩個兒子結點(該兩個兒子 應該是i-1個節(jié)點中無父親且權值最小的兩個結點) 四、構造哈夫曼樹并求四、構造哈夫曼樹并求n個字符的哈夫曼編碼之程序個字符的哈夫曼編碼之程序 4.構造哈夫曼樹的程序之實現(xiàn)： 算法思想： 例如： a 7 b

32、5 c 2 d 4 6 11 18 7 7 0 05600 2500 4500 6 634 11 72518016 1 2 3 4 5 6 7 HT 其哈夫曼樹HT的存儲結構的初始情況如下： 針對第i個結點(n+1i2n-1,n=4為葉子結點的個數(shù))，在 1i-1號結點中為第i個結點尋找兩個兒子結點(該兩個兒子 應該是i-1個節(jié)點中無父親且權值最小的兩個結點) 四、構造哈夫曼樹并求四、構造哈夫曼樹并求n個字符的哈夫曼編碼之程序個字符的哈夫曼編碼之程序 4.構造哈夫曼樹的程序之實現(xiàn)： void HuffmanCoding(HuffmanTree if (n=1) return; m = 2 *

33、n - 1; /n即為葉子數(shù)即為葉子數(shù)n0,由二叉樹性質由二叉樹性質3,n0=n2+1,故樹中結點數(shù)為故樹中結點數(shù)為2*n-1 HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); / 0號單元未用 for (i=1; i=n; i+) /n個葉子結點賦初值，個葉子結點賦初值，n個葉子最初為個葉子最初為n個根結點個根結點 HTi.weight=wi-1; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; for (i=n+1; i=m; i+) /n-1個度為個度為2的結點賦初值的結點賦初值 HTi.weight=0;

34、 HTi.parent=0; HTi.lchild=0; HTi.rchild=0; for (i=n+1; i=m; i+) / 第第i次循環(huán)時為第次循環(huán)時為第i個結點選擇兩個兒子結點個結點選擇兩個兒子結點s1與與s2 Select(HT, i-1, / 在在i-1棵子樹中也即棵子樹中也即HT1.i-1中選擇無父親中選擇無父親(parent為為0) /且權值最小的兩個結點且權值最小的兩個結點(其序號分別為其序號分別為s1和和s2)。該子程序是一個順序查找過程。該子程序是一個順序查找過程 HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; /建立父子關系建立父子關系 /哈夫曼樹哈夫曼樹HT構造完畢構造完畢 四、構造哈夫曼樹并求四、構造哈夫曼樹并求n個字符的哈夫曼編碼之程序個字符的哈夫曼編碼之程序 5.從葉子到根逆向求每個字符的哈夫曼編碼的程序之實現(xiàn)： /從葉子到根逆向求每個字符的哈夫曼編碼從葉子到根逆向求每個字符的哈夫曼編碼; HC=(HuffmanCode)malloc(n+1)*sizeof(cha