第6章樹及二叉樹C

1、1第第6章章 樹和二叉樹（樹和二叉樹（ Tree & Binary Tree ）6.1 樹的基本概念樹的基本概念6.2 二叉樹二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 樹和森林樹和森林6.5 赫夫曼樹及其應用赫夫曼樹及其應用2上堂課例題討論上堂課例題討論問問: : 設一棵完全二叉樹具有設一棵完全二叉樹具有10001000個結(jié)點，則它有個結(jié)點，則它有 個葉個葉子結(jié)點，有子結(jié)點，有 個度為個度為2 2的結(jié)點，有的結(jié)點，有 個結(jié)點只有非空左子個結(jié)點只有非空左子樹，有樹，有 個結(jié)點只有非空右子樹。個結(jié)點只有非空右子樹。法法1 1：先先求全部葉子數(shù)。求全部葉子數(shù)。n n0 048

2、9489( (末層末層) )1111(k-1(k-1層層) )= =500500個；個；法法2 2：先求先求2 2度結(jié)點數(shù)。度結(jié)點數(shù)。n n2 2=255=255( (k-2層層) )244244( (k-1層層) )= =499499個；個； 這兩種方法的缺點：都要先計算樹的深度這兩種方法的缺點：都要先計算樹的深度 k=k= log2n 1 =10; =10; 法法3 3：無需求樹深無需求樹深k k，便可快捷求出，便可快捷求出 取大于取大于n/2n/2的最小整數(shù)值的最小整數(shù)值 可由二叉樹性質(zhì)可由二叉樹性質(zhì)5 5輕松證明！輕松證明！( (編號為編號為i i的結(jié)點，其孩子編號必為的結(jié)點，其孩子編

3、號必為2i2i和和2i+1)2i+1) nn已知最后一個結(jié)點編號為已知最后一個結(jié)點編號為n n，則其雙親（，則其雙親（n/2n/2或或(n-1)/2)(n-1)/2)肯定是最后一個非葉子結(jié)點。其編號之后的全部結(jié)點都肯定是最后一個非葉子結(jié)點。其編號之后的全部結(jié)點都是葉子了！是葉子了！故，故，n0=n-n/2n0=n-n/2或或n-(n-1)/2= n-(n-1)/2= 3問：問：用二叉鏈表法（用二叉鏈表法（l_child, r_childl_child, r_child）存儲包含）存儲包含n n個結(jié)點個結(jié)點的二叉樹，結(jié)點的指針區(qū)域中必有的二叉樹，結(jié)點的指針區(qū)域中必有 個空指針。個空指針。思考：思

4、考：二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？有用的信息或線索？所以，所以， 空指針個數(shù)空指針個數(shù)2n(n-1)=n+1個個。n+1分析：分析：n n個結(jié)點必有個結(jié)點必有2n個鏈域；個鏈域； （見二叉鏈表數(shù)據(jù)類型說明）（見二叉鏈表數(shù)據(jù)類型說明）除根結(jié)點外，二叉樹中每一個結(jié)點除根結(jié)點外，二叉樹中每一個結(jié)點有且僅有一個雙親有且僅有一個雙親（直接（直接前驅(qū)），所以只會有前驅(qū)），所以只會有n n1 1個結(jié)點的鏈域存放指針，指向非空子個結(jié)點的鏈域存放指針，指向非空子女結(jié)點（即直接后繼）。女結(jié)點（即直接后繼）。4二、線索二叉樹線索二叉樹（

5、Threaded Binary Tree）普通二叉樹只能找到結(jié)點的左右孩子信息，普通二叉樹只能找到結(jié)點的左右孩子信息，而該結(jié)點而該結(jié)點的直接前驅(qū)和直接后繼只能在遍歷過程中獲得。的直接前驅(qū)和直接后繼只能在遍歷過程中獲得。若將若將遍歷后遍歷后對應的有關前驅(qū)和后繼對應的有關前驅(qū)和后繼預存預存起來，則從起來，則從第第一個結(jié)點一個結(jié)點開始就能很快開始就能很快“順藤摸瓜順藤摸瓜”而遍歷整個樹了。而遍歷整個樹了。兩種解決方法：兩種解決方法：增加兩個域：增加兩個域：fwd和和bwd；存放前驅(qū)指針存放前驅(qū)指針存放后繼指針存放后繼指針如何預存這類信息？如何預存這類信息？例如中序遍歷結(jié)果：例如中序遍歷結(jié)果：B D

6、C E A F H GB D C E A F H G，實際上，實際上已將二叉已將二叉樹轉(zhuǎn)為樹轉(zhuǎn)為線性排列線性排列，顯然具有唯一前驅(qū)和唯一后繼。，顯然具有唯一前驅(qū)和唯一后繼。1. 1. 定義定義 2. 2. 生成生成 3. 3. 遍歷遍歷利用空鏈域（利用空鏈域（n+1個空鏈域）個空鏈域）5規(guī)定：規(guī)定：1）若結(jié)點有左子樹，則）若結(jié)點有左子樹，則lchild指向其左孩子；指向其左孩子； 否則，否則， lchild指向其直接前驅(qū)指向其直接前驅(qū)(即線索即線索)；2）若結(jié)點有右子樹，則）若結(jié)點有右子樹，則rchild指向其右孩子；指向其右孩子； 否則，否則， rchild指向其直接后繼指向其直接后繼(即線

7、索即線索) 。為區(qū)別兩種不同情況，特增加兩個標志域（各為區(qū)別兩種不同情況，特增加兩個標志域（各1bit)lchilddatarchild約定約定:當當Tag域為域為0時時,表示表示正常正常情況情況;當當Tag域為域為1時時,表示表示線索線索情況情況.右孩子或后繼右孩子或后繼左孩子或前驅(qū)左孩子或前驅(qū)LTagRTag6附：有關線索二叉樹的幾個術語：附：有關線索二叉樹的幾個術語： 線索鏈表：線索鏈表：用用含含Tag的結(jié)點樣式所構成的二叉鏈表的結(jié)點樣式所構成的二叉鏈表 線線 索：索：指向結(jié)點前驅(qū)和后繼的指針指向結(jié)點前驅(qū)和后繼的指針線索二叉樹：線索二叉樹：加上線索的二叉樹加上線索的二叉樹 線線 索索 化

8、：化：對二叉樹以對二叉樹以某種次序遍歷某種次序遍歷使其變?yōu)榫€索二使其變?yōu)榫€索二叉樹的過程叉樹的過程討論：討論：增加了前驅(qū)和后繼等線索有什么好處？增加了前驅(qū)和后繼等線索有什么好處？能方便找出當前結(jié)點的前驅(qū)和后繼，不用能方便找出當前結(jié)點的前驅(qū)和后繼，不用堆棧也能遍歷整個樹。堆棧也能遍歷整個樹。7dataAGEIDJHCFBltag0011110101rtag0001010111AGEIDJHCFB例：例：某某先序遍歷先序遍歷結(jié)果如下表所示，請畫出對應的結(jié)果如下表所示，請畫出對應的二叉樹。二叉樹。（多帶了兩個標志?。ǘ鄮Я藘蓚€標志?。?2. 2. 線索二叉樹的生成線索二叉樹的生成線索化過程就是線索

9、化過程就是在遍歷過程中修改空指針在遍歷過程中修改空指針的過程：的過程：將空的將空的l lchildchild改為結(jié)點的直接前驅(qū)；改為結(jié)點的直接前驅(qū)；將空的將空的r rchildchild改為結(jié)點的直接后繼。改為結(jié)點的直接后繼。非空指針呢？仍然指向孩子結(jié)點（稱為非空指針呢？仍然指向孩子結(jié)點（稱為“正常情況正常情況”）9ABCGEIDHFroot懸空？懸空？懸空？懸空？解：解：該二叉樹中序遍歷結(jié)果為該二叉樹中序遍歷結(jié)果為: : H, D, I, B, E, A, F, C, G所以添加線索應當按如下路徑進行：所以添加線索應當按如下路徑進行：為避免懸空為避免懸空態(tài)，應增設態(tài)，應增設一個頭結(jié)點一個頭結(jié)

10、點例例1 1：畫出以下二叉樹對應的畫出以下二叉樹對應的中序中序線索二叉樹。線索二叉樹。1000A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為注：此圖中序遍歷結(jié)果為: : H, D, I, B, E, A, F, C, G0-root0對應的中序線索二叉樹存儲結(jié)構如圖所示：對應的中序線索二叉樹存儲結(jié)構如圖所示：11例例2 2：【 計算機系考研題計算機系考研題】給定如圖所示二叉樹給定如圖所示二叉樹T T，請畫出與其對應的中序線索二叉樹。請畫出與其對應的中序線索二叉樹。 2825405560330854解解: :因為中序遍歷序列是：因為中序遍歷序列是：5555 40 25

11、60 40 25 60 2828 08 33 08 33 5454對應線索樹應當按此規(guī)律連線，即對應線索樹應當按此規(guī)律連線，即在原二叉樹中添加虛線。在原二叉樹中添加虛線。NILNILNILNIL12線索二叉樹的生成算法線索二叉樹的生成算法（算法算法6.6, 見教材見教材P134）目的：目的：在在依某種順序遍歷依某種順序遍歷二叉樹時修改空指針，添加前驅(qū)或后繼。二叉樹時修改空指針，添加前驅(qū)或后繼。注解：注解：為方便添加結(jié)點的前驅(qū)或后繼，需要設置兩個指針：為方便添加結(jié)點的前驅(qū)或后繼，需要設置兩個指針： p指針指針當前結(jié)點之指針；當前結(jié)點之指針； pre指針指針前驅(qū)結(jié)點之指針。前驅(qū)結(jié)點之指針。技巧：技

12、巧：當結(jié)點當結(jié)點p的左的左/右域為空右域為空時，只改寫它的左域（裝入前驅(qū)時，只改寫它的左域（裝入前驅(qū)pre），而其右域（后繼）留給下一結(jié)點來填寫。，而其右域（后繼）留給下一結(jié)點來填寫。 或者說，當前結(jié)點的指針或者說，當前結(jié)點的指針p應當送到前驅(qū)結(jié)點的空右域中。應當送到前驅(qū)結(jié)點的空右域中。若若p-lchildNULL, ,則則p-Ltag=1;p-Ltag=1;p-lp-lchildchildprepre; ; /p/p的前驅(qū)結(jié)點指針的前驅(qū)結(jié)點指針prepre存入左空域存入左空域若若pre-rchildNULL, 則則pre-Rtagpre-Rtag1;1;pre-rpre-rchildchil

13、d= =p p; / /p p存入其前驅(qū)結(jié)點存入其前驅(qū)結(jié)點prepre的右空域的右空域133. 3. 線索二叉樹的遍歷線索二叉樹的遍歷理論上，只要找到序列中的理論上，只要找到序列中的第一個結(jié)點第一個結(jié)點，然后，然后依次訪依次訪問結(jié)點的后繼問結(jié)點的后繼直到后繼為空時結(jié)束。直到后繼為空時結(jié)束。在線索化二叉樹中，并不是每個結(jié)點都能直接找到其在線索化二叉樹中，并不是每個結(jié)點都能直接找到其后繼的，后繼的，當標志為當標志為0 0時，時，R_child=R_child=右孩子地址指針，并非后繼！右孩子地址指針，并非后繼！需要通過一定運算才能找到它的后繼。需要通過一定運算才能找到它的后繼。以以中序線索二叉樹中

14、序線索二叉樹為例：為例：對葉子結(jié)點（對葉子結(jié)點（RTag=1），直接后繼指針就在其），直接后繼指針就在其rchild域內(nèi)；域內(nèi)；對其他結(jié)點（對其他結(jié)點（RTag=0），直接后繼是其），直接后繼是其右子樹最左下的結(jié)點右子樹最左下的結(jié)點；（因為中序遍歷規(guī)則是（因為中序遍歷規(guī)則是LDR，）14程序注解程序注解 (非遞歸，且不用棧非遞歸，且不用棧）：）：P=T-lchild; /從頭結(jié)點進入到根結(jié)點；從頭結(jié)點進入到根結(jié)點；while( p!=T) while(p-LTag=link)p=p-lchild; /先找到中序遍歷起點先找到中序遍歷起點 if(!visit(p-data) return ERR

15、OR; /若起點值為空則出錯告警若起點值為空則出錯告警 while(p-RTag=Thread ) p=p-rchild; Visit(p-data); /若有后繼標志，則直接提取若有后繼標志，則直接提取p-rchild中線索并中線索并訪問后繼結(jié)點；訪問后繼結(jié)點；p=p-rchild; /當前結(jié)點右域不空當前結(jié)點右域不空或或已經(jīng)找好了后繼已經(jīng)找好了后繼，則一律從，則一律從結(jié)點的右子樹開始重復結(jié)點的右子樹開始重復 的全部過程。的全部過程。Return OK;線索二叉樹的線索二叉樹的中序中序遍歷算法遍歷算法（算法算法6.5, 參見教材參見教材P134）LTag=0RTag=115算法流程：算法流程

16、：return OK;p=T-lchild;p!=Tp-LTag=0p=p-lchild;vist(p-data);p-LTag=1&p-rchild!=Tp=p-rchild;visit(p-data);p=p-rchild;YNYNYN演演示示程程序序16提前介紹：二叉樹的應用提前介紹：二叉樹的應用平衡樹平衡樹排序樹排序樹字典樹字典樹判定樹判定樹帶權樹帶權樹最優(yōu)樹最優(yōu)樹特點：左右子樹深度差特點：左右子樹深度差 1特點：特點：“左小右大左小右大”（見實驗二的方案（見實驗二的方案1）由字符串構成的二叉樹排序樹由字符串構成的二叉樹排序樹例如，例如，12個球只稱個球只稱3次分出輕重次分出輕重特點：

17、路徑長度帶權值特點：路徑長度帶權值 帶權路徑長度最短的樹，又稱帶權路徑長度最短的樹，又稱 Huffman樹，用途之一是通信中的壓縮編碼。樹，用途之一是通信中的壓縮編碼。17路路 徑徑：路徑長度路徑長度：樹的路徑長度樹的路徑長度：帶權路徑長度帶權路徑長度：樹的帶權路徑長度樹的帶權路徑長度：霍霍 夫夫 曼曼 樹樹：6.5 Huffman6.5 Huffman樹及其應用樹及其應用一、最優(yōu)二叉樹（一、最優(yōu)二叉樹（霍夫曼霍夫曼樹）樹）由一結(jié)點到另一結(jié)點間的分支所構成由一結(jié)點到另一結(jié)點間的分支所構成路徑上的分支數(shù)目路徑上的分支數(shù)目從樹根到從樹根到每一結(jié)點每一結(jié)點的路徑長度之和。的路徑長度之和。結(jié)點到根的路

18、徑長度與結(jié)點上權的乘積結(jié)點到根的路徑長度與結(jié)點上權的乘積預備知識：若干術語預備知識：若干術語debacf g樹中所有樹中所有葉子結(jié)點葉子結(jié)點的帶權路徑長度之和的帶權路徑長度之和帶權路徑長度最小的樹。帶權路徑長度最小的樹。aeae的路徑長度的路徑長度樹長度樹長度2 2101018HuffmanHuffman樹簡介：樹簡介：樹的帶權路徑長度如何計算？樹的帶權路徑長度如何計算？WPLWPL = = w wk kl lk k k=1k=1n nabdc7524(a)cdab2457(b)bdac7524(c)WPL=36WPL=46WPL= 35哈夫曼哈夫曼樹樹則則是是：WPL WPL 最小的樹。最小

19、的樹。Huffman樹樹Weighted Path LengthWeighted Path Length19構造霍夫曼樹的基本思想：構造霍夫曼樹的基本思想：構造構造HuffmanHuffman樹的步驟（即樹的步驟（即HuffmanHuffman算法）：算法）：20設有設有4 4個字符個字符d,i,a,nd,i,a,n，出現(xiàn)的頻度分別為，出現(xiàn)的頻度分別為7,5,2, 7,5,2, 4 4，怎樣編碼才能使它們組成的報文在網(wǎng)絡中傳得最快？，怎樣編碼才能使它們組成的報文在網(wǎng)絡中傳得最快？法法1 1：等長編碼等長編碼。例如用二進制編碼來實現(xiàn)。例如用二進制編碼來實現(xiàn)。 取取 d=d=0000，i=i=01

20、01，a=a=1010，n=n=1111怎樣實現(xiàn)怎樣實現(xiàn)HuffmanHuffman編碼？編碼？法法2 2：不等長編碼不等長編碼，例如用哈夫曼編碼來實現(xiàn)。，例如用哈夫曼編碼來實現(xiàn)。 取取 d=d=0 0; i=; i=1010, a=, a=110110, n=, n=111111最快的編碼是哪個？最快的編碼是哪個？是非等長的是非等長的HuffmanHuffman碼！碼！先要構造先要構造HuffmanHuffman樹！樹！21操作要點操作要點1 1：對權值的合并、刪除與替換對權值的合并、刪除與替換在權值集合在權值集合7,5,2,47,5,2,4中，總是合并中，總是合并當前值最小當前值最小的兩個

21、權的兩個權構造構造HuffmanHuffman樹的步驟：樹的步驟：注：方框表示外結(jié)點（葉子，字符對應的權值），注：方框表示外結(jié)點（葉子，字符對應的權值）， 圓框表示內(nèi)結(jié)點（合并后的權值）。圓框表示內(nèi)結(jié)點（合并后的權值）。22操作要點操作要點2 2：按左按左0 0右右1 1對對HuffmanHuffman樹的所有分支編號！樹的所有分支編號！d da ai in n1 11 11 10 00 00 0HuffmanHuffman編碼結(jié)果：編碼結(jié)果：d=d=0 0, i=, i=1010, a=, a=110110, n=, n=111111WPL=1bitWPL=1bit7 72bit2bit5+

22、3bit(2+4)=5+3bit(2+4)=3535特點：每一碼都不是另一碼的前綴，絕不會錯譯特點：每一碼都不是另一碼的前綴，絕不會錯譯! ! 稱為前綴碼稱為前綴碼HuffmanHuffman樹樹 與與 HuffmanHuffman編碼編碼 掛鉤掛鉤23例例2 2（嚴題集（嚴題集6.266.26）：假設用于通信的電文僅由假設用于通信的電文僅由8 8個字母個字母 a, a, b, c, d, e, f, g, hb, c, d, e, f, g, h 構成，它們在電文中出現(xiàn)的概率分別構成，它們在電文中出現(xiàn)的概率分別為為 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.

23、21, 0.10 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10，試為這試為這8 8個字母設計哈夫曼個字母設計哈夫曼編碼。編碼。如果用如果用0 07 7的二進制編碼方案的二進制編碼方案又如何？又如何？霍夫曼霍夫曼編碼的基本思想是：編碼的基本思想是：概率大的字符用短碼，概率小的用概率大的字符用短碼，概率小的用長碼長碼。由于。由于霍夫曼樹的霍夫曼樹的WPLWPL最小，說明編碼所需要的比特數(shù)最最小，說明編碼所需要的比特數(shù)最少。這種編碼已廣泛應用于網(wǎng)絡通信中。少。這種編碼已廣泛應用于網(wǎng)絡通信中。解：解：先將概率放大先將概率放大100100倍，以方便構造哈夫

24、曼樹。倍，以方便構造哈夫曼樹。權值集合權值集合 w=7, 19, 2, 6, 32, 3, 21, 10w=7, 19, 2, 6, 32, 3, 21, 10，按哈夫曼樹構造規(guī)則（合并、刪除、替換），可得到哈夫曼樹。按哈夫曼樹構造規(guī)則（合并、刪除、替換），可得到哈夫曼樹。24w4=19, 21, w4=19, 21, 28,28, 32 32為清晰起見，重新排序為為清晰起見，重新排序為: :w=2, 3, 6, 7, 10, 19, 21, 32w=2, 3, 6, 7, 10, 19, 21, 322 23 35 56 6w1=w1=5,5, 6, 7, 10, 19, 21, 32 6,

25、 7, 10, 19, 21, 32w2=7, 10, w2=7, 10, 11,11, 19, 21, 32 19, 21, 32w3=w3=11, 17,11, 17, 19, 21, 32 19, 21, 32111110107 717172828212119194040w5=w5=28,28,32,32,4040 32326060w6=w6=40,6040,60 w7=w7=100100 100100b bc ca ad de eg gf fh h哈夫曼樹哈夫曼樹25對應的哈夫曼編碼（左對應的哈夫曼編碼（左0右右1）：）：2 23 35 56 6111110107 73232171728282121191940406060100100b bc ca ad de eg gf fh h0 00 00 00 00 01 11 11 11 11 11 11 10 00 0符符編碼編碼頻率頻率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符符編碼編碼頻率頻率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10Huffman碼的碼的WPL2(0.19+0.32+0.21) + 4(0.07+0.06+0.10) +5(0.02+0.03) =1.44+0.92+0.25=2.61 WPL3(0.19+0.