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

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

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

下面給出哈夫曼樹的構造過程，假設給定的葉子結點的權分別為1,5,7,3，則構造哈夫曼樹過程如圖7-24所示。構造哈夫曼樹的模擬演示

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

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

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

ABACCDA

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

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

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

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