ch06-4 樹和二叉樹4-哈夫曼樹和回溯

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

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

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

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

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

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

ABACCDA

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

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

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

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