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

6.8哈夫曼樹與

哈夫曼編碼

最優(yōu)樹的定義

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

前綴編碼

赫夫曼編碼

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

樹中每個(gè)結(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個(gè)權(quán)值{w1,w2,…wn}，構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(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個(gè)權(quán)值{w1,w2,…,wn}，構(gòu)造n棵二叉樹的集合

F={T1,T2,…,Tn}，其中每棵二叉樹中均只含一個(gè)帶權(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中刪去這兩棵樹，同時(shí)加入剛生成的新樹；重復(fù)

(2)

和

(3)

兩步，直至F中只含一棵樹為止。(3)(4)9例如:已知權(quán)值W={5,6,2,9,7}5627527697671395276713952795271667132900001111000110110111從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上分支字符組成的字符串，可以作為每個(gè)葉子結(jié)點(diǎn)編碼。約定左分支表示字符‘0’，右分支表示字符‘1’。若要設(shè)計(jì)不等長的編碼，則必須任何一個(gè)字符的編碼都不是同一字符集中另一個(gè)字符的編碼的前綴，這種編碼稱為前綴編碼。三、前綴編碼以傳送的電文為例比較等長編碼和不等長編碼方法：一、等長編碼：電文中所需傳送的字符有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ì)電文總長最短的二進(jìn)制前綴編碼即為以n種字符出現(xiàn)的頻率作權(quán)，設(shè)計(jì)一棵赫夫曼樹的問題，由此得到的二進(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ǔ)。實(shí)現(xiàn)二叉樹遍歷的具體算法與所采用的存儲結(jié)構(gòu)有關(guān)。掌握各種遍歷策略的遞歸算法，靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它操作。層次遍歷是按另一種搜索策略進(jìn)行的遍歷。4.理解二叉樹線索化的實(shí)質(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é)會編寫實(shí)現(xiàn)樹的各種操作的算法。7.了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和哈夫曼編碼的方法。復(fù)習(xí)題一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（）。250500254505以上答案都不是答案：E以下說法錯(cuò)誤的是（）存在這樣的二叉樹，對它采用任何次序遍歷其結(jié)點(diǎn)訪問序列均相同。二叉樹是樹的特殊情形。由樹轉(zhuǎn)換成二叉樹，其根結(jié)點(diǎn)的右子樹總是空的。在二叉樹只有一棵子樹的情況下，也要明確指出該子樹是左子樹還是右子樹。答案：B樹的基本遍歷策略可分為先根遍歷和后根遍歷，二叉樹的基本遍歷策略分為先序、中序和后序三種遍歷。我們把由樹轉(zhuǎn)化得到的二叉樹稱該樹對應(yīng)的二叉樹，則下面（）是正確的。樹的先根遍歷序列與其對應(yīng)的二叉樹先序遍歷序列相同。樹的后根遍歷序列與其對應(yīng)的二叉樹后序遍歷序列相同。樹的先根遍歷序列與其對應(yīng)的二叉樹中序遍歷序列相同。以上均不對。答案：A下面幾個(gè)符號串編碼集合中，不是前綴編碼的是（）。{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)無右孩子的二叉