《樹和二叉樹4-哈夫曼樹和回溯.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《樹和二叉樹4-哈夫曼樹和回溯.ppt（25頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第6章 樹和二叉樹,嘉應(yīng)學(xué)院 數(shù)學(xué)系,數(shù)據(jù)結(jié)構(gòu)講義,- 哈夫曼樹,1路徑和路徑長度 在一棵樹中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或子孫結(jié)點(diǎn)之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。 若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長度為L-1。,2結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長度 若將樹中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱為該結(jié)點(diǎn)的權(quán)。 結(jié)點(diǎn)的帶權(quán)路徑長度為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)的權(quán)的乘積。,6.6 哈夫曼樹一、基本術(shù)語,3樹的帶權(quán)路徑長度 樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，記為wpl= ， 其中n 為葉子結(jié)點(diǎn)數(shù)目，wi為第i 個(gè)葉子結(jié)點(diǎn)的權(quán)值，

2、li 為第i 個(gè)葉子結(jié)點(diǎn)的路徑長度。,1哈夫曼樹的定義 在一棵二叉樹中，若帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman tree)。,二、構(gòu)造哈夫曼樹,例 有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè)葉子結(jié)點(diǎn)的二叉樹,WPL=7*2+5*2+2*2+4*2=36,WPL=7*3+5*3+2*1+4*2=46,WPL=7*1+5*2+2*3+4*3=35,2哈夫曼樹的構(gòu)造 假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹有n個(gè)葉子結(jié)點(diǎn)。 n個(gè)權(quán)值分別設(shè)為 w1,w2,wn,則哈夫曼樹的構(gòu)造規(guī)則為：,(1) 將w1,w2,wn看成是有n 棵樹的森林(每棵樹僅有一個(gè)結(jié)點(diǎn))；

3、,(2) 在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點(diǎn)權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和； (3)從森林中刪除選取的兩棵樹，并將新樹加入森林； (4)重復(fù)(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為我們所求得的哈夫曼樹。,下面給出哈夫曼樹的構(gòu)造過程，假設(shè)給定的葉子結(jié)點(diǎn)的權(quán)分別為1,5,7,3，則構(gòu)造哈夫曼樹過程如圖7-24所示。,構(gòu)造哈夫曼樹的模擬演示,在遠(yuǎn)程通訊中，要將待傳字符轉(zhuǎn)換成由二進(jìn)制組成的字符串： 設(shè)要傳送的字符為： ABACCDA 若編碼為：A00 B01 C10 D-11,若將編碼設(shè)計(jì)為長度不等的二進(jìn)制編碼，即讓待傳字符串中出現(xiàn)次數(shù)較多

4、的字符采用盡可能短的編碼，則轉(zhuǎn)換的二進(jìn)制字符串便可能減少。,00010010101100,三、哈夫曼樹的應(yīng)用(哈夫曼編碼),設(shè)要傳送的字符為：ABACCDA 若編碼為： A0 B00 C1 D-01,關(guān)鍵：要設(shè)計(jì)長度不等的編碼，則必須使任一字符的編碼都不是另一個(gè)字符的編碼的前綴。這種編碼稱作前綴編碼。,ABACCDA,000011010,但： 0000 AAAA ABA BB,重碼,設(shè)要傳送的字符為： ABACCDA 若編碼為 ：A0 B110 C10 D-111,0110010101110,A,C,B,D,0,0,0,1,1,1,采用二叉樹設(shè)計(jì)二進(jìn)制前綴編碼,規(guī)定： 左分支用“0”表示； 右

5、分支用“1”表示,譯碼過程：分解接收字符串：遇“0”向左，遇“1”向右；一旦到達(dá)葉子結(jié)點(diǎn)，則譯出一個(gè)字符，反復(fù)由根出發(fā)，直到譯碼完成。,0110010101110,A,C,B,D,0,0,0,1,1,1,ABACCDA,求Huffman編碼：由葉子根，若： （1）從左分支下去，則分支為“0”； （2）從右分支下去，則分支為“1”。,A,C,B,D,0,0,0,1,1,1,例：已知某系統(tǒng)在通訊時(shí)，只出現(xiàn)C，A，S，T，B五種字符，它們出現(xiàn)的頻率依次為2，4，2，3，3，試設(shè)計(jì)Huffman編碼。 由Huffman樹得Huffman編碼為： T B A C S 00 01 10 110 111,1

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

7、,3,1,2,1,3,2,3,1,2,3, 求的冪集的解空間樹：可以用高度為的滿足二叉樹表示，其中由根到第一層結(jié)點(diǎn)的分支表示對(duì)第個(gè)元素的取舍，第一層到第二層的分支表示對(duì)第個(gè)元素的取舍，第二層到第三層的分支表示對(duì)第個(gè)元素的取舍，從根到葉子的路徑構(gòu)成一個(gè)解。,1,2,3,1,2,1, 3,1,2,3,2,3,表示取，表示不取，到每個(gè)葉子的路徑構(gòu)成一個(gè)子集，所有路徑的集合即為的冪集。,例：n=3時(shí)的0-1背包問題 三件物品，重量分別為16,15,15，即w=16,15,15 價(jià)值分別為45,25,25，即p=45,25,25，背包空間30，問：應(yīng)如何裝，才能使得所裝物品總價(jià)值最大？ 窮舉法：考慮所有

8、情形，取其最大值，共有23=8種情形。 貪心法：先取單位價(jià)值最大者，再取次大者。結(jié)果取重量為的物品。 回溯法：先建立解空間樹如下：,表示取，表示不取，每個(gè)分支代表一個(gè)物品 第2層:w=16,p=45,第2,3層:w=15,p=25,A,B,D,H,I,J,K,L,M,N,O,G,C,F,E,用回溯法解題的三個(gè)步驟 ，針對(duì)所給問題，定義問題的解空間 ，確定易于搜索的解空間結(jié)構(gòu) ，以先序遍歷（深度優(yōu)先搜索）的方式搜索解空間，并在搜索過程中使用剪枝函數(shù)避免無效搜索。,使用遞歸方法實(shí)現(xiàn)回溯 void backtrack(int t) if(tn) output(x); else for(int i=f

9、(n,t);i=g(n,t);i+) xt=h(i);/h(i)為當(dāng)前結(jié)點(diǎn)處xt的第i個(gè)可選值 if(constraint(t) /if函數(shù)內(nèi)的兩個(gè)函數(shù)為約束函數(shù)和界限函數(shù) ,t為遞歸深度，tn時(shí)表示已搜索到葉子結(jié)點(diǎn)，for循環(huán)是對(duì)剩下的分支進(jìn)行循環(huán)。,例6-4求皇后問題的所有合法布局 解空間樹（叉樹）的構(gòu)成：根結(jié)點(diǎn)為空棋盤（棋盤），根結(jié)點(diǎn)的個(gè)孩子為由在根結(jié)點(diǎn)上放置了第一個(gè)皇后后形成的棋盤，第三層則是在第二層的基礎(chǔ)上放置了第二個(gè)皇后后形成的棋盤，共有4層，第4層共有44=256個(gè)葉子。 約束函數(shù)為：任何兩個(gè)棋子均不在同一行，不在同一列和不在同一斜線上,使用遞歸方法實(shí)現(xiàn)回溯 void Trial

10、(int i,int n) if(in) 輸出棋盤的當(dāng)前布局; else for(j=1;j=n);j+) 在第i行第j列放置一個(gè)皇后 if(當(dāng)前布局合法) Trial(i+1,n); /if函數(shù)內(nèi)的兩個(gè)函數(shù)為約束函數(shù)和界限函數(shù) ,1. 熟練掌握二叉樹的結(jié)構(gòu)特性，了解相應(yīng)的證明方法。 2. 熟悉二叉樹的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。 3. 遍歷二叉樹是二叉樹各種操作的基礎(chǔ)。實(shí)現(xiàn)二叉樹遍歷的具體算法與所采用的存儲(chǔ)結(jié)構(gòu)有關(guān)。掌握各種遍歷策略的遞歸算法，靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它操作。層次遍歷是按另一種搜索策略進(jìn)行的遍歷。,4. 熟悉樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹和森林與二叉樹的轉(zhuǎn)換方法。建

11、立存儲(chǔ)結(jié)構(gòu)是進(jìn)行其它操作的前提，因此讀者應(yīng)掌握 1 至 2 種建立二叉樹和樹的存儲(chǔ)結(jié)構(gòu)的方法。 5. 學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法。 6. 了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和哈夫曼編碼的方法。,作業(yè),1，假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼并畫出相應(yīng)的哈夫曼樹。 2，n=5時(shí)的0-1背包問題：設(shè)有五件物品，重量分別為2, 6,5,4，價(jià)值分別為6, 5,4,6，背包空間10，問：應(yīng)如何裝，才能使得所裝物品總價(jià)值最大？分別用貪心算法和回溯法求解（回溯法求解時(shí)只要求畫出解空間樹并給出最后的解）。,