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

6.8哈夫曼樹與

哈夫曼編碼

最優(yōu)樹的定義

如何構(gòu)造最優(yōu)樹

前綴編碼

赫夫曼編碼

一、最優(yōu)樹的定義樹的路徑長度定義為：

樹中每個結(jié)點(diǎn)的路徑長度之和。結(jié)點(diǎn)的路徑長度定義為：

從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的數(shù)目。樹的帶權(quán)路徑長度定義為：

樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和WPL(T)=

wklk(對所有葉子結(jié)點(diǎn))。假設(shè)有n個權(quán)值{w1,w2,…wn}，構(gòu)造一棵有n個葉子結(jié)點(diǎn)的二叉樹，每個葉子結(jié)點(diǎn)帶權(quán)為Wi，則其中帶權(quán)路徑長度取最小值的二叉樹稱為“最優(yōu)樹”。例如：27975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=8954

根據(jù)給定的n個權(quán)值{w1,w2,…,wn}，構(gòu)造n棵二叉樹的集合

F={T1,T2,…,Tn}，其中每棵二叉樹中均只含一個帶權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹為空樹；二、如何構(gòu)造最優(yōu)樹(1)(赫夫曼算法)以二叉樹為例：在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；(2)從F中刪去這兩棵樹，同時加入剛生成的新樹；重復(fù)

(2)

和

(3)

兩步，直至F中只含一棵樹為止。(3)(4)9例如:已知權(quán)值W={5,6,2,9,7}5627527697671395276713952795271667132900001111000110110111從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上分支字符組成的字符串，可以作為每個葉子結(jié)點(diǎn)編碼。約定左分支表示字符‘0’，右分支表示字符‘1’。若要設(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’，在接收端，對于子串’0000’的譯法就有多種，可以是’AAAA‘、’BB’、‘ABA’、‘BAA’等等。四、赫夫曼編碼如何得到使電文總長最短的二進(jìn)制前綴編碼呢？假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為wi，其編碼長度為li，電文中只有n種字符，則電文總長為

wili。

對應(yīng)到二叉樹上，置wi為葉子結(jié)點(diǎn)的權(quán)，li為根到葉子的路徑長度，則

wili恰為二叉樹上帶權(quán)路徑長度。設(shè)計電文總長最短的二進(jìn)制前綴編碼即為以n種字符出現(xiàn)的頻率作權(quán)，設(shè)計一棵赫夫曼樹的問題，由此得到的二進(jìn)制前綴編碼稱為赫夫曼編碼。

利用赫夫曼樹可以構(gòu)造一種不等長的二進(jìn)制編碼，并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短。例6－2：

1.熟練掌握二叉樹的結(jié)構(gòu)特性，了解相應(yīng)的證明方法。2.熟悉二叉樹的各種存儲結(jié)構(gòu)的特點(diǎn)及適用范圍。3.遍歷二叉樹是二叉樹各種操作的基礎(chǔ)。實現(xiàn)二叉樹遍歷的具體算法與所采用的存儲結(jié)構(gòu)有關(guān)。掌握各種遍歷策略的遞歸算法，靈活運(yùn)用遍歷算法實現(xiàn)二叉樹的其它操作。層次遍歷是按另一種搜索策略進(jìn)行的遍歷。4.理解二叉樹線索化的實質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟練掌握二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。二叉樹的線索化過程是基于對二叉樹進(jìn)行遍歷，而線索二叉樹上的線索又為相應(yīng)的遍歷提供了方便。5.熟悉樹的各種存儲結(jié)構(gòu)及其特點(diǎn)，掌握樹和森林與二叉樹的轉(zhuǎn)換方法。建立存儲結(jié)構(gòu)是進(jìn)行其它操作的前提，因此讀者應(yīng)掌握1至2種建立二叉樹和樹的存儲結(jié)構(gòu)的方法。6.學(xué)會編寫實現(xiàn)樹的各種操作的算法。7.了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和哈夫曼編碼的方法。復(fù)習(xí)題一棵完全二叉樹上有1001個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個數(shù)是（）。250500254505以上答案都不是答案：E以下說法錯誤的是（）存在這樣的二叉樹，對它采用任何次序遍歷其結(jié)點(diǎn)訪問序列均相同。二叉樹是樹的特殊情形。由樹轉(zhuǎn)換成二叉樹，其根結(jié)點(diǎn)的右子樹總是空的。在二叉樹只有一棵子樹的情況下，也要明確指出該子樹是左子樹還是右子樹。答案：B樹的基本遍歷策略可分為先根遍歷和后根遍歷，二叉樹的基本遍歷策略分為先序、中序和后序三種遍歷。我們把由樹轉(zhuǎn)化得到的二叉樹稱該樹對應(yīng)的二叉樹，則下面（）是正確的。樹的先根遍歷序列與其對應(yīng)的二叉樹先序遍歷序列相同。樹的后根遍歷序列與其對應(yīng)的二叉樹后序遍歷序列相同。樹的先根遍歷序列與其對應(yīng)的二叉樹中序遍歷序列相同。以上均不對。答案：A下面幾個符號串編碼集合中，不是前綴編碼的是（）。{0,10,110,1111}{11,10,001,101,0001}{00,010,0110,1000}{b,c,aa,ac,aba,abb,abc}答案：B對于前序遍歷與中序遍歷結(jié)果相同的二叉樹為（），對于前序遍歷和后序遍歷結(jié)果相同的二叉樹為（）。一般二叉樹只有根結(jié)點(diǎn)的二叉樹根結(jié)點(diǎn)無左孩子的二叉樹根結(jié)點(diǎn)無右孩子的二叉