ch06-4 樹(shù)和二叉樹(shù)4-哈夫曼樹(shù)和回溯

第6章樹(shù)和二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)講義-哈夫曼樹(shù)信息工程學(xué)院魏洪濤Email:greattide@163.com1．路徑和路徑長(zhǎng)度在一棵樹(shù)中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或子孫結(jié)點(diǎn)之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長(zhǎng)度。若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)-1。2．結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長(zhǎng)度若將樹(shù)中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積。6.6哈夫曼樹(shù)

一、基本術(shù)語(yǔ)3．樹(shù)的帶權(quán)路徑長(zhǎng)度樹(shù)的帶權(quán)路徑長(zhǎng)度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記為wpl=，其中n為葉子結(jié)點(diǎn)數(shù)目，wi為第i個(gè)葉子結(jié)點(diǎn)的權(quán)值，li為第i個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。1．哈夫曼樹(shù)的定義在一棵二叉樹(shù)中，若帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱為哈夫曼樹(shù)(Huffmantree)。二、構(gòu)造哈夫曼樹(shù)例有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=352．哈夫曼樹(shù)的構(gòu)造假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹(shù)有n個(gè)葉子結(jié)點(diǎn)。n個(gè)權(quán)值分別設(shè)為w1,w2,…,wn,則哈夫曼樹(shù)的構(gòu)造規(guī)則為：(1)將w1,w2,…,wn看成是有n棵樹(shù)的森林(每棵樹(shù)僅有一個(gè)結(jié)點(diǎn))；(2)在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹(shù)合并，作為一棵新樹(shù)的左、右子樹(shù)，且新樹(shù)的根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和；(3)從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)加入森林；(4)重復(fù)(2)、(3)步，直到森林中只剩一棵樹(shù)為止，該樹(shù)即為我們所求得的哈夫曼樹(shù)。

下面給出哈夫曼樹(shù)的構(gòu)造過(guò)程，假設(shè)給定的葉子結(jié)點(diǎn)的權(quán)分別為1,5,7,3，則構(gòu)造哈夫曼樹(shù)過(guò)程如圖7-24所示。構(gòu)造哈夫曼樹(shù)的模擬演示

在遠(yuǎn)程通訊中，要將待傳字符轉(zhuǎn)換成由二進(jìn)制組成的字符串：設(shè)要傳送的字符為：ABACCDA若編碼為：A—00B—01 C—10D---11

若將編碼設(shè)計(jì)為長(zhǎng)度不等的二進(jìn)制編碼，即讓待傳字符串中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼，則轉(zhuǎn)換的二進(jìn)制字符串便可能減少。00010010101100三、哈夫曼樹(shù)的應(yīng)用(哈夫曼編碼)設(shè)要傳送的字符為：ABACCDA若編碼為：A—0B—00 C—1D---01

關(guān)鍵：要設(shè)計(jì)長(zhǎng)度不等的編碼，則必須使任一字符的編碼都不是另一個(gè)字符的編碼的前綴。這種編碼稱作前綴編碼。

ABACCDA

000011010但：0000AAAAABABB重碼設(shè)要傳送的字符為：ABACCDA若編碼為：A—0B—110 C—10D---111

0110010101110ACBD000111采用二叉樹(shù)設(shè)計(jì)二進(jìn)制前綴編碼規(guī)定：左分支用“0”表示；右分支用“1”表示譯碼過(guò)程：分解接收字符串：遇“0”向左，遇“1”向右；一旦到達(dá)葉子結(jié)點(diǎn)，則譯出一個(gè)字符，反復(fù)由根出發(fā)，直到譯碼完成。0110010101110ACBD000111ABACCDA求Huffman編碼：由葉子→根，若：（1）從左分支下去，則分支為“0”；（2）從右分支下去，則分支為“1”。

ACBD000111例：已知某系統(tǒng)在通訊時(shí)，只出現(xiàn)C，A，S，T，B五種字符，它們出現(xiàn)的頻率依次為2，4，2，3，3，試設(shè)計(jì)Huffman編碼。

由Huffman樹(shù)得Huffman編碼為：TBACS000110110111148464220001113301TBACS出現(xiàn)頻率越大的字符，其Huffman編碼越短。６.7回溯法與樹(shù)的遍歷一、回溯法的基本思想回溯法：是對(duì)解空間樹(shù)進(jìn)行搜索的算法，從根結(jié)點(diǎn)開(kāi)始，對(duì)樹(shù)進(jìn)行先序遍歷，若遍歷到某一結(jié)點(diǎn)時(shí)肯定不包含問(wèn)題的解，則將該結(jié)點(diǎn)及其子樹(shù)去掉，并從該結(jié)點(diǎn)向根的方向回溯到其上一結(jié)點(diǎn)，繼續(xù)進(jìn)行先序遍歷。直到找到解或所有結(jié)點(diǎn)均遍歷完。分治法：將規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，而這些子問(wèn)題與原問(wèn)題是同一問(wèn)題，只是規(guī)模小了。例６-３：求含n個(gè)元素的集合的冪集Ａ的冪集：由Ａ的所有子集構(gòu)成的集合。如Ａ＝｛１，2，３｝則Ａ的冪集為：ρ(A)={{1,2,3},{1,2},{1,3},{2,