數(shù)據(jù)結(jié)構(gòu) 樹與二叉樹

數(shù)據(jù)結(jié)構(gòu)樹與二叉樹第1頁，共24頁，2023年，2月20日，星期六7.7二叉排序樹(1)若它的左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；1．定義：二叉排序樹(二叉搜索樹或二叉查找樹)或者是一棵空樹；或者是具有如下特性的二叉樹(3)它的左、右子樹也都分別是二叉排序樹。(2)若它的右子樹不空，則右子樹上所有結(jié)點的值均大于等于根結(jié)點的值；第2頁，共24頁，2023年，2月20日，星期六7.7二叉排序樹503080209010854035252388例如:是二叉排序樹。66不對二叉排序樹進行中序遍歷，得到一個有序序列第3頁，共24頁，2023年，2月20日，星期六7.7二叉排序樹452412145390中序遍歷:12,14,24,45,53,90二叉排序樹的構(gòu)造特點：樹結(jié)構(gòu)在查找的過程中動態(tài)生成。

每次插入的結(jié)點只能成為新的葉子結(jié)點例：關(guān)鍵字序列為{45，24，53，12，14，90}第4頁，共24頁，2023年，2月20日，星期六7.7二叉排序樹二叉排序樹構(gòu)造—遞歸算法與非遞歸算法p142第5頁，共24頁，2023年，2月20日，星期六7.7二叉排序樹二叉排序刪除節(jié)點（1）若被刪除節(jié)點為葉結(jié)點，則可以直接刪除（2）若被刪除結(jié)點沒有左子樹，則可以用其右子樹的跟結(jié)點取代被刪除結(jié)點的位置（3）若被刪除結(jié)點沒有右子樹，則可以用其左子樹的跟結(jié)點取代被刪除結(jié)點的位置（4）若被刪除結(jié)點的左、右子樹均存在，則要找到右子樹中值最小的結(jié)點（r），用該節(jié)點取代被刪除節(jié)點的位置。由于由r指出的節(jié)點的位置一定沒有左子樹，所以用其右孩子來取代r所指節(jié)點的位置。第6頁，共24頁，2023年，2月20日，星期六7.7二叉排序樹二叉排序刪除節(jié)點（1）若被刪除節(jié)點為葉結(jié)點，則可以直接刪除（2）若被刪除結(jié)點沒有左子樹，則可以用其右子樹的跟結(jié)點取代被刪除結(jié)點的位置（3）若被刪除結(jié)點沒有右子樹，則可以用其左子樹的跟結(jié)點取代被刪除結(jié)點的位置（4）若被刪除結(jié)點的左、右子樹均存在，則要找到右子樹中值最小的結(jié)點（r），用該節(jié)點取代被刪除節(jié)點的位置。由于由r指出的節(jié)點的位置一定沒有左子樹，所以用其右孩子來取代r所指節(jié)點的位置。第7頁，共24頁，2023年，2月20日，星期六7.7二叉排序樹1）若給定值等于根結(jié)點的關(guān)鍵字，則查找成功；2）若給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)在左子樹上進行查找；3）若給定值大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右子樹上進行查找。否則二叉排序樹的查找——查找算法若二叉排序樹為空，則查找不成功；第8頁，共24頁，2023年，2月20日，星期六7.7二叉排序樹平均查找長度：確定一個元素在樹中的位置所需進行的比較次數(shù)節(jié)點內(nèi)路徑長度（IPL）：從二叉樹根節(jié)點到某節(jié)點所經(jīng)過的分枝數(shù)，定義為該節(jié)點的內(nèi)經(jīng)長度二叉樹內(nèi)路徑長度：外路徑長度（XPL）：外邊結(jié)點內(nèi)部結(jié)點EPL：二叉樹中所有外邊結(jié)點的路徑之和二叉排序樹的查找——查找長度第9頁，共24頁，2023年，2月20日，星期六7.7二叉排序樹查找成功的平均查找長度

ASL=（IPL+n)/n查找失敗的平均查找長度

ASL=EPL/n=(IPL+2n)/n平均查找長度

ASL=(IPL+n+EPL)/(n+n+1)=(2IPL+3n)/2n+1二叉排序樹的查找——查找長度第10頁，共24頁，2023年，2月20日，星期六7.9哈夫曼樹及其應(yīng)用問題的提出：例：編制一個將百分制轉(zhuǎn)換為五級分制的程序。如：

if(a<60)b=”bad”;elseif(a<70)b=”pass”elseif(a<80)b=”general”elseif(a<90)b=”good”elseb=”excellent”;第11頁，共24頁，2023年，2月20日，星期六7.9哈夫曼樹及其應(yīng)用顯然，此程序很簡單，只要利用條件語句便可完成。如果上述程序需反復(fù)使用，而且每次的輸入量很大，則應(yīng)考慮上述程序的質(zhì)量問題，即其操作所需要的時間。因為在實際中，學(xué)生的成績在五個等級上的分布是不均勻的，假設(shè)其分布規(guī)律如下表所示：分數(shù)0－5960－6970－7980－8990－100比例數(shù)0.050.150.400.300.10則80%以上的數(shù)據(jù)需進行三次或三次以上的比較才能得出結(jié)果。第12頁，共24頁，2023年，2月20日，星期六7.9哈夫曼樹及其應(yīng)用葉子結(jié)點的權(quán)值：對葉子結(jié)點賦予的一個有意義的數(shù)值量。二叉樹的帶權(quán)路徑長度：設(shè)二叉樹具有n個帶權(quán)值的葉子結(jié)點，從根結(jié)點到各個葉子結(jié)點的路徑長度與相應(yīng)葉子結(jié)點權(quán)值的乘積之和。

記為：WPL=?=nkkklw1第k個葉子的權(quán)值；從根結(jié)點到第k個葉子的路徑長度第13頁，共24頁，2023年，2月20日，星期六編碼：給每一個對象標記一個二進制位串來表示一組對象。例：ASCII，指令系統(tǒng)等長編碼：表示一組對象的二進制位串的長度相等。不等長編碼：表示一組對象的二進制位串的長度不相等。不等長編碼什么情況下空間效率高？等長編碼什么情況下空間效率高？7.9哈夫曼樹及其應(yīng)用第14頁，共24頁，2023年，2月20日，星期六7.9哈夫曼樹及其應(yīng)用前綴編碼：一組編碼中任一編碼都不是其它任何一個編碼的前綴。前綴編碼保證了在解碼時不會有多種可能。

第15頁，共24頁，2023年，2月20日，星期六7.9哈夫曼樹及其應(yīng)用哈夫曼樹：給定一組具有確定權(quán)值的葉子結(jié)點，帶權(quán)路徑長度最小的二叉樹。例：給定4個葉子結(jié)點，其權(quán)值分別為{2，3，4，7}，可以構(gòu)造出形狀不同的多個二叉樹。

WPL=32WPL=41WPL=30234723477423第16頁，共24頁，2023年，2月20日，星期六7.9哈夫曼樹及其應(yīng)用哈夫曼樹的特點：1.權(quán)值越大的葉子結(jié)點越靠近根結(jié)點，而權(quán)值越小的葉子結(jié)點越遠離根結(jié)點。2.只有度為0（葉子結(jié)點）和度為2（分支結(jié)點）的結(jié)點，不存在度為1的結(jié)點.

234723477423第17頁，共24頁，2023年，2月20日，星期六7.9哈夫曼樹及其應(yīng)用第1步：初始化W＝{2，3，4，5}

哈夫曼樹的構(gòu)造過程3524第2步：選取與合并32

5第3步：刪除與加入5432

5第18頁，共24頁，2023年，2月20日，星期六7.9哈夫曼樹及其應(yīng)用W＝{2，3，4，5}

哈夫曼樹的構(gòu)造過程重復(fù)第2步5432

554

9重復(fù)第3步

554

932第19頁，共24頁，2023年，2月20日，星期六7.9哈夫曼樹及其應(yīng)用重復(fù)第2步重復(fù)第3步

554

932

554

93214W＝{2，3，4，5}

哈夫曼樹的構(gòu)造過程第20頁，共24頁，2023年，2月20日，星期六7.9哈夫曼樹及其應(yīng)用例：一組字符{A,B,C,D,E,F,G}出現(xiàn)的頻率分別是{9,11,5,7,8,2,3}，設(shè)計最經(jīng)濟的編碼方案。第21頁，共24頁，2023年，2月20日，星期六7.9哈夫曼樹及其應(yīng)用9523510191126871545000000111111ABDCEFG編碼方案：A：00B：10C：010D：110E：111F：0110G：0111第22頁，共24頁，2023年，2月20日，星期六7.9哈夫曼樹及其應(yīng)用哈夫曼算法的存儲結(jié)構(gòu)設(shè)置一個數(shù)組（向量）huffTree[2n-1]保存哈夫曼樹中各點的信息，數(shù)組（向量）元素的結(jié)點結(jié)構(gòu)。weight：權(quán)值域，保存該結(jié)點的權(quán)值；lchild：指針域，結(jié)點的左孩子結(jié)點在數(shù)組中的下標；rchild：指針域，結(jié)點的右孩子結(jié)點在數(shù)組中的下標；parent：指針域，該結(jié)點的雙親結(jié)點在數(shù)組中的下標。

weightlchildrchildparent第23頁，共24頁，2023年，2月20日，星期六樹結(jié)構(gòu)樹二叉樹邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)存儲結(jié)構(gòu)存儲結(jié)構(gòu)樹的定義基