哈夫曼樹與哈夫曼編碼課件

1、6.8 哈 夫 曼 樹 與 哈 夫 曼 編 碼 最優(yōu)樹的定義 如何構(gòu)造最優(yōu)樹 前綴編碼 赫夫曼編碼 6.8 哈 夫 曼 樹 與 哈 夫 曼 編 碼 一、最優(yōu)樹的定義樹的路徑長度定義為： 樹中每個結(jié)點的路徑長度之和。 結(jié)點的路徑長度定義為： 從根結(jié)點到該結(jié)點的路徑上 分支的數(shù)目。 一、最優(yōu)樹的定義樹的路徑長度定義為： 結(jié)點的路徑長度定義為 樹的帶權(quán)路徑長度定義為： 樹中所有葉子結(jié)點的帶權(quán)路徑長度之和 WPL(T) = wklk (對所有葉子結(jié)點)。假設(shè)有n個權(quán)值w1,w2,wn，構(gòu)造一棵有n個葉子結(jié)點的二叉樹，每個葉子結(jié)點帶權(quán)為Wi，則其中帶權(quán)路徑長度取最小值的二叉樹稱為“最優(yōu)樹”。例如： 樹的

2、帶權(quán)路徑長度定義為：假設(shè)有n個權(quán)值w1,w2,w27 9 75492WPL(T)= 72+52+23+43+92 =60WPL(T)= 74+94+53+42+21 =89 5427 9 75492WPL(T)= 7 根據(jù)給定的 n 個權(quán)值 w1, w2, , wn， 構(gòu)造 n 棵二叉樹的集合 F = T1, T2, , Tn， 其中每棵二叉樹中均只含一個帶權(quán)值 為 wi 的根結(jié)點，其左、右子樹為空樹；二、如何構(gòu)造最優(yōu)樹(1) (赫夫曼算法) 以二叉樹為例： 根據(jù)給定的 n 個權(quán)值 w1, w2, , 在 F 中選取其根結(jié)點的權(quán)值為最 小的兩棵二叉樹，分別作為左、 右子樹構(gòu)造一棵新的二叉樹，并

3、 置這棵新的二叉樹根結(jié)點的權(quán)值 為其左、右子樹根結(jié)點的權(quán)值之 和；(2) 在 F 中選取其根結(jié)點的權(quán)值為最(2) 從F中刪去這兩棵樹，同時加入 剛生成的新樹； 重復(fù) (2) 和 (3) 兩步，直至 F 中只 含一棵樹為止。(3)(4) 從F中刪去這兩棵樹，同時加入 重復(fù) (29例如: 已知權(quán)值 W= 5, 6, 2, 9, 7 5627527697671395279例如: 已知權(quán)值 W= 5, 6, 2, 9, 7 56713952795271667132900001111000110110111從根結(jié)點到葉子結(jié)點的路徑上分支字符組成的字符串，可以作為每個葉子結(jié)點編碼。約定左分支表示字符0，右

4、分支表示字符1。671395279527166713290000111100 若要設(shè)計不等長的編碼，則必須任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴，這種編碼稱為前綴編碼。三、前綴編碼以傳送的電文為例比較等長編碼和不等長編碼方法：一、等長編碼：電文中所需傳送的字符有A、B、C、D，編碼分別為00、01、10、11，若要發(fā)送ABACCDA電文，則以字符串00010010101100發(fā)送，根據(jù)字符對應(yīng)的編碼，在接收端能知道發(fā)送的電文為ABACCDA。二、不等長編碼：當(dāng)A、B、C、D的編碼分別為0、00、1、10，要發(fā)送上述電文以電文ABACCDA ，相應(yīng)的字符串為000011100

5、，在接收端，對于子串0000的譯法就有多種，可以是AAAA、BB、ABA、BAA等等。 若要設(shè)計不等長的編碼，則必須任何一個字符的編碼都不是同一四、赫夫曼編碼 如何得到使電文 總長最短的二進制前綴編碼呢？假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為wi，其編碼長度為li，電文中只有n種字符，則電文總長為wili。 對應(yīng)到二叉樹上，置wi為葉子結(jié)點的權(quán)，li為根到葉子的路徑長度，則wili恰為二叉樹上帶權(quán)路徑長度。 設(shè)計電文總長最短的二進制前綴編碼即為以n種字符出現(xiàn)的頻率作權(quán)，設(shè)計一棵赫夫曼樹的問題，由此得到的二進制前綴編碼稱為赫夫曼編碼。 四、赫夫曼編碼 如何得到使電文 總長最短的二進 利用赫夫曼樹可以構(gòu)

6、造一種不等長的二進制編碼，并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短。 例62： 利用赫夫曼樹可以構(gòu)造一種不等長的二進制編碼，1. 熟練掌握二叉樹的結(jié)構(gòu)特性，了解相應(yīng)的證明方法。2. 熟悉二叉樹的各種存儲結(jié)構(gòu)的特點及適用范圍。3. 遍歷二叉樹是二叉樹各種操作的基礎(chǔ)。實現(xiàn)二叉樹遍歷的具體算法與所采用的存儲結(jié)構(gòu)有關(guān)。掌握各種遍歷策略的遞歸算法，靈活運用遍歷算法實現(xiàn)二叉樹的其它操作。層次遍歷是按另一種搜索策略進行的遍歷。1. 熟練掌握二叉樹的結(jié)構(gòu)特性，了解相應(yīng)的證明方法。4. 理解二叉樹線索化的實質(zhì)是建立結(jié)點與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟練掌握二叉樹的線索化

7、過程以及在中序線索化樹上找給定結(jié)點的前驅(qū)和后繼的方法。二叉樹的線索化過程是基于對二叉樹進行遍歷，而線索二叉樹上的線索又為相應(yīng)的遍歷提供了方便。4. 理解二叉樹線索化的實質(zhì)是建立結(jié)點與其在相應(yīng)序列中的5. 熟悉樹的各種存儲結(jié)構(gòu)及其特點，掌握樹和森林與二叉樹的轉(zhuǎn)換方法。建立存儲結(jié)構(gòu)是進行其它操作的前提，因此讀者應(yīng)掌握 1 至 2 種建立二叉樹和樹的存儲結(jié)構(gòu)的方法。6. 學(xué)會編寫實現(xiàn)樹的各種操作的算法。7. 了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和哈夫曼編碼的方法。5. 熟悉樹的各種存儲結(jié)構(gòu)及其特點，掌握樹和森林與二叉樹的復(fù)習(xí)題一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（）。250500254

8、505以上答案都不是答案：E復(fù)習(xí)題一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是以下說法錯誤的是（）存在這樣的二叉樹，對它采用任何次序遍歷其結(jié)點訪問序列均相同。二叉樹是樹的特殊情形。由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的。在二叉樹只有一棵子樹的情況下，也要明確指出該子樹是左子樹還是右子樹。答案：B以下說法錯誤的是（）樹的基本遍歷策略可分為先根遍歷和后根遍歷，二叉樹的基本遍歷策略分為先序、中序和后序三種遍歷。我們把由樹轉(zhuǎn)化得到的二叉樹稱該樹對應(yīng)的二叉樹，則下面（）是正確的。樹的先根遍歷序列與其對應(yīng)的二叉樹先序遍歷序列相同。樹的后根遍歷序列與其對應(yīng)的二叉樹后序遍歷序列相同。樹的先根遍歷序列與其對應(yīng)的二叉樹中序遍歷序列相同。以上均不對。答案：A樹的基本遍歷策略可分為先根遍歷和后根遍歷，二叉樹的基本遍歷策下面幾個符號串編碼集合中，不是前綴編碼的是（）。0,10,110,111111,10,001,101,000100,010,0110,1000b,c,aa,ac,aba,abb,abc答案：B下面幾個符號串編碼集合中，不是前綴編碼的是（）。對于前序遍歷與中序遍歷結(jié)果相同的二叉樹為（），對于前序遍歷和后序遍歷結(jié)果相同的二叉樹為（）。一般二叉樹只有根結(jié)點的二叉樹根結(jié)點無左孩子的二叉樹根結(jié)點無右孩子的二叉樹所有結(jié)點只有左子樹的二叉樹所有結(jié)點只有右子樹