T17-樹(轉(zhuǎn)換、構(gòu)建與線索化)

轉(zhuǎn)換、構(gòu)建與線索化第八章：樹

主講：周翔樹與二叉樹的相互轉(zhuǎn)換樹與二叉樹的相互轉(zhuǎn)換ABEDCDECAB

孩子兄弟表示法樹與二叉樹的相互轉(zhuǎn)換樹與二叉樹的相互轉(zhuǎn)換ABEDCECAB

D

二叉鏈表樹與二叉樹的相互轉(zhuǎn)換樹轉(zhuǎn)化為二叉樹方法1：將樹的孩子兄弟表示法看成是二叉樹的二叉鏈表存儲結(jié)構(gòu)，即可實現(xiàn)轉(zhuǎn)化。方法2：樹中所有相鄰兄弟之間加一條連線；對樹中的每個結(jié)點，只保留其與第一個孩子結(jié)點之間的連線，刪去其與其他孩子結(jié)點之間的連線；以樹的根結(jié)點為軸心，將整棵樹順時針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。樹與二叉樹的相互轉(zhuǎn)換ABGECFDHABDECFGHABDECFGH樹與二叉樹的相互轉(zhuǎn)換將此二叉樹還原為樹ABDEFGHIJKMLC樹與二叉樹的相互轉(zhuǎn)換第一步：加線（虛線），將樹中每條右鏈中的所以右孩子都連接到右鏈鏈頭結(jié)點的父結(jié)點上；ABDEFGHIJKMLC樹與二叉樹的相互轉(zhuǎn)換第二步是去線，將原二叉樹中父結(jié)點與其右孩子的連線抹去；ABDEFGHIJKMLC樹與二叉樹的相互轉(zhuǎn)換第三步整理，去掉原二叉樹中的連接線后，將新的連接線由虛線變?yōu)閷嵕€，調(diào)整樹中結(jié)點的層次結(jié)構(gòu)；ABDEFGHIJKMLCABDEFGHIJKMLC樹、森林與二叉樹的相互轉(zhuǎn)換森林轉(zhuǎn)化為二叉樹的方法將森林中的每棵樹轉(zhuǎn)換成對應(yīng)的二叉樹；每一棵二叉樹不動，從第二棵二叉樹開始，依次將后一棵二叉樹的根結(jié)點作為前一棵二叉樹根結(jié)點的右孩子；當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。樹、森林與二叉樹的相互轉(zhuǎn)換ABDCEFGHIJABDCEFGHIJ樹、森林與二叉樹的相互轉(zhuǎn)換ABDCEFGHIJABDCEFGHIJ樹、森林與二叉樹的相互轉(zhuǎn)換二叉樹還原為森林或樹的方法若某結(jié)點是其雙親結(jié)點的左孩子，則把該結(jié)點的右孩子、右孩子的右孩子……都與該結(jié)點的雙親結(jié)點用線連起來；刪掉原二叉樹中所有雙親結(jié)點與右孩子結(jié)點的連線；整理前兩步所得到的樹或森林，使之結(jié)構(gòu)層次分明。樹、森林與二叉樹的相互轉(zhuǎn)換ABDCEFGHIJABDCEFGHIJ二叉樹的構(gòu)建——中序和先序中序和先序構(gòu)建二叉樹想要通過遍歷結(jié)果來確定一棵樹需要將兩種順序的遍歷結(jié)果結(jié)合起來。結(jié)合方案有以下兩種：中序遍歷結(jié)果和先序遍歷結(jié)果一起可以確定一棵二叉樹；中序遍歷結(jié)果和后序遍歷結(jié)果一起可以確定一棵二叉樹；即便結(jié)合先序遍歷和后序遍歷的結(jié)果也無法確定一棵二叉樹的的結(jié)構(gòu)，因為這兩種遍歷結(jié)果結(jié)合只能求解出根，不能確定左子樹什么時候結(jié)束，右子樹什么時候開始。二叉樹的構(gòu)建——中序和先序中序和先序構(gòu)建二叉樹根據(jù)中序遍歷和先序遍歷結(jié)果確定二叉樹結(jié)構(gòu)的基本思路如下：（1）通過先序遍歷找到根結(jié)點，再通過根節(jié)點在中序遍歷的位置找出左子樹、右子樹；（2）根據(jù)左子樹在先序遍歷結(jié)果的順序，找到左子樹的根結(jié)點，視左子樹為一棵獨立的樹，轉(zhuǎn)步驟（1）；（3）根據(jù)右子樹在先序遍歷結(jié)果的順序，找到右子樹的根結(jié)點，視右子樹為一棵獨立的樹，轉(zhuǎn)步驟（1）；二叉樹的構(gòu)建——中序和先序中序和先序構(gòu)建二叉樹假如有一棵二叉樹，它的先序遍歷結(jié)果為：ADEBCF；中序遍歷結(jié)果為：DEACFB。則確定此二叉樹的步驟如下：第一步：由先序遍歷結(jié)果可知，此二叉樹的根結(jié)點為A；再結(jié)合中序遍歷結(jié)果，可知A的左子樹為DE，右子樹為CFB；二叉樹的構(gòu)建——中序和先序中序和先序構(gòu)建二叉樹假如有一棵二叉樹，它的先序遍歷結(jié)果為：ADEBCF；中序遍歷結(jié)果為：DEACFB。則確定此二叉樹的步驟如下：第二步：A的左子樹中包含有DE兩個結(jié)點，由先序遍歷結(jié)果可知，D結(jié)點在E的前面，那么D是左子樹的根結(jié)點；又因在中序遍歷中，E結(jié)點在根結(jié)點D之后，先遍歷D后遍歷E，說明D是根結(jié)點，E是D的右孩子；二叉樹的構(gòu)建——中序和先序中序和先序構(gòu)建二叉樹假如有一棵二叉樹，它的先序遍歷結(jié)果為：ADEBCF；中序遍歷結(jié)果為：DEACFB。則確定此二叉樹的步驟如下：第三步：由整棵樹的先序遍歷結(jié)果可知右子樹的先序遍歷結(jié)果為：CFB，因此B是右子樹的根結(jié)點；又因為在中序遍歷中，CF都在B之前，說明C、F是B的左子樹結(jié)點；對以B為根節(jié)點的子樹繼續(xù)分析：在先序遍歷中，C在F的前面，說明在B的左子樹中，C是根結(jié)點；在中序遍歷中：F在C的后面，說明F是C的右孩子；二叉樹的構(gòu)建——中序和先序中序和先序構(gòu)建二叉樹這三個步驟分別確定了二叉樹的根結(jié)點、左子樹與右子樹，這樣就確定了一棵二叉樹。二叉樹的構(gòu)建——中序和先序已知一棵二叉樹的以下兩種遍歷結(jié)果，試畫出這棵二叉樹。前序遍歷的結(jié)果是ABECDFGHIJ中序遍歷的結(jié)果是EBCDAFHIGJABCEDFGIHJ二叉樹的構(gòu)建——中序和先序一棵二叉樹前序遍歷和中序遍歷序列如下所示：前序：DACEBHFGI；中序：DCBEHAGIF;試畫出二叉樹結(jié)構(gòu)，并簡述求算過程。二叉樹的構(gòu)建——#號法#號法創(chuàng)建樹#號法就是讓樹的每一個結(jié)點都變成度數(shù)為2的樹，度不為2的結(jié)點就用“#”符號補齊。二叉樹的構(gòu)建——#號法#號法創(chuàng)建樹假設(shè)有一棵二叉樹先序遍歷結(jié)果為：DFE###B##。第一步：先序遍歷，那么D就是這棵樹的根結(jié)點；D的左孩子為F，F(xiàn)的左孩子為E。二叉樹的構(gòu)建——#號法#號法創(chuàng)建樹假設(shè)有一棵二叉樹先序遍歷結(jié)果為：DFE###B##。第二步：E結(jié)點后面緊跟了兩個“#”符號，則E為葉子結(jié)點。二叉樹的構(gòu)建——#號法#號法創(chuàng)建樹假設(shè)有一棵二叉樹先序遍歷結(jié)果為：DFE###B##。第三步：E后面還有第三個“#”符號，則這個符號必為F的右孩子。二叉樹的構(gòu)建——#號法#號法創(chuàng)建樹假設(shè)有一棵二叉樹先序遍歷結(jié)果為：DFE###B##。第四步：D的右子樹為B##，B為一個葉子結(jié)點。只需輸入AB#DF##G##C#E#H##，便可創(chuàng)建出如下二叉樹二叉樹的構(gòu)建——#號法ABCEDHFG什么是線索二叉樹用指針實現(xiàn)二叉樹時，每個結(jié)點只有指向其左、右兒子結(jié)點的指針，所以從任一結(jié)點出發(fā)能直接找到該結(jié)點的左、右兒子。那么，可不可以像找孩子一樣方便地找到某個結(jié)點的前驅(qū)或后繼呢？

ABCDFEroot什么是線索二叉樹如果改造結(jié)點，在每個結(jié)點中增加指向直接前驅(qū)和直接后繼結(jié)點的指針，顯然將降低存儲效率線索二叉樹用指針實現(xiàn)二叉樹時，在n個結(jié)點二叉樹中含有n+1個空指針（閑置）改造方案：利用閑置的空指針。存放指向結(jié)點某種遍歷次序下的前驅(qū)和后繼結(jié)點的指針。這種附加的指針稱為“線索”，加上了線索的二叉樹為線索(化)二叉樹。什么是線索二叉樹在二叉鏈表表示的二叉樹中，利用空閑空間來存儲結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點的信息，通常把這種指向前驅(qū)和后繼的指針稱為線索，帶有線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹。線索二叉樹添加了“線索”的中序線索化二叉樹

ABCDFEroot問題：

那么如何區(qū)分當(dāng)前指針是指向孩子結(jié)點，還是指向前驅(qū)（后繼）？線索二叉樹線索化二叉樹的結(jié)點結(jié)構(gòu)Ltag=0,LChild為左子女指針Ltag=1,LChild為前驅(qū)線索Rtag=0,RChild為右子女指針Rtag=1,RChild為后繼線索LChildRChilddataLtagRtag線索二叉樹中序線索化二叉樹線索二叉樹中序線索化二叉樹中，如何尋找當(dāng)前結(jié)點在中序下的直接后繼？ABDECFHIKGJL線索二叉樹中序結(jié)索化二叉樹中，如何尋找當(dāng)前結(jié)點在中序下的直接前驅(qū)？ABDECFHIKGJL線索二叉樹線索化對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程線索二叉樹加上線索的二叉樹（圖形式樣）線索鏈表加上線索二叉鏈表線索指向結(jié)點前驅(qū)和后繼的指針哈夫曼樹游戲中主角的生命值d，有這樣的條件判定：當(dāng)怪物碰到主角后，怪物的反應(yīng)遵從下規(guī)則:解決該問題，我們通常習(xí)慣用if等多分支語句進行處理，但效率不高哈夫曼樹分析主角生命值d的特點，即預(yù)測出每種條件占總條件的百分比，將這些比值作為權(quán)值來構(gòu)造最優(yōu)二叉樹（哈夫曼樹），作為判定樹來設(shè)定算法。效率提高哈夫曼樹在了解哈夫曼樹之前，首先來學(xué)習(xí)幾個術(shù)語：路徑：由一結(jié)點到另一結(jié)點間的分支所構(gòu)成路徑長度：路徑上的分支數(shù)目。a→e的路徑長度＝2帶權(quán)路徑長度：結(jié)點到根的路徑長度與結(jié)點上權(quán)的乘積樹的帶權(quán)路徑長度（WeightedPathLengthofTree，簡記為WPL）：樹中所有葉子結(jié)點的帶權(quán)路徑長度之和哈夫曼樹：帶權(quán)路徑長度最小的樹debacfg哈夫曼樹哈夫曼樹的構(gòu)造：根據(jù)給定的n個權(quán)值{w1,w2,……wn}，構(gòu)造n棵只有根結(jié)點的二叉樹；在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點權(quán)值為其左右子樹根結(jié)點權(quán)值之和。在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中。重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹。權(quán)值分別為7，5，2，4，構(gòu)造有4個葉子結(jié)點的二叉樹哈夫曼樹dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*2+5*2+2*2+4*2=36權(quán)值分別為7，5，2，4，構(gòu)造有4個葉子結(jié)點的二叉樹哈夫曼樹abcd7524WPL=7*1+5*2+2*3+4*3=35哈夫曼樹哈夫曼樹的構(gòu)造過程：a7b5c2d4a7b5c2d46a7b5c2d411a7b5c2d418a7b5c2d4哈夫曼樹哈夫曼樹的構(gòu)造過程：基本思想：使權(quán)大的結(jié)點靠近根操作要點：對權(quán)值的合并、刪除與替換，總是合并當(dāng)前值最小的兩個哈夫曼樹哈夫曼編碼：在遠程通訊中，要將待傳字符轉(zhuǎn)換成二進制的字符串，怎樣編碼才能使它們組成的報文在網(wǎng)絡(luò)中傳得最快？ABACCDA000110010101100000011010出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼哈夫曼樹哈夫曼編碼：

0000AAAAABABB重碼ABACCDA000011010關(guān)鍵：要設(shè)計長度不等的編碼，則必須使任一字符的編碼都不是另一個字符的編碼的前綴－前綴編碼哈夫曼樹哈夫曼編碼：ACBD000111采用二叉樹設(shè)計前綴編碼左分支用“0”右分支用“1”A—0B—110C—10D—111

0110010101110ABACCDA哈夫曼樹哈夫曼編碼：分解接收字符串：遇“0”向左，遇“1”向右；一旦到達葉子結(jié)點，則譯出一個字符，反復(fù)由根出發(fā)，直到譯碼完成。0110010101110ACBD000111ABACCDA特點：每一碼都不是另一碼的前綴，絕不會錯譯!稱為前綴碼哈夫曼樹哈夫曼編碼的基本思想：概率大的字符用短碼，小的用長碼，構(gòu)造哈夫曼樹例：某系統(tǒng)在通訊時，只出現(xiàn)C，A，S，T，B五種字符，其出現(xiàn)頻率依次為2，4，2，3，3，試設(shè)計Huffman編碼。148464220001113301TBACST

00B

01A

10C

110S

111哈夫曼樹哈夫曼編碼的幾點結(jié)論：哈夫曼編碼是不等長編碼。哈夫曼編碼是前綴編碼，即任一字符的編碼都不是另一字符編碼的前綴。哈夫曼編碼樹中沒有度為1的結(jié)點。若葉子結(jié)點的個數(shù)為n，則哈夫曼編碼樹