作品名稱：數(shù)據(jù)結(jié)構(gòu)
學(xué)校名稱：山東交通學(xué)院
參賽隊(duì)伍：朱振方
參賽老師：朱振方
哈夫曼樹及其應(yīng)用教學(xué)內(nèi)容安排
一、最優(yōu)二叉樹（Huffman樹）
哈夫曼樹又叫最優(yōu)二叉樹，它是由n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹中帶權(quán)路徑長度WPL最短的二叉樹。
1、基本術(shù)語
?路徑和路徑長度
?樹的路徑長度
?結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長度
?樹的帶權(quán)路徑長度
?Huffman樹（最優(yōu)二叉樹）
路徑：若在一棵樹中存在著一個(gè)結(jié)點(diǎn)序列k1，k2 … kj，使得 ki 是k i+1(1￡i<j) 的父親，則該結(jié)點(diǎn)序列是k1 到kj的路徑
路徑長度：從k1 到kj所經(jīng)過的分支數(shù)稱為這兩點(diǎn)間的路徑長度 。
?樹的路徑長度：樹中每個(gè)結(jié)點(diǎn)的路徑長度之和。
?結(jié)點(diǎn)的權(quán)：樹中的結(jié)點(diǎn)賦予的一定意義上的實(shí)數(shù)稱之為該結(jié)點(diǎn)的權(quán)
?樹的帶權(quán)路徑長度定義為：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和WPL(T) = SwkLk (對所有葉子結(jié)點(diǎn))。
在所有含 n 個(gè)葉子結(jié)點(diǎn)、并帶相同權(quán)值的 m 叉樹中，必存在一棵其帶權(quán)路徑長度取最小值的樹，稱為“最優(yōu)樹”。
最優(yōu)二叉樹（也稱Huffman樹）：它是n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹中帶權(quán)路徑長度 WPL最小的二叉樹。
2、為何要構(gòu)造哈夫曼樹
3、如何構(gòu)造哈夫曼樹
哈夫曼算法：
（1）根據(jù)給定的 n 個(gè)權(quán)值 {w1, w2, …, wn}，構(gòu)造 n 棵二叉樹的集合 F = {T1, T2,… , Tn}，
其中每棵二叉樹中均只含一個(gè)帶權(quán)值 為 wi 的根結(jié)點(diǎn)，其左、右子樹為空樹；
（2）在 F 中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；
（3）從F中刪去這兩棵樹，同時(shí)加入剛生成的新樹；
（4）重復(fù) (2) 和 (3) 兩步，直至 F 中只含一棵樹為止。
例1: 已知權(quán)值 W={ 6，7，2，3，5，11，12 }，試構(gòu)造一棵哈夫曼樹，并求加權(quán)路徑長度
二、哈夫曼編碼
1、問題的提出
通訊中常需要將文字轉(zhuǎn)換成二進(jìn)制字符串電文進(jìn)行傳送。文字電文，稱為編碼。
反之，收到電文后要將電文轉(zhuǎn)換成原來的文字，電文 文字，稱為譯碼。
反之，收到電文后要將電文轉(zhuǎn)換成原來的文字，電文 文字，稱為譯碼。
設(shè)有n種字符，每種字符出現(xiàn)的次數(shù)為Wi ,其編碼長度為Li ( i=1,2,…n)，則整個(gè)電文總長度為∑ Wi Li ，要得到最短的電文，即使得∑ Wi Li最小。也就是以字符出現(xiàn)的次數(shù)為權(quán)值，構(gòu)造一棵 Huffman樹，并規(guī)定左分支編碼位0，右分支編碼為1，則字符的編碼就是從根到該字符所在的葉結(jié)點(diǎn)的路徑上的分支編號序列。
用構(gòu)造Huffman樹編出來的碼，稱為Huffman編碼。
2. 哈夫曼編碼的構(gòu)造方法
（1）構(gòu)造Huffman 樹
（2）產(chǎn)生Huffman 編碼
