數(shù)據(jù)結(jié)構(gòu)算法之樹的應(yīng)用PPT課件

1、 設(shè)有100個學(xué)生某門課程的考試成績的分布如下表所示： 一、問題的提出(判斷樹)分?jǐn)?shù)05960697079 808990100學(xué)生比例數(shù)0.050.150.400.300.10學(xué)生成績數(shù)據(jù)分布情況表學(xué)生成績數(shù)據(jù)分布情況表*問題：問題：現(xiàn)在要編寫程序依次根據(jù)每個學(xué)生的成績現(xiàn)在要編寫程序依次根據(jù)每個學(xué)生的成績打印出該學(xué)生的成績等級。打印出該學(xué)生的成績等級。第1頁/共36頁分?jǐn)?shù)05960697079 808990100學(xué)生比例數(shù)0.050.150.400.300.10學(xué)生成績數(shù)據(jù)分布情況表學(xué)生成績數(shù)據(jù)分布情況表方法方法1：a60打印打印badyesa70no打印打印passyesa80no打印打印g

2、eneralyesa90no打印打印goodyes打印打印excellentno5%的的學(xué)生學(xué)生15%的的學(xué)生學(xué)生40%的的學(xué)生學(xué)生30%的的學(xué)生學(xué)生10%的的學(xué)生學(xué)生共做315次比較讀取一個學(xué)生成績讀取一個學(xué)生成績a循環(huán)一百次循環(huán)一百次第2頁/共36頁分?jǐn)?shù)05960697079 808990100學(xué)生比例數(shù)0.050.150.400.300.10學(xué)生成績數(shù)據(jù)分布情況表學(xué)生成績數(shù)據(jù)分布情況表方法方法2：a80打印打印badyesa90noyesnoa70yesnoa60yesno打印打印“good打印打印excellent打印打印pass打印打印general5%的的學(xué)生學(xué)生15%的的學(xué)生學(xué)生

3、40%的的學(xué)生學(xué)生30%的的學(xué)生學(xué)生10%的的學(xué)生學(xué)生共做220次比較讀取一個學(xué)生成績讀取一個學(xué)生成績a循環(huán)一百次循環(huán)一百次第3頁/共36頁思考：思考：如何找到一棵如何找到一棵最優(yōu)的最優(yōu)的判斷樹使得編寫判斷樹使得編寫出來的程序的運行時間是最高效的？出來的程序的運行時間是最高效的？第4頁/共36頁1.哈夫曼樹的有關(guān)概念 結(jié)點的路徑長度： 從根結(jié)點沿某條路徑到某結(jié)點途中所經(jīng)歷的邊的條數(shù)稱為該結(jié)點的路徑長度。 二、哈夫曼樹及其應(yīng)用 樹的路徑長度： 從根結(jié)點到每一個葉子結(jié)點的路徑長度之和。 樹的帶權(quán)路徑長度(WPL)： 樹中所有葉子結(jié)點的帶權(quán)路徑長度之和稱為樹的帶權(quán)路徑長度。結(jié)點的帶權(quán)路徑長度： 某結(jié)

4、點的路徑長度與該結(jié)點上的權(quán)值的乘積稱為該結(jié)點的帶權(quán)路徑長度。 第5頁/共36頁1.哈夫曼樹的有關(guān)概念 二、哈夫曼樹及其應(yīng)用實例實例：已知某二叉樹的四個葉子結(jié)點已知某二叉樹的四個葉子結(jié)點 a,b,c,d分別帶權(quán)分別帶權(quán)7，5，2，4，則可構(gòu)造出有如下幾，則可構(gòu)造出有如下幾種不同形式的二叉樹：種不同形式的二叉樹：aaa777b5b5c2d4c2d4b5c2d 4樹的帶權(quán)路徑長度為：WPL=2*7+2*5+2*2+2*4=36樹的帶權(quán)路徑長度為：WPL=2*4+3*7+3*5+1*2=46樹的帶權(quán)路徑長度為：WPL=1*7+2*5+3*2+3*4=35第6頁/共36頁哈夫曼樹的定義：二、哈夫曼樹及其

5、應(yīng)用 設(shè)有設(shè)有n個葉子結(jié)點的二叉樹，其第個葉子結(jié)點的二叉樹，其第i個個葉子結(jié)點的權(quán)值為葉子結(jié)點的權(quán)值為wi(i=1,2,3,.n),且第且第i個個葉子結(jié)點的路徑長度為葉子結(jié)點的路徑長度為li ,則使則使WPL=wi*li最小的二叉樹稱為最小的二叉樹稱為“最優(yōu)最優(yōu)二叉樹二叉樹”或稱為或稱為“哈夫曼樹哈夫曼樹”。i=1n第7頁/共36頁2.哈夫曼樹的求解過程 二、哈夫曼樹及其應(yīng)用問題：問題： 已知已知n個葉子的權(quán)值為個葉子的權(quán)值為w1,w2,.wn，構(gòu)，構(gòu)造一棵最優(yōu)二叉樹。造一棵最優(yōu)二叉樹。第8頁/共36頁2.哈夫曼樹的求解過程 二、哈夫曼樹及其應(yīng)用方法：方法： 步驟步驟1:構(gòu)造一個具有構(gòu)造一個具

6、有n棵二叉樹的森林棵二叉樹的森林F=T1,T2,.,Tn，其中，其中Ti是只有一個根結(jié)點且根結(jié)是只有一個根結(jié)點且根結(jié)點的權(quán)值為點的權(quán)值為wi的二叉樹。的二叉樹。步驟步驟2:在在F中選取兩棵其根結(jié)點的權(quán)值最小的二叉樹，從中選取兩棵其根結(jié)點的權(quán)值最小的二叉樹，從F中刪除這兩棵樹，并以這兩棵二叉樹為左右子樹構(gòu)造一中刪除這兩棵樹，并以這兩棵二叉樹為左右子樹構(gòu)造一棵新的二叉樹添加到棵新的二叉樹添加到F中，該新的二叉樹的根結(jié)點的權(quán)值中，該新的二叉樹的根結(jié)點的權(quán)值為其左右孩子二叉樹的根結(jié)點的權(quán)值之和。為其左右孩子二叉樹的根結(jié)點的權(quán)值之和。步驟步驟3:判斷判斷F中是否只有唯一的一棵二叉樹。若是，則求中是否只有

7、唯一的一棵二叉樹。若是，則求解過程結(jié)束；否則，轉(zhuǎn)步驟解過程結(jié)束；否則，轉(zhuǎn)步驟2。第9頁/共36頁2.哈夫曼樹的求解過程 二、哈夫曼樹及其應(yīng)用實例：已知有實例：已知有5個葉子結(jié)點的權(quán)值分別為：個葉子結(jié)點的權(quán)值分別為：5 , 15 , 40 , 30 , 10 ；試畫出一棵相應(yīng)的哈夫曼樹。；試畫出一棵相應(yīng)的哈夫曼樹。 a40b30c5d10e1515第10頁/共36頁2.哈夫曼樹的求解過程 二、哈夫曼樹及其應(yīng)用實例：已知有實例：已知有5個葉子結(jié)點的權(quán)值分別為：個葉子結(jié)點的權(quán)值分別為：5 , 15 , 40 , 30 , 10 ；試畫出一棵相應(yīng)的哈夫曼樹。；試畫出一棵相應(yīng)的哈夫曼樹。 a40b30c

8、5d10e1515第11頁/共36頁2.哈夫曼樹的求解過程 二、哈夫曼樹及其應(yīng)用實例：已知有實例：已知有5個葉子結(jié)點的權(quán)值分別為：個葉子結(jié)點的權(quán)值分別為：5 , 15 , 40 , 30 , 10 ；試畫出一棵相應(yīng)的哈夫曼樹。；試畫出一棵相應(yīng)的哈夫曼樹。 a40b30c5d10e151530第12頁/共36頁2.哈夫曼樹的求解過程 二、哈夫曼樹及其應(yīng)用實例：已知有實例：已知有5個葉子結(jié)點的權(quán)值分別為：個葉子結(jié)點的權(quán)值分別為：5 , 15 , 40 , 30 , 10 ；試畫出一棵相應(yīng)的哈夫曼樹。；試畫出一棵相應(yīng)的哈夫曼樹。 a40b30c5d10e15153060第13頁/共36頁2.哈夫曼樹

9、的求解過程 二、哈夫曼樹及其應(yīng)用a40b30c5d1014頁/共36頁3.哈夫曼編碼 二、哈夫曼樹及其應(yīng)用等長等長編碼：編碼： 以英文字符編碼為例，一般英文字符編碼是采以英文字符編碼為例，一般英文字符編碼是采用用7位二進(jìn)制數(shù)編碼（位二進(jìn)制數(shù)編碼（ASCII碼）。碼）。7位二進(jìn)制數(shù)位二進(jìn)制數(shù)可以為可以為27個不同的英文字符編碼。個不同的英文字符編碼。 下面為討論問題簡單起見，假設(shè)被編碼的字符下面為討論問題簡單起見，假設(shè)被編碼的字符集中只有集中只有4個（即個（即22個）不同字符，故只要兩位二個）不同字符，故只要兩位二進(jìn)制數(shù)即可完成編碼。進(jìn)制數(shù)即可完成編碼。 設(shè)這設(shè)這4個不

10、同的字符為個不同的字符為A，B，C，D，則可進(jìn)，則可進(jìn)行等長編碼如下：行等長編碼如下：第15頁/共36頁3.哈夫曼編碼 二、哈夫曼樹及其應(yīng)用等長等長編碼：編碼： 設(shè)這設(shè)這4個不同的字符為個不同的字符為A，B，C，D，則可進(jìn)，則可進(jìn)行等長編碼如下：行等長編碼如下：第16頁/共36頁3.哈夫曼編碼 二、哈夫曼樹及其應(yīng)用等長等長編碼：編碼： 設(shè)這設(shè)這4個不同的字符為個不同的字符為A，B，C，D，則可進(jìn)，則可進(jìn)行等長編碼如下：行等長編碼如下： A: 00 B: 01 C: 10 D: 11 則對于電文則對于電文“ABACCDA”的二進(jìn)制電碼為：的二進(jìn)制電碼為： 總長為總長為14位位 譯碼時，兩位一分進(jìn)

11、行譯碼，可唯一得到電文：譯碼時，兩位一分進(jìn)行譯碼，可唯一得到電文：ABACCDA 。第17頁/共36頁3.哈夫曼編碼 二、哈夫曼樹及其應(yīng)用壓縮編碼：壓縮編碼： 例如：例如：對于剛才的對于剛才的4個字符的編碼問題，可以按如個字符的編碼問題，可以按如下不等長編碼方案進(jìn)行編碼：下不等長編碼方案進(jìn)行編碼： A: 0 B: 00 C: 1 D: 01問題：問題：譯碼時可能出現(xiàn)多意性，即譯碼不唯一。譯碼時可能出現(xiàn)多意性，即譯碼不唯一。 則對于電文則對于電文“ABACCDA”的二進(jìn)制電碼為：的二進(jìn)制電碼為： 000011010 總長為總長為9位位 如如000011010中的前中的前4個個0的譯碼會有如下幾的

12、譯碼會有如下幾種不同譯碼：種不同譯碼： 0000AAAA；0000ABA；0000BB思考：如何解決這一問題？問題的關(guān)鍵在于編碼是否為無前綴編碼。第18頁/共36頁3.哈夫曼編碼 二、哈夫曼樹及其應(yīng)用無前綴無前綴壓縮編碼（既哈夫曼編碼）：壓縮編碼（既哈夫曼編碼）： * *思想思想：利用哈夫曼樹設(shè)計出來的不等長的編碼方：利用哈夫曼樹設(shè)計出來的不等長的編碼方案一定是無前綴的。案一定是無前綴的。* *方法方法：步驟步驟1：將各字符按照其：將各字符按照其“出現(xiàn)頻率出現(xiàn)頻率”的統(tǒng)計數(shù)字安排的統(tǒng)計數(shù)字安排一個一個“權(quán)值權(quán)值”并作為并作為“葉子葉子”，并求出相應(yīng)的哈夫曼樹；，并求出相應(yīng)的哈夫曼樹；步驟步驟2

13、：樹中各結(jié)點到其左孩子的邊上的權(quán)值設(shè)為：樹中各結(jié)點到其左孩子的邊上的權(quán)值設(shè)為0、到、到其右孩子的邊上的權(quán)值設(shè)為其右孩子的邊上的權(quán)值設(shè)為1（即所謂左（即所謂左0右右1）；）； 步驟步驟3：從根開始到：從根開始到“葉子葉子”所經(jīng)歷的邊上的數(shù)值的序所經(jīng)歷的邊上的數(shù)值的序列即為該列即為該“葉子葉子”所對應(yīng)的字符的編碼。所對應(yīng)的字符的編碼。第19頁/共36頁三、實例 已知某通信用電文僅由A、B、C、D這4個字符構(gòu)成，其出現(xiàn)的頻率分別為：8、4、6、2，請給出它們的哈夫曼編碼，要求寫出相應(yīng)的哈夫曼樹。解：根據(jù)哈夫曼算法，求得哈夫曼樹如下：208122664BDAC010101 從根開始到葉子得各字從根開始

14、到葉子得各字符的哈夫曼編碼如下：符的哈夫曼編碼如下：A :0 B:100 C:11 D:101 則對于電文則對于電文“ABACCDA”的的二進(jìn)制電碼為：二進(jìn)制電碼為： 總長為總長為13位位第20頁/共36頁四、小結(jié)四、小結(jié): :4. 4.哈夫曼哈夫曼樹的應(yīng)用：哈夫曼編碼的設(shè)計問題。樹的應(yīng)用：哈夫曼編碼的設(shè)計問題。2. 2.哈夫曼哈夫曼樹的定義：樹的定義：WPL=wi*li最小的二叉樹稱為最小的二叉樹稱為“最優(yōu)二叉樹最優(yōu)二叉樹”或或稱稱為為“哈夫曼樹哈夫曼樹”。3.3.哈夫曼哈夫曼樹求解的算法思想：樹求解的算法思想：3個步驟。個步驟。1. 1.哈夫曼哈夫曼樹的引入：程序優(yōu)化問題。樹的引入：程序優(yōu)

15、化問題。i=1nn第21頁/共36頁 哈夫曼樹的性質(zhì) 哈夫曼樹中沒有度為1的結(jié)點 一棵有N個葉子的哈夫曼樹中有2N-1個結(jié)點 給定權(quán)值的哈夫曼樹不唯一 權(quán)值越大的節(jié)點離根節(jié)點越近 第22頁/共36頁作業(yè)作業(yè): :1.假設(shè)用于通信的電文僅由假設(shè)用于通信的電文僅由6個字母個字母 A,B,C,D,E,F組成組成,這這6個字母在電文中出現(xiàn)的頻率高低依次為：個字母在電文中出現(xiàn)的頻率高低依次為：3,4,5,8,9,4,試為這試為這6個字母設(shè)計哈夫曼編碼。個字母設(shè)計哈夫曼編碼。2.證明證明:若哈夫曼樹中有若哈夫曼樹中有n個葉子結(jié)點個葉子結(jié)點,則該哈夫曼樹則該哈夫曼樹中共有中共有2n-1個結(jié)點。（提示：哈夫曼

16、樹中無度數(shù)為個結(jié)點。（提示：哈夫曼樹中無度數(shù)為1的結(jié)點的結(jié)點 ）第23頁/共36頁線索二叉樹 當(dāng)以二叉鏈表作為存儲結(jié)構(gòu)時，只能找到結(jié)點的左，右孩子的信息，而不能直接得到結(jié)點在任一序列中的前驅(qū)和后繼信息。 如果增加前驅(qū)和后繼指針，降低存儲效率 因為在有n個結(jié)點的二杈鏈表中必定存在n+1個空鏈域，故可以利用這些空鏈域來存放結(jié)點的前驅(qū)和后繼信息。第24頁/共36頁結(jié)構(gòu) leftThread=0 時 left指向左兒子； leftThread=1 時 left指向前驅(qū)； rightThread=0 時 right指向左子女； rightThread=1 時 right指向后繼；leftleftThre

17、adelementrightThreadright第25頁/共36頁注意： 一是何種“序”的線索化，是先序、中序還是后序； 二是要“前驅(qū)”線索化、“后繼”線索化還是“全”線索化（前驅(qū)后繼都要）； 三是只有空指針處才能加線索。第26頁/共36頁二叉搜索樹 二叉搜索樹又稱為二叉排序樹，其定義是一個遞歸過程： 它或者是一棵空樹；或者是具有下列性質(zhì)定義的二叉樹： 若左子樹不空，則左子樹上所有結(jié)若左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；若右子樹點的值均小于根結(jié)點的值；若右子樹不空，則右子樹上所有結(jié)點的值均大不空，則右子樹上所有結(jié)點的值均大于或等于根結(jié)點的值。于或等于根結(jié)點的值。 左右子樹都分

18、別是一棵二叉搜索樹 。 第27頁/共36頁 中序遍歷二叉搜索樹可以得到解決一個按關(guān)鍵字有序的序列。 構(gòu)造二叉搜索樹的目的不是為了排序，而是用來加速查找。第28頁/共36頁 二叉搜索樹的建立： 由空集為初始狀態(tài)，將結(jié)點按關(guān)鍵字依次插入到二叉樹中去。先將第一個結(jié)點作為二叉樹的根結(jié)點，插入其它結(jié)點時，若結(jié)點的值小于根結(jié)點的值，則插入左子樹，否則插入右子樹，該過程依次進(jìn)行，直到整個過程結(jié)束。 動態(tài)生成二叉排樹時，樹的形狀、高度不僅依賴于記錄關(guān)鍵字的大小，還與記錄輸入的先后順序有關(guān)第29頁/共36頁70，35，85，20，70，9070358520709020 ，35， 70 ， 70 ， 85 ，90203570708590第30頁/共36頁第31頁/共36頁查找結(jié)點 根據(jù)前面的定義可知，二叉搜索樹的查找是一個遞歸的過程，具體如下： 若二叉排序樹為空，則查找失敗，輸出相關(guān)信息。 若二叉查找樹不為空，將給定值x與查找樹的根結(jié)點關(guān)鍵字進(jìn)行比較。 若比較結(jié)果為相等，則查找成功，整個查找結(jié)束。第32頁/共36頁否則，完成下面的判斷： (i) 若給定的值x小于根結(jié)點關(guān)鍵字的值，查找將按照遞歸的方式在左子樹上進(jìn)行。 (ii)若給定的值x大于根結(jié)點關(guān)鍵字的值，查找將按照遞歸的方式在右子樹上進(jìn)行。 (iii)重復(fù)以上過程，直到查找