第6章樹和二叉樹

1、第6章 樹和二叉樹 第第6章章 樹和二叉樹樹和二叉樹 6.1 樹的定義和基本術語樹的定義和基本術語6.2 二叉樹的定義二叉樹的定義 6.3 二叉樹的遍歷與線索化二叉樹的遍歷與線索化 6.4 樹、森林樹、森林 6.6 赫夫曼樹及其應用赫夫曼樹及其應用 6.7 樹的計數樹的計數第6章 樹和二叉樹 6.1 樹的定義和基本術語樹的定義和基本術語 樹是n（n0）個結點的有限集合T。當n=0時，稱為空樹；當n0時，該集合滿足如下條件： (1) 其中必有一個稱為根（root）的特定結點，它沒有直接前驅，但有零個或多個直接后繼。 (2) 其余n-1個結點可以劃分成m（m0）個互不相交的有限集T1，T2，T3，

2、Tm，其中Ti又是一棵樹，稱為根root的子樹。每棵子樹的根結點有且僅有一個直接前驅，但有零個或多個直接后繼。 第6章 樹和二叉樹 圖6.1 樹的圖示方法EFBAGKLMHIJCD第6章 樹和二叉樹 ADT Tree 數據對象D：一個集合，該集合中的所有元素具有相同的特性。 數據關系R： 若D為空集，則為空樹。若D中僅含有一個數據元素，則R為空集，否則R=H，H是如下的二元關系： (1) 在D中存在唯一的稱為根的數據元素root，它在關系H下沒有前驅。 (2)若D- root ，則存在D- root 的一個劃分D1，D2Dm ( m0 ) 對任意jk ( 1j, km ) 有DjDk=,且對任

3、意的i( 1im ) 唯一存在數據元素 xiH. (3)對應于D- root 的劃分，H- , 有唯一的一個劃分H1，H2，,Hm ( m0 ), 對任意jk ( 1j, km )有HjHk=,且對任意i(1im ) ,H1是Di上的二元關系，(Di, Hi )是一棵符合本定義的樹，成為根root的子樹。 第6章 樹和二叉樹 樹的基本術語 結點：包含一個數據元素及若干指向其它結點的分支信息。 結點的度：一個結點的子樹個數稱為此結點的度。 葉子結點：度為0的結點，即無后繼的結點，也稱為終端結點。 分支結點：度不為0的結點，也稱為非終端結點。 孩子結點：一個結點的直接后繼稱為該結點的孩子結點。在圖

4、6.1中， B、C是A的孩子。 雙親結點：一個結點的直接前驅稱為該結點的雙親結點。在圖6.1中，A 是B、C的雙親。 兄弟結點：同一雙親結點的孩子結點之間互稱兄弟結點。在圖6.1中，結點H、I、 J互為兄弟結點。 第6章 樹和二叉樹 堂兄弟：雙親在同一層的結點互為堂兄弟。 祖先結點：一個結點的祖先結點是指從根結點到該結點的路徑上的所有結點。在圖6.1中，結點K的祖先是A、B、E。 子孫結點：以某結點為根的子樹中的任一結點都稱為該結點的子孫 。在圖6.1中，結點D的子孫是H、I、 J、 M。 結點的層次：從根結點開始定義，根結點的層次為1，根的直接后繼的層次為2，依此類推。 樹的度： 樹中所有結

5、點的度的最大值。 樹的高度（深度）： 樹中所有結點的層次的最大值。 有序樹：在樹T中，如果各子樹Ti之間是有先后次序的，則稱為有序樹。否則稱為無序樹 。 森林：m（m0）棵互不相交的樹的集合。將一棵非空樹的根結點刪去，樹就變成一個森林；反之，給森林增加一個統一的根結點，森林就變成一棵樹。 第6章 樹和二叉樹 6.2 二叉樹的定義二叉樹的定義 6.2.1 二叉樹的定義二叉樹的定義 定義：我們把滿足以下兩個條件的樹形結構叫做二叉樹二叉樹（Binary Tree）： （1） 每個結點至多只有二棵子樹（即度都不大于2）； （2）二叉樹的子樹有左右之分，其次序不能任意顛倒。 由此定義可以看出，一個二叉樹

6、中的每個結點只能含有0、 1或2個孩子，而且每個孩子有左右之分。我們把位于左邊的孩子叫做左孩子，位于右邊的孩子叫做右孩子。 第6章 樹和二叉樹 圖6.2 二叉樹的五種基本形態(tài)。 (a) 空二叉樹(b) 只有根結點 的二叉樹(c) 只有左子樹 的二叉樹(d) 左右子樹均非 空的二叉樹(e) 只有右子樹的二叉樹第6章 樹和二叉樹 與樹的基本操作類似，二叉樹有如下基本操作： (1) InitBiTree（&T）; 操作結果：構造空二叉樹。 (2) DestoryBitree（&T）; 初始條件：二叉樹T存在。 操作結果：銷毀二叉樹T。 (3) GreateBiTree（&T,

7、definition）; 初始條件：definition給出二叉樹T的定義。 操作結果：按definition構造二叉樹T。 (4) ClearBiTree（&T）; 初始條件：二叉樹T存在。 操作結果：將二叉樹T清為空樹。第6章 樹和二叉樹 (5) BiTreeEmpty（T）; 初始條件：二叉樹T存在。 操作結果：若T為空二叉樹，則返回TRUE，否則FLASE。 (6) BiTreeDepth（T）; 初始條件：二叉樹T存在。 操作結果：返回T的深度。 (7) Root（T）； 初始條件：二叉樹T存在。 操作結果：返回T的根。 (8) Value(T,e); 初始條件：二叉樹T存在

8、，e是T中某個結點。 操作結果：返回e的值。第6章 樹和二叉樹 (9) Assign（T，&e,value）; 初始條件：二叉樹T存在，e是T中某個結點。 操作結果：結點e賦值為value。 (10) Parent（T，e）； 初始條件：二叉樹T存在，e是T中某個結點。 操作節(jié)點：返回e的右孩子。若e無左孩子，則返回“空”； (11) LeftChild（T，e）; 初始條件：二叉樹T存在，e是T中某個結點。 操作結果：返回e的左孩子。若e無左孩子，則返回“空”。 (12) RightChild（T，e）; 初始條件：二叉樹T存在，e是T中某個結點。 操作結果：返回e 的右孩子。 第6

9、章 樹和二叉樹 6.2.2 二叉樹的性質二叉樹的性質 性質性質1: 在二叉樹的第i層上至多有2i-1個結點(i1)。 證明：證明： 用數學歸納法。 歸納基礎：當i=1時，整個二叉樹只有一根結點，此時2i-1=20=1，結論成立。 歸納假設：假設i=k時結論成立，即第k層上結點總數最多為2k-1個。 現證明當i=k+1時， 結論成立： 因為二叉樹中每個結點的度最大為2，則第k+1層的結點總數最多為第k層上結點最大數的2倍，即22k-1=2(k+1)-1，故結論成立。 第6章 樹和二叉樹 性質性質2: 深度為k的二叉樹至多有2k-1個結點（k1）。 證明證明：因為深度為k的二叉樹，其結點總數的最大

10、值是將二叉樹每層上結點的最大值相加，所以深度為k的二叉樹的結點總數至多為 kikikii111122層上的最大結點個數第故結論成立。 第6章 樹和二叉樹 性質性質3: 對任意一棵二叉樹T，若終端結點數為n0，而其度數為2的結點數為n2，則n0=n2+1。 證明：設二叉樹中結點總數為n，n1為二叉樹中度為1的結點總數。因為二叉樹中所有結點的度小于等于2，所以有n=n0+n1+n2 設二叉樹中分支數目為B，因為除根結點外，每個結點均對應一個進入它的分支，所以有n=B+1第6章 樹和二叉樹 又因為二叉樹中的分支都是由度為1和度為2的結點發(fā)出， 所以分支數目為B=n1+2n2 整理上述兩式可得到 n=

11、B+1=n1+2n2+1 將n=n0+n1+n2代入上式，得出n0+n1+n2=n1+2n2+1，整理后得n0=n2+1，故結論成立。 第6章 樹和二叉樹 滿二叉樹：滿二叉樹： 深度為k且有2k-1個結點的二叉樹。在滿二叉樹中，每層結點都是滿的，即每層結點都具有最大結點數。圖6.3(a)所示的二叉樹，即為一棵滿二叉樹。 滿二叉樹的順序表示，即從二叉樹的根開始，層間從上到下，層內從左到右，逐層進行編號（1， 2， ， n）。第6章 樹和二叉樹 完全二叉樹：完全二叉樹： 深度為k，結點數為n的二叉樹，如果其結點1n的位置序號分別與滿二叉樹的結點1n的位置序號一一對應，則為完全二叉樹， 如圖6.3(

12、b)所示。 滿二叉樹必為完全二叉樹， 而完全二叉樹不一定是滿二叉樹。 完全二叉樹的特點： 葉子只能在層次最大的兩層上出現； 對任意一個結點，右分支下的子孫的最大層次為L，則左分支為L或L+1 。第6章 樹和二叉樹 圖6.3 滿二叉樹與完全二叉樹 8910111213452136714158910111213452136714(a) 滿二叉樹(b) 完全二叉樹第6章 樹和二叉樹 性質性質4：具有n個結點的完全二叉樹的深度為log2n+1。 證明：假設n個結點的完全二叉樹的深度為k，根據性質2可知，k-1層滿二叉樹的結點總數為n1=2k-1-1 k層滿二叉樹的結點總數為n2=2k-1 顯然有n1n

13、n2，進一步可以推出n1+1nn2+1。 將n1=2k-1-1和n2=2k-1代入上式，可得2k-1n2k，即 k-1log2n1，則序號為i的結點的雙親結點序號為i/2。 （2） 如2in，則序號為i的結點無左孩子；如2in，則序號為i的結點的左孩子結點的序號為2i。 （3）如2i1n，則序號為i的結點無右孩子；如2i1n，則序號為i的結點的右孩子結點的序號為2i1。 第6章 樹和二叉樹 可以用歸納法證明其中的（2）和（3）： 當i=1時，由完全二叉樹的定義知，如果2i=2n，說明二叉樹中存在兩個或兩個以上的結點，所以其左孩子存在且序號為2；反之，如果2n，說明二叉樹中不存在序號為2的結點，

14、其左孩子不存在。同理，如果2i+1=3n，說明其右孩子存在且序號為3；如果3n，則二叉樹中不存在序號為3的結點，其右孩子不存在。 假設對于序號為j(1ji)的結點，當2jn時，其左孩子存在且序號為2j，當2jn 時，其左孩子不存在；當2j+1n時，其右孩子存在且序號為2j+1，當2j+1n時，其右孩子不存在。 第6章 樹和二叉樹 當i=j+1時，根據完全二叉樹的定義，若其左孩子存在， 則其左孩子結點的序號一定等于序號為j的結點的右孩子的序號加1，即其左孩子結點的序號等于（2j+1）+1=2（j+1）=2i，且有2in；如果2in，則左孩子不存在。若右孩子結點存在，則其右孩子結點的序號應等于其左

15、孩子結點的序號加1，即右孩子結點的序號為2i+1，且有2i+1n；如果2i+1n，則右孩子不存在。 故（2）和（3）得證。 第6章 樹和二叉樹 由（2）和（3）我們可以很容易證明（1）。 當i=1時，顯然該結點為根結點，無雙親結點。當i1時，設序號為i的結點的雙親結點的序號為m，如果序號為i的結點是其雙親結點的左孩子，根據（2）有i=2m，即m=i/2; 如果序號為i的結點是其雙親結點的右孩子，根據（3）有i=2m+1，即m=（i-1）/2=i/2-1/2，綜合這兩種情況，可以得到，當i1時，其雙親結點的序號等于i/2。證畢。 第6章 樹和二叉樹 6.2.3 二叉樹的存儲結構二叉樹的存儲結構

16、二叉樹的結構是非線性的， 每一結點最多可有兩個后繼。 二叉樹的存儲結構有兩種： 順序存儲結構和鏈式存儲結構。 順序存儲結構順序存儲結構 用一組地址連續(xù)的存儲單元，依次自上而下、自左至右存用一組地址連續(xù)的存儲單元，依次自上而下、自左至右存儲完全二叉樹上的結點元素，即將完全二叉樹上編號為儲完全二叉樹上的結點元素，即將完全二叉樹上編號為i 的的結點元素存儲在數組的第結點元素存儲在數組的第i 1個分量中。個分量中。 圖6.4 二叉樹與順序存儲結構 第6章 樹和二叉樹 圖6.5 單支二叉樹與其順序存儲結構 ABCD(a) 單支二叉樹ABCD(b) 順序存儲結構第6章 樹和二叉樹 2. 鏈式存儲結構鏈式存

17、儲結構 對于任意的二叉樹來說，每個結點只有兩個孩子，一個雙親結點。我們可以設計每個結點至少包括三個域：數據域、 左孩子域和右孩子： LChildDataRChild其中，LChild域指向該結點的左孩子，Data域記錄該結點的信息，RChild域指向該結點的右孩子。 第6章 樹和二叉樹 用C語言可以這樣聲明二叉樹的二叉鏈表結點的結構： typedef struct BiTNodeTElemType data; struct BiTNode *LChild; struct BiTNode *RChild; BiTNode, *BiTree; 有時，為了便于找到父結點，可以增加一個Parent域，

18、Parent域指向該結點的父結點。該結點結構如下： LChildDataparentRChild第6章 樹和二叉樹 圖6.6 二叉樹和二叉鏈表 BCDGEFADEFCBGA(a) 二叉樹T(b) 二叉樹 T 的二叉鏈表第6章 樹和二叉樹 若一個二叉樹含有n個結點，則它的二叉鏈表中必含有2n個指針域，其中必有n1個空的鏈域。此結論證明如下： 證明：分支數目B=n-1，即非空的鏈域有n-1個，故空鏈域有2n-(n-1)=n+1個。 不同的存儲結構實現二叉樹的操作也不同。如要找某個結點的父結點，在三叉鏈表中很容易實現；在二叉鏈表中則需從根指針出發(fā)一一查找?？梢姡诰唧w應用中，需要根據二叉樹的形態(tài)和需

19、要進行的操作來決定二叉樹的存儲結構。 第6章 樹和二叉樹 6.3 二叉樹的遍歷與線索化二叉樹的遍歷與線索化 6.3.1 二叉樹的遍歷二叉樹的遍歷 圖6.7 二叉樹結點的基本結構 LChildDataRChildLChildRChildData第6章 樹和二叉樹 遍歷二叉樹：按某種搜索路徑，使二叉樹每個結點均被訪問一次，且僅被訪問一次。 訪問的含義很廣。 遍歷需尋找某中規(guī)律，使二叉樹的結點能排列在一個線形隊列上 。 我們用L、D、R分別表示遍歷左子樹、訪問根結點、 遍歷右子樹， 那么對二叉樹的遍歷順序就可以有六種方式： (1) 訪問根，遍歷左子樹，遍歷右子樹（記做DLR）。 (2) 訪問根，遍歷

20、右子樹，遍歷左子樹（記做DRL）。 (3) 遍歷左子樹，訪問根，遍歷右子樹（記做LDR）。 (4) 遍歷左子樹，遍歷右子樹，訪問根（記做LRD）。 (5) 遍歷右子樹，訪問根，遍歷左子樹（記做RDL）。 (6) 遍歷右子樹，遍歷左子樹，訪問根（記做RLD）。 第6章 樹和二叉樹 注意：先序、中序、后序遍歷是遞歸定義的，即在其子樹中亦按上述規(guī)律進行遍歷。 下面就分別介紹三種遍歷方法的遞歸定義。 先序遍歷（DLR）操作過程： 若二叉樹為空，則空操作，否則依次執(zhí)行如下3個操作 (1) 訪問根結點； (2) 按先序遍歷左子樹； (3) 按先序遍歷右子樹。 第6章 樹和二叉樹 中序遍歷（LDR）操作過程

21、： 若二叉樹為空，則空操作，否則依次執(zhí)行如下3個操作： (1) 按中序遍歷左子樹； (2) 訪問根結點； (3) 按中序遍歷右子樹。 后序遍歷（LRD）操作過程： 若二叉樹為空，則空操作，否則依次執(zhí)行如下3個操作： (1) 按后序遍歷左子樹； (2) 按后序遍歷右子樹； (3) 訪問根結點。 第6章 樹和二叉樹 對于如圖6.8所示的二叉樹，其先序、中序、后序遍歷的序列如下： 先序遍歷： A、 B、 D、 F、 G、 C、 E、 H 。 中序遍歷： B、 F、 D、 G、 A、 C、 E、 H 。 后序遍歷： F、 G、 D、 B、 H、 E、 C、 A 。 圖6.8 二叉樹 CEHGFBDA第

22、6章 樹和二叉樹 最早提出遍歷問題是對存儲在計算機中的表達式求值。例如：（a+b*c）-d/e。該表達式用二叉樹表示如圖6.9所示。當我們對此二叉樹進行先序、中序、后序遍歷時，便可獲得表達式的前綴、中綴、后綴書寫形式： 前綴： -+a*bc/de 中綴： a+b*c-d/e 后綴： abc*+de/- 其中中綴形式是算術表達式的通常形式，只是沒有括號。 前綴表達式稱為波蘭表達式。算術表達式的后綴表達式被稱作逆波蘭表達式。 在計算機內，使用后綴表達式易于求值。 第6章 樹和二叉樹 圖6.9 算術式的二叉樹表示 /edcb*a第6章 樹和二叉樹 1） 先序遍歷先序遍歷 Status PreOrde

23、rTraverse ( Bitree T, Status ( * Visit ) ( TelemType e ) )12 if ( T ) 3 4 if ( Visit ( T-data ) )5 if ( PreOrderTraverse ( T-lchild , Visit ) ) 6 if ( PreOrderTraverse ( T-rchild, Visit ) ) return OK;7 return ERROR;8 9 else return OK;10 第6章 樹和二叉樹 2） 中序遍歷中序遍歷 Status InOrderTraverse ( Bitree T, Status

24、 ( * Visit ) ( TelemType e ) )12 if ( T ) 3 4 if ( InOrderTraverse ( T-lchild , Visit ) )5 if ( Visit ( T-data ) )6 if ( InOrderTraverse ( T-rchild, Visit ) ) return OK;7 return ERROR;8 9 else return OK;10 第6章 樹和二叉樹 圖6.10 中序遍歷二叉樹的遞歸過程 ABDCE(a) 二叉樹的遍歷走向BD第一次經過第二次經過第三次經過(b) 遍歷中三次經過結點的情形第6章 樹和二叉樹 基于棧的遞

25、歸消除基于棧的遞歸消除 依棧的狀態(tài)變化，可直接寫出相應的非遞歸算法，棧元素包含兩項，遞歸調用語句編號（返回地址），指向根結點的指針。若棧頂記錄中指針值為空，則應退至上一層，若從左子樹返回，應退到指針所指的根。若是從右子樹返回，表明本層的遍歷結束，應繼續(xù)退棧。 第6章 樹和二叉樹 Status InOrderTraverse( BiTree T, Status ( * Visit ) ( TelemType e ) ) InitStack ( S ); Push ( S, T ); While( !StackEmpty ( S ) ) while ( GetTop ( S, p ) &p

26、) Push ( S, p-lchild ); Pop ( S, p ); if ( !StackEmpty ( S ) ) Pop ( S, p ); if ( !Visit ( p-data ) ) return ERROR; Push ( S, p-rchild ); / if / While return OK;/ InOrderTraverse 第6章 樹和二叉樹 Status InOrderTraverse ( BiTree T, Status ( *Visit ) ( TelemType e ) ) InitStack ( S ); p=T; While ( p | !Stack

27、Empty ( S ) ) if ( p ) Push ( S, p ); p=p-lchild; else Pop ( S, p ); if ( !Visit ( p-data ) ) return ERROR; p=p-rchild; return OK; 第6章 樹和二叉樹 圖6.11 中序遍歷二叉樹的非遞歸算法處理流程 ABDCE(a) 二叉樹的遍歷走向BD第一次經過第二次經過第三次經過(b) 遍歷中三次經過結點的情形第6章 樹和二叉樹 遍歷算法應用遍歷算法應用 1. 輸出二叉樹中的結點輸出二叉樹中的結點 遍歷算法將走遍二叉樹中的每一個結點，故輸出二叉樹中的結點并無次序要求，因此可用三

28、種遍歷中的任何一種算法完成。 下面寫出先序遍歷順序的實現算法。 2. 輸出二叉樹中的葉子結點輸出二叉樹中的葉子結點 輸出二叉樹中的葉子結點與輸出二叉樹中的結點相比，它是一個有條件的輸出問題，即在遍歷過程中走到每一個結點時需進行測試，看是否有滿足葉子結點的條件。第6章 樹和二叉樹 void PreOrder(BiTree root) /* 先序遍歷輸出二叉樹中的葉子結點, root為指向二叉樹根結點的指針 */ if (root! =NULL) if (root -LChild=NULL & root -RChild=NULL) printf (root -data); /* 輸出葉子結

29、點 */ PreOrder(root -LChild); /* 先序遍歷左子樹 */PreOrder(root -RChild); /* 先序遍歷右子樹 */ 第6章 樹和二叉樹 3. 統計葉子結點數目統計葉子結點數目 /* LeafCount是保存葉子結點數目的全局變量, 調用之前初始化值為0 */void leaf(BiTree root) if(root! =NULL) leaf(root-LChild); leaf(root-RChild); if (root -LChild=NULL & root -RChild=NULL) LeafCount+; 第6章 樹和二叉樹 /*

30、采用遞歸算法，如果是空樹，返回0；如果只有一個結點，返回1；否則為左右子樹的葉子結點數之和 */int leaf(BiTree root) int LeafCount; if(root=NULL) LeafCount =0; else if(root-lchild=NULL)&(root-rchild=NULL) LeafCount =1; else LeafCount =leaf(root-lchild)+leaf(root-rchild); /* 葉子數為左右子樹的葉子數目之和 */ return LeafCount; 第6章 樹和二叉樹 4. 建立二叉鏈表方式存儲的二叉樹建立二叉

31、鏈表方式存儲的二叉樹 給定一棵二叉樹，我們可以得到它的遍歷序列；反過來，給定一棵二叉樹的遍歷序列，我們也可以創(chuàng)建相應的二叉鏈表。 這里所說的遍歷序列是一種“擴展的遍歷序列”。在通常的遍歷序列中，均忽略空子樹，而在擴展的遍歷序列中，必須用特定的元素表示空子樹。A B C D E G F 其中用表示空子樹。第6章 樹和二叉樹 Status CreateBiTree( BiTree &T ) scanf ( &ch ); if ( ch = ) T = NULL; else if ( !( T=( BiTNode * ) malloc (sizeof(BiTNode ) ) ) )

32、exit ( OVERFLOW ); T-data=ch; CreateBiTree( T-lchild ); CreateBiTree( T-rchild ); return OK; 第6章 樹和二叉樹 圖圖6.12 二叉樹高度示意圖二叉樹高度示意圖 bt左子樹右子樹hlhrHighmax(hlhr)l5 求二叉樹的高度求二叉樹的高度第6章 樹和二叉樹 設函數表示二叉樹bt的高度，則遞歸定義如下: 若bt為空，則高度為0。 若bt非空，其高度應為其左右子樹高度的最大值加1， 如圖6.12所示。 二叉樹的高度(深度)為二叉樹中結點層次的最大值，即結點的層次自根結點起遞推。設根結點為第1層的結點

33、，所有h層的結點的左右孩子結點在h+1層，則可以通過先序遍歷計算二叉樹中的每個結點的層次，其中最大值即為二叉樹的高度。 第6章 樹和二叉樹 int PostTreeDepth(BiTree bt) /* 后序遍歷求二叉樹的高度遞歸算法 */ int hl, hr, max; if(bt! =NULL) hl=PostTreeDepth(bt-LChild); /* 求左子樹的深度 */ hr=PostTreeDepth(bt-RChild); /* 求右子樹的深度 */ max=hlhr?hl: hr; /* 得到左、 右子樹深度較大者*/ return(max+1); /* 返回樹的深度 *

34、/ else return(0); /* 如果是空樹， 則返回0 */ 第6章 樹和二叉樹 6. 按樹狀打印的二叉樹按樹狀打印的二叉樹 例：例：假設以二叉鏈表存儲的二叉樹中，每個結點所含數據元素均為單字母, 要求實現如圖6.13所示打印結果。 這實際是一個二叉樹的橫向顯示問題：因為二叉樹的橫向顯示應是二叉樹豎向顯示的90旋轉，又由于二叉樹的橫向顯示算法一定是中序遍歷算法，所以把橫向顯示的二叉樹算法改為先右子樹再根結點再左子樹的RDL結構， 實現算法如下： 第6章 樹和二叉樹 ABCDEF輸出CAEFDB圖6.13 樹狀打印的三叉樹示意第6章 樹和二叉樹 void PrintTree(Bitre

35、e root, int nLayer) /* 按豎向樹狀打印的二叉樹 */ if(root= =NULL) return; PrintTree(root-rchild, nLayer+1); for(int i=0; idata); PrintTree(root-lchild, nLayer+1); 第6章 樹和二叉樹 6.3.2 線索二叉樹線索二叉樹 1. 基本概念基本概念 二叉樹的遍歷運算是將二叉樹中結點按一定規(guī)律線性化的過程。當以二叉鏈表作為存儲結構時，只能找到結點的左、右孩子信息，而不能直接得到結點在遍歷序列中的前驅和后繼信息。要得到這些信息可采用以下兩種方法：第一種方法是將二叉樹遍歷

36、一遍，在遍歷過程中便可得到結點的前驅和后繼，但這種動態(tài)訪問浪費時間；第二種方法是充分利用二叉鏈表中的空鏈域，將遍歷過程中結點的前驅、后繼信息保存下來。 第6章 樹和二叉樹 我們知道，在有n個結點的二叉鏈表中共有2n個鏈域，但只有n-1個有用的非空鏈域，其余n+1個鏈域是空的。我們可以利用剩下的n+1個空鏈域來存放遍歷過程中結點的前驅和后繼信息?，F作如下規(guī)定：若結點有左子樹，則其LChild域指向其左孩子，否則LChild域指向其前驅結點；若結點有右子樹，則其RChild域指向其右孩子，否則RChild域指向其后繼結點。為了區(qū)分孩子結點和前驅、后繼結點，為結點結構增設兩個標志域，如下所示： LC

37、hildLtagDataRtagRChild第6章 樹和二叉樹 其中： 在這種存儲結構中，指向前驅和后繼結點的指針叫做線索。 以這種結構組成的二叉鏈表作為二叉樹的存儲結構，叫做線索鏈表。對二叉樹以某種次序進行遍歷并且加上線索的過程叫做線索化。線索化了的二叉樹稱為線索二叉樹。 0 LChild域指示結點的左孩子LChild域指示結點的遍歷前驅0 RChild域指示結點的右孩子1 RChild域指示結點的遍歷后繼 LTag= RTag= 第6章 樹和二叉樹 圖圖6.14 線索二叉樹線索二叉樹 ABCDEFGH(a) 二叉樹ABCDEFGH(b )先序線索二叉樹ACDEFGH(c) 中序線索二叉樹A

38、BCDEFGH(d) 后序線索二叉樹BNULLNULLNULLNULL第6章 樹和二叉樹 3. 在線索二叉樹中找前驅、在線索二叉樹中找前驅、 后繼結點后繼結點 1）對中序線索樹： 找后繼 若 rtag=1 則rchild指示后繼 若 rtag=0 右子樹的最左下結點為后繼 找前驅 若 ltag=1 則lchild指示前驅 若 ltag=0 左子樹最右下結點為前驅 第6章 樹和二叉樹 對后序線索樹找后繼，分3種情況 若結點x是二叉樹的根，則后繼為空； 若x是雙親的右孩子或是雙親的左孩子且雙親沒有右子樹，則后繼為雙親； 若x是雙親的左孩子，且雙親有右子樹，則后繼為雙親右子樹，第一個遍歷的結點。 可

39、見，在后序線索化樹上找后繼時需知道雙親，即需帶標志域的三叉鏈表作為存儲結構。 第6章 樹和二叉樹 在中序線索二叉樹上遍歷二叉樹，雖時間復雜度也為O（n ）但常數因子比前面討論的算法小，且不需要設棧，若經常找前驅、后繼，應采用線索鏈表做為存儲結構。 為方便起見，在二叉鏈表上添加一個頭結點，并令lchild指向二叉樹的根rchild指向最后訪問的結點。同樣，第一個訪問結點的lchild和最后訪問結點的rchild指向頭結點，雙向線索鏈表。 第6章 樹和二叉樹 6.4 樹和森林樹和森林6.4.1 樹的存儲結構樹的存儲結構 樹的主要存儲方法有以下三種： 1. 雙親表示法雙親表示法 這種方法用一組連續(xù)的

40、空間來存儲樹中的結點，在保存每個結點的同時附設一個指示器來指示其雙親結點在表中的位置， 其結點的結構如下： DataParent數據 雙親 第6章 樹和二叉樹 圖6.18 樹的雙親表示法 第6章 樹和二叉樹 雙親表示法的形式說明如下： #define MAX_TREE_SIZE 100typedef struct PTNode TelemType data; int parent;PTNode;typedef struct PTNode nodes MAX_TREE_SIZE ; int r, n;Ptree; PARENT ( T, x ) 常數量時間;反復PARENT操作可找到樹的根，即R

41、OOT（x ）;求解孩子，需遍歷整個鏈表。第6章 樹和二叉樹 2. 孩子表示法孩子表示法 這種方法通常是把每個結點的孩子結點排列起來，構成一個單鏈表，稱為孩子鏈表。n個結點共有n個孩子鏈表（葉子結點的孩子鏈表為空表），而n個結點的數據和n個孩子鏈表的頭指針又組成一個順序表。 這種存儲結構的形式說明如下： typedef struct CTNode int child; struct CTNode *next; *ChildPtr; 第6章 樹和二叉樹 typedef struct TelemType data; ChildPtr firstchild; CTBox; typedef struc

42、t CTBox nodes MAX_TREE_SIZE ; int n, r; Ctree; 第6章 樹和二叉樹 圖6.19 樹的孩子鏈表表示法 第6章 樹和二叉樹 3. 孩子兄弟表示法孩子兄弟表示法圖6.20 樹的孩子兄弟表示法 第6章 樹和二叉樹 孩子兄弟表示法的類型定義如下： 鏈表中結點的兩個鏈域分別指向該結點的第一個孩子結點和下一個兄弟結點，分別命名為firstchild域和nextsibling域 typedef struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling;CSNode, *CSTree;

43、這種存儲結構便于實現樹的各種操作，例如：如果要訪問結點x的第i個孩子，則只要先從FirstChild域找到第一個孩子結點，然后沿著這個孩子結點的Nextsibling域連續(xù)走i-1步，便可找到x的第i個孩子。如果在這種結構中為每個結點增設一個Parent域，則同樣可以方便地實現查找雙親的操作。 第6章 樹和二叉樹 6.4.2 森林與二叉樹的轉換森林與二叉樹的轉換 1. 樹轉換為二叉樹樹轉換為二叉樹 圖6.21 樹 ACBDEFGH第6章 樹和二叉樹 將一棵樹轉換為二叉樹的方法是： (1) 樹中所有相鄰兄弟之間加一條連線。 (2) 對樹中的每個結點，只保留其與第一個孩子結點之間的連線，刪去其與其

44、它孩子結點之間的連線。 (3) 以樹的根結點為軸心，將整棵樹順時針旋轉一定的角度，使之結構層次分明。 可以證明，樹做這樣的轉換所構成的二叉樹是唯一的。 圖6.22給出了將圖6.21所示的樹轉換為二叉樹的轉換過程示意。 第6章 樹和二叉樹 圖6.22 樹到二叉樹的轉換 ABDEFCGHABDEFCGHABDEFCHG第6章 樹和二叉樹 圖6.23 樹與二叉樹的對應 DABCE對應ABCDEABCDEEABCDABCDE存儲存儲解釋解釋第6章 樹和二叉樹 2. 森林轉換為二叉樹森林轉換為二叉樹 森林是若干棵樹的集合。樹可以轉換為二叉樹，森林同樣也可以轉換為二叉樹。因此，森林也可以方便地用孩子兄弟鏈

45、表表示。森林轉換為二叉樹的方法如下： （1）將森林中的每棵樹轉換成相應的二叉樹。 （2）第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子， 當所有二叉樹連在一起后，所得到的二叉樹就是由森林轉換得到的二叉樹。 第6章 樹和二叉樹 圖6.24 森林轉換為二叉樹的過程 ABCDEFGHIJ(a) 森林ABCDEFGHIJ(b) 森林中每棵樹對應的二叉樹ABEFGHIHCD(c) 森林對應的二叉樹第6章 樹和二叉樹 如果F= T1, T2, , Tm 是森林，按以下規(guī)則轉換成一棵二叉樹B= ( root, LB, RB ) （1）若F為空即m=0，則B為空

46、樹 （2）若F非空，則B的根root為森林第一棵樹的根ROOT（T1）B的左子樹LB是從T1中各結點的子樹森林F1= T11，T12，T1m1 轉換成二叉樹，其右子樹RB是從森林F= T2，T3，Tm 轉換成二叉樹。 第6章 樹和二叉樹 3. 二叉樹還原為樹或森林二叉樹還原為樹或森林 樹和森林都可以轉換為二叉樹，二者的不同是：樹轉換成的二叉樹，其根結點必然無右孩子，而森林轉換后的二叉樹，其根結點有右孩子。將一棵二叉樹還原為樹或森林，具體方法如下： （1） 若某結點是其雙親的左孩子，則把該結點的右孩子、 右孩子的右孩子都與該結點的雙親結點用線連起來。 （2） 刪掉原二叉樹中所有雙親結點與右孩子結

47、點的連線。 （3） 整理由（1）、（2）兩步所得到的樹或森林，使之結構層次分明。 第6章 樹和二叉樹 圖6.25 二叉樹到森林的轉換示例 ABECFGHIJD(a) 添加連線ABECFGHIJD(b) 刪除右孩子結點的連線ABCDEFGHIJ(c) 整理第6章 樹和二叉樹 同樣，我們可以用遞歸的方法描述上述轉換過程。 如果B=（ root，LB，RB ）是一棵二叉樹，則可按如下規(guī)則轉換成森林F= T1, T2, , Tm （1）若B為空，則F為空； （2）若B為非空，則F中第一棵樹T1的根ROOT（T1）即為二叉樹B的根root；T1中根結點的子樹森林F1是由B的左子樹LB轉換成的森林F中除T

48、1之外其余樹組成的森林F= T2，T3，Tm 是由B的右子樹RB轉換成的森林。 根據這個遞歸的定義，我們同樣可以寫出遞歸的轉換算法。 第6章 樹和二叉樹 6.4.3 樹的遍歷樹的遍歷 1. 樹的遍歷樹的遍歷 樹的遍歷方法主要有以下兩種： 1） 先根遍歷 若樹非空，則遍歷方法為： (1) 訪問根結點。 (2) 從左到右，依次先根遍歷根結點的每一棵子樹。 例如，圖6.21中樹的先根遍歷序列為ABECFHGD。 第6章 樹和二叉樹 2） 后根遍歷 若樹非空，則遍歷方法為： （1） 從左到右，依次后根遍歷根結點的每一棵子樹。 （2） 訪問根結點。 例如，圖6.21中樹的后根遍歷序列為EBHFGCDA。

49、 2. 森林的遍歷森林的遍歷 森林的遍歷方法主要有以下三種： 1） 先序遍歷 若森林非空，則遍歷方法為： (1) 訪問森林中第一棵樹的根結點。 (2) 先序遍歷第一棵樹的根結點的子樹森林。 (3) 先序遍歷除去第一棵樹之后剩余的樹構成的森林。 例如，圖6.24(a)中森林的先序遍歷序列為ABCDEFGHIJ。 第6章 樹和二叉樹 2） 中序遍歷若森林非空， 則遍歷方法為： (1) 中序遍歷森林中第一棵樹的根結點的子樹森林。 (2) 訪問第一棵樹的根結點。 (3) 中序遍歷除去第一棵樹之后剩余的樹構成的森林。 例如，圖6.24(a)中森林的中序遍歷序列為BCDAFEHJIG。 第6章 樹和二叉樹

50、 6.5 樹與等價問題typedef PTree MFSet;int find_mfset(MFSet S, int i)/找集合找集合S中中i所在子集的根。所在子集的根。if(iS.n) return -1;for(j=i; S.nodesj.parent; j=S.nodesj.parent);return j;算法算法6.8第6章 樹和二叉樹 Status merge_mfset(MFSet &S, int i, int j)if(iS.n |jS.n) return ERROR;S.nodesi.parent=j;return OK;算法算法6.9void mix_mfset(

51、MFSet &S, int i, int j)if(iS.n |jS.n) return ERROR;if(S.nodesi.parentS.nodesj.parent)S.nodesj.parent+=S.nodesi.parent;S.nodesi.parent=j;elseS.nodesi.parent+=S.nodesj.parent;S.nodesj.parent=i; return OK;第6章 樹和二叉樹 int fix_mfset(MFSet &S, int i)if(iS.n) return -1;for(j=i; S.nodesj.parent0; j=S.

52、nodesj.parent);for(k=i; k!=j; k=t)t=S.nodesk.parent;S.nodesk.parent=j;return j;算法算法6.11第6章 樹和二叉樹 6.6 赫夫曼樹及其應用赫夫曼樹及其應用 6.6.1 最優(yōu)二叉樹最優(yōu)二叉樹 1. 路徑和路徑長度路徑和路徑長度 路徑是指從樹中一個結點到另一個結點之間的分支序列， 路徑長度是指從一個結點到另一個結點所經過的分支數目。 樹的路徑長度：從樹根到每一個結點的路徑長度之和。 完全二叉樹是路徑長度最短的二叉樹。 第6章 樹和二叉樹 2. 結點的權和帶權路徑長度結點的權和帶權路徑長度 在實際的應用中，人們常常給樹的

53、每個結點賦予一個具有某種實際意義的實數，我們稱該實數為這個結點的權權。在樹形結構中，我們把從樹根到某一結點的路徑長度與該結點從樹根到某一結點的路徑長度與該結點的權的乘積，叫做該結點的帶權路徑長度的權的乘積，叫做該結點的帶權路徑長度。 第6章 樹和二叉樹 3. 樹的帶權路徑長度樹的帶權路徑長度 樹的帶權路徑長度為樹中所有葉子結點的帶權路徑長度之和樹中所有葉子結點的帶權路徑長度之和，通常記為： iniiWWPL11 其中n為葉子結點的個數，wi為第i個葉子結點的權值，li為第i個葉子結點的路徑長度。 例如， 圖 6.26中三棵二叉樹的帶權路徑長度分別為： WPL(a)=7252224236WPL(

54、b)=4273532146WPL(c)=7152234335 假設假設n個權值個權值 w1, w2, , wn 構造一棵有構造一棵有n個葉子結點的個葉子結點的二叉樹，每個葉子的權值為二叉樹，每個葉子的權值為wi 則則WPL最小的二叉樹，叫做最最小的二叉樹，叫做最優(yōu)二叉樹優(yōu)二叉樹 。第6章 樹和二叉樹 圖6.26 具有不同帶權路徑長度的二叉樹 ABCD7524(a) 帶權路徑長度為36ABCD7524(b) 帶權路徑長度為46ADCB7524(c) 帶權路徑長度為35第6章 樹和二叉樹 問題1: 什么樣的二叉樹的路徑長度PL最??？ 一棵樹的路徑長度為0，結點至多只有1個（根）； 路徑長度為1，結

55、點至多只有2個（兩個孩子）； 路徑長度為2，結點至多只有4個； 依此類推，路徑長度為k，結點至多只有2k個, 所以n個結點二叉樹其路徑長度至少等于如圖6.27所示序列的前n項之和。 圖圖6.27 結點序列及結點的路徑長度結點序列及結點的路徑長度 結點路徑長度0，1， 1， 2，2，2，2， 3， 3， 3， 3， 3， 3， 3， 3， 4，4，結點數n n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=15 第6章 樹和二叉樹 由圖6.27可知，結點n對應的路徑長度為log2n，所以前n項之和為 。完全二叉樹的路徑長度 (h為樹的深度)，所以完全二叉樹具有最小路徑長度的性質

56、，但不具有唯一性。有些樹并不是完全二叉樹，但也可以具有最小路徑長度，如圖6.28所示。 nkk12loghkhkh12210log2221202 圖6.28 具有相同最小路徑長度的不同形態(tài)的二叉樹 ABCDE(a) PL 0 1 1 2 2 6BCDEA(b) PL 0 1 1 2 2 6第6章 樹和二叉樹 問題問題2: 什么樣的樹的帶權路徑長度最?。?例如：給定一個權值序列2, 3, 4, 7，可構造如圖6.29所示的多種二叉樹的形態(tài)。 圖圖6.29 具有不同帶權路徑長度的二叉樹具有不同帶權路徑長度的二叉樹 234723477432(a) W PL 22 23 24 27 32(b) W P

57、L 12 23 34 37 41(c) W PL 17 24 33 32 7 8 9 6 30第6章 樹和二叉樹 4. 赫赫夫曼樹夫曼樹 構造赫夫曼算法的步驟如下： （1） 用給定的n個權值w1, w2, , wn對應的n個結點構成n棵二叉樹的森林F=T1, T2, , Tn，其中每一棵二叉樹Ti(1in)都只有一個權值為wi的根結點，其左、右子樹為空。 （2） 在森林F中選擇兩棵根結點權值最小的二叉樹，作為一棵新二叉樹的左、右子樹，標記新二叉樹的根結點權值為其左右子樹的根結點權值之和。 第6章 樹和二叉樹 （3） 從F中刪除被選中的那兩棵二叉樹，同時把新構成的二叉樹加入到森林F中。 （4）

58、重復（2）、（3）操作， 直到森林中只含有一棵二叉樹為止，此時得到的這棵二叉樹就是赫夫曼樹。 第6章 樹和二叉樹 6.6.2 赫赫夫曼編碼夫曼編碼 電報需將傳送的文字轉換成由二進制的字符組成的字符串，如ABACCDA設A、B、C、D編碼分別為00、01、10、11則0001001010110014位，對方接收時將其譯碼。在傳送電文時，希望總長度盡可能的短，如A、B、C、D分別編碼為0、00、1和01，則上述7個字符轉換成總長為9位000011010，但是這樣的電文無法譯碼。0000可有多種譯法AAAA或ABA、BB，設計時用前綴編碼。 前綴編碼：任一個字符的編碼都不是另一個字符編碼的前綴，可利

59、用二叉樹設計前綴編碼。 第6章 樹和二叉樹 設計電文總長最短的前綴編碼，設每種字符在電文中出現的次數為wi編碼長度為Li，有n種字符，電文總長wiLi ( i=1n) 對應二叉樹上，若置wi為葉子結點的權，恰為WPL,即設計赫夫曼樹，得到的前綴編碼為赫夫曼編碼，赫夫曼樹中沒有度為1的結點（嚴格的（正則的）二叉樹），一棵有n個葉子結點的赫夫曼樹共有2n-1個結點，可以存儲在2n-1的一維數組中，另外需知道雙親。 第6章 樹和二叉樹 表 6 1 指令的使用頻率 指令使用頻率(Pi）I10.40I20.30I30.15I40.05I50.04I60.03I70.03第6章 樹和二叉樹 表表 6 2

60、指令的變長編碼指令的變長編碼 指令使用頻率(Pi）I10I21I300I401I5000I6001I7010第6章 樹和二叉樹 圖6.30 構造赫夫曼樹示例 1.000.030.030.060.050.040.090.150.150.300.300.600.40I7I6I5I4I3I2I1第6章 樹和二叉樹 表表 6 3 指令的赫夫曼編碼指令的赫夫曼編碼 指令使用頻率(Pi）I10I210I3110I411100I511101I611110I711111第6章 樹和二叉樹 可以驗證，該編碼是前綴編碼。若一段程序有1000條指令， 其中I1大約有400條，I2大約有300條，I3大約有150條，I4大約有50條，I5大約有40條，I6大約有30條，I7大約有30條。對于定長編碼，該段程序的總位數大約為3100