第6章 樹(shù)和二叉樹(shù),嘉應(yīng)學(xué)院 數(shù)學(xué)系,數(shù)據(jù)結(jié)構(gòu)講義,- 哈夫曼樹(shù),1路徑和路徑長(zhǎng)度 在一棵樹(shù)中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或子孫結(jié)點(diǎn)之間的通路，稱(chēng)為路徑。通路中分支的數(shù)目稱(chēng)為路徑長(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ù)值稱(chēng)為該結(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á)到最小，稱(chēng)這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱(chēng)為哈夫曼樹(shù)(Huffman tree)。,二、構(gòu)造哈夫曼樹(shù),例 有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè)葉子結(jié)點(diǎn)的二叉樹(shù),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哈夫曼樹(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 若編碼為：A00 B01 C10 D-11,若將編碼設(shè)計(jì)為長(zhǎng)度不等的二進(jìn)制編碼，即讓待傳字符串中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼，則轉(zhuǎn)換的二進(jìn)制字符串便可能減少。,00010010101100,三、哈夫曼樹(shù)的應(yīng)用(哈夫曼編碼),設(shè)要傳送的字符為：ABACCDA 若編碼為： A0 B00 C1 D-01,關(guān)鍵：要設(shè)計(jì)長(zhǎng)度不等的編碼，則必須使任一字符的編碼都不是另一個(gè)字符的編碼的前綴。這種編碼稱(chēng)作前綴編碼。,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ù)設(shè)計(jì)二進(jìn)制前綴編碼,規(guī)定： 左分支用“0”表示； 右分支用“1”表示,譯碼過(guò)程：分解接收字符串：遇“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樹(shù)得Huffman編碼為： T B A C S 00 01 10 110 111,14,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回溯法與樹(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,3,1,2,3, 求的冪集的解空間樹(shù)：可以用高度為的滿(mǎn)足二叉樹(shù)表示，其中由根到第一層結(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背包問(wèn)題 三件物品，重量分別為16,15,15，即w=16,15,15 價(jià)值分別為45,25,25，即p=45,25,25，背包空間30，問(wèn)：應(yīng)如何裝，才能使得所裝物品總價(jià)值最大？ 窮舉法：考慮所有情形，取其最大值，共有23=8種情形。 貪心法：先取單位價(jià)值最大者，再取次大者。結(jié)果取重量為的物品。 回溯法：先建立解空間樹(shù)如下：,表示取，表示不取，每個(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ì)所給問(wèn)題，定義問(wèn)題的解空間 ，確定易于搜索的解空間結(jié)構(gòu) ，以先序遍歷（深度優(yōu)先搜索）的方式搜索解空間，并在搜索過(guò)程中使用剪枝函數(shù)避免無(wú)效搜索。,使用遞歸方法實(shí)現(xiàn)回溯 void backtrack(int t) if(tn) output(x); else for(int i=f(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求皇后問(wèn)題的所有合法布局 解空間樹(shù)（叉樹(shù)）的構(gòu)成：根結(jié)點(diǎn)為空棋盤(pán)（棋盤(pán)），根結(jié)點(diǎn)的個(gè)孩子為由在根結(jié)點(diǎn)上放置了第一個(gè)皇后后形成的棋盤(pán)，第三層則是在第二層的基礎(chǔ)上放置了第二個(gè)皇后后形成的棋盤(pán)，共有4層，第4層共有44=256個(gè)葉子。 約束函數(shù)為：任何兩個(gè)棋子均不在同一行，不在同一列和不在同一斜線(xiàn)上,使用遞歸方法實(shí)現(xiàn)回溯 void Trial(int i,int n) if(in) 輸出棋盤(pán)的當(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. 熟練掌握二叉樹(shù)的結(jié)構(gòu)特性，了解相應(yīng)的證明方法。 2. 熟悉二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。 3. 遍歷二叉樹(shù)是二叉樹(shù)各種操作的基礎(chǔ)。實(shí)現(xiàn)二叉樹(shù)遍歷的具體算法與所采用的存儲(chǔ)結(jié)構(gòu)有關(guān)。掌握各種遍歷策略的遞歸算法，靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其它操作。層次遍歷是按另一種搜索策略進(jìn)行的遍歷。,4. 熟悉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換方法。建立存儲(chǔ)結(jié)構(gòu)是進(jìn)行其它操作的前提，因此讀者應(yīng)掌握 1 至 2 種建立二叉樹(shù)和樹(shù)的存儲(chǔ)結(jié)構(gòu)的方法。 5. 學(xué)會(huì)編寫(xiě)實(shí)現(xiàn)樹(shù)的各種操作的算法。 6. 了解最優(yōu)樹(shù)的特性，掌握建立最優(yōu)樹(shù)和哈夫曼編碼的方法。,作業(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ì)哈夫曼編碼并畫(huà)出相應(yīng)的哈夫曼樹(shù)。 2，n=5時(shí)的0-1背包問(wèn)題：設(shè)有五件物品，重量分別為2, 6,5,4，價(jià)值分別為6, 5,4,6，背包空間10，問(wèn)：應(yīng)如何裝，才能使得所裝物品總價(jià)值最大？分別用貪心算法和回溯法求解（回溯法求解時(shí)只要求畫(huà)出解空間樹(shù)并給出最后的解）。,