1、第5章 樹和二叉樹（4課時）n樹是一種非常重要的非線性數據結構。樹由n（n0）個數據元素組成，數據元素之間具有明顯的層次結構。圖5-1是樹的樹形圖表示，由于它很像自然界中倒長的樹，因此，被命名為“樹”。樹的樹形圖表示法規定在用直線連接起來的兩端結點中，處在上端的結點是前驅，處在下端的結點是后繼，如A是B的前驅，B是A的后繼。圖5-1中所示樹的邏輯結構可表示為T=(D, R)，其中：數據元素集合D=A, B, C, D, E, F, G, H, I, J, K, L，各數據元素之間的前后件關系R=, , , , , , , , , , 。 n從圖5-1可以很直觀地看出樹具有如下結構特性：只有最頂

2、層的結點沒有前驅，其余結點都有且只有一個前驅；一個結點可以沒有后繼，也可以有一個或多個后繼。nAnBnCnDnEnFnGnHnInJnKnLn第1層n第2層n第3層n第4層圖5-1 樹的樹形圖表示n在客觀世界中，很多事物都可以用樹這種數據結構來表示，如圖5-2所示的學校組織結構圖。在計算機領域，樹也有著非常廣泛的應用，如用樹型結構表示實體之間聯系的層次模型是最早用于商業數據庫管理系統的數據模型；在操作系統中用樹來表示文件目錄結構等。5.1.1 樹的定義樹的定義5.1.3樹的基本術語樹的基本術語5.1.2 樹的表示形式樹的表示形式n樹是由n（n0）個結點組成的有限集T。當n=0時，稱為空樹；當n

3、0時，集合T須滿足如下條件：n有且僅有一個沒有前驅的結點，該結點稱為樹的根結點；n將根節點去除后，其余結點可分為m（m0）個互不相交的子集T1、T2、Tm，其中每個子集Ti（i=1, 2, , m）又是一棵樹，并稱其為根的子樹。n可以看到，樹的定義采用的是遞歸定義方式，即一棵非空的樹由根節點和去除根節點后得到的若干棵規模更小的子樹構成，而每一棵子樹又是由該子樹的根節點和去除該子樹根節點后得到的若干棵更小的子樹構成。例如，圖5-1所示的樹可以看作是由根節點A和3棵子樹T1、T2、T3（結點集合分別為D1=B, E, F, I、D2=C, G和D3=D, H, J, K, L）構成；子樹T1又可以

4、看作是由根節點B和兩棵子樹T11、T12（結點集合分別為D11=E、D12=F, I）構成。 5.1.1 樹的定義樹的定義n樹形圖表示法因其直觀性強而成為樹的最常用的表示形式，圖5-1即是采用樹形圖表示法表示的樹。除樹形圖表示法之外，還有三種常用的表示形式：n1.1.嵌套集合表示法嵌套集合表示法嵌套集合表示法是通過集合包含的形式體現結點之間的關系，后繼結點集合包含在前驅結點集合中。例如，采用嵌套集合表示法可將圖5-1所示的樹表示為圖5-3所示的形式。 nAnBnCnDnEnInFnGnHnJnKnL5.1.2 樹的表示形式樹的表示形式n2.凹入表表示法凹入表表示法凹入表表示法是利用書的目錄形式

5、表示結點之間的關系，后繼結點位于前驅結點的下一層目錄中。例如，采用凹入表表示法可將圖5-1所示的樹表示為圖5-4所示的形式。 n3.廣義表表示法廣義表表示法廣義表表示法是利用廣義表的多層次結構來表示樹，后繼結點位于前驅結點的下一層次。例如，采用廣義表表示法可將圖5-1所示的樹表示為圖5-5所示的形式。nAnBnEnFnInCnGnDnHnJnKnL5.1.2 樹的表示形式樹的表示形式2.結點的層和樹的深度結點的層和樹的深度 樹的根結點所在的層為第1層，其余結點的層等于其前驅結點的層加1；樹中各結點的層的最大值稱為樹的深度。1.度和樹的度度和樹的度 一個結點的后繼的數目稱為該結點的度度；樹中各結

6、點度的最大值稱為樹的度。5.1.3樹的基本術語樹的基本術語3.3.分支、路徑、路徑長度和樹的路徑長度分支、路徑、路徑長度和樹的路徑長度 從一個結點到其后繼結點之間的連線稱為一個分支分支；從一個結點X到另一個結點Y所經歷的所有分支構成結點X到結點Y的路徑；一條路徑上的分支數目稱為路徑長度；從樹的根結點到其他各個結點的路徑長度之和稱為樹的路徑長度。5.1.3樹的基本術語樹的基本術語 5.結點間的關系結點間的關系 在樹中，一個結點的后繼結點稱為該結點的孩子，相應地，一個結點的前驅結點稱為該結點的雙親，即一個結點是其孩子結點的雙親、其雙親結點的孩子。 同一雙親的孩子結點之間互稱為兄弟，不同雙親但在同一

7、層的結點之間互稱為堂兄弟。 從樹的根結點到某一個結點X的路徑上經歷的所有結點（包括根結點但不包括結點X）稱為結點X的祖先，以某一結點X為根的子樹上的所有非根結點（即除結點X外）稱為結點X的子孫。 4.葉子結點、分支結點和內部結點葉子結點、分支結點和內部結點 樹中度為0的結點稱為葉子結點（或終端結點），度不為0的結點稱為分支結點（或非終端結點），除根結點以外的分支結點也稱為內部結點。5.1.3樹的基本術語樹的基本術語6.有序樹和無序樹有序樹和無序樹 對于樹中的任一結點，如果其各棵子樹的相對次序被用來表示數據之間的關系，即交換子樹位置會改變樹所表示的內容，則稱該樹為有序樹；否則稱為無序樹。ABCA

8、CB（a）（b）5.1.3樹的基本術語樹的基本術語7.森林森林 m（m0）棵互不相交的樹的集合就構成了森林。顯然，將一棵樹的根結點刪除就可以得到由根結點的子樹組成的森林；將森林中的樹用一個根結點連起來就可以得到一棵樹。 n二叉樹是一種特殊的樹型結構，在實際應用中有著十分重要的意義。比如，在通信、數據壓縮等領域有著廣泛應用的哈夫曼樹就是采用二叉樹的結構；在數據庫中可以選擇使用二叉樹結構管理數據等。本節主要介紹二叉樹的定義和一些基本性質。 n對二叉樹中的結點可以按照“自上而下、自左至右”的順序進行連續編號（稱為順序編號法），即從根結點開始將其編號為1；除第一層外其余各層第一個結點的編號等于上一層最

9、后一個結點的編號加1。圖5-8所示的就是3棵深度為3、采用順序編號法表示的二叉樹：5.2.1 二叉樹的定義二叉樹的定義1234567（a）123456（b）12345（c）圖5-8 采用順序編號法表示的樹5.2.1 二叉樹的定義二叉樹的定義5.2.2 二叉樹的基本性質二叉樹的基本性質n 1.1.二叉樹二叉樹 與樹一樣，二叉樹的定義也采用遞歸定義方式。二叉樹是由n（n0）個結點組成的有限集T。當n=0時，稱為空二叉樹；當n0時，集合T須滿足如下條件：n 有且僅有一個沒有前驅的結點，該結點稱為二叉樹的根結n 將根節點去除后，其余結點可分為兩個互不相交的子集T1、T2，其中每個子集Ti（i=1, 2

10、）又是一棵二叉樹，并分別稱為根結點的左子樹和右子樹。5.2.1 二叉樹的定義二叉樹的定義n二叉樹共有5種基本形態，如圖5-7所示。5.2.1 二叉樹的定義二叉樹的定義AAAA（a）空二叉樹（b）只有根結點（c）右子樹為空（d）左子樹為空（e）左、右子樹非空圖5-7 二叉樹的基本形態n2.滿二叉樹和完全二叉樹滿二叉樹和完全二叉樹 滿二叉樹是指除了最后一層的結點為葉子結點外其它結點都有左、右兩棵子樹的二叉樹。例如，圖5-8（a）是一棵滿二叉樹；圖5-8（b）中的結點3缺少右子樹，圖5-8（c）中的結點2缺少右子樹、結點3缺少左子樹，因此它們都不是滿二叉樹。 完全二叉樹是指其結點與相同深度的滿二叉樹

11、中的結點編號完全一致的二叉樹。對于深度為k的完全二叉樹，其前k-1層與深度為k的滿二叉樹的前k-1層完全一樣，只是在第k層上有可能缺少右邊若干個結點。顯然，滿二叉樹必然是完全二叉樹，而完全二叉樹不一定是滿二叉樹。例如，圖5-8（a）既是滿二叉樹也是完全二叉樹；圖5-8（b）與圖5-8（a）中的滿二叉樹相比只是在最后一層上缺少右邊的一個結點，因此是一棵完全二叉樹；而圖5-8（c）則不是完全二叉樹。5.2.1 二叉樹的定義二叉樹的定義二叉樹具有以下幾個基本性質。二叉樹具有以下幾個基本性質。n性質1：在二叉樹的第i層上至多有2i-1個結點（i1）。n性質2：深度為k的二叉樹至多有2k-1個結點。n性

12、質3：在二叉樹中，若度為0的結點（即葉子結點）數為n0，度為2的結點數為n2，則n0=n2+1。n性質4：具有n個結點的完全二叉樹其深度為log2n+1（其中log2n表示不大于log2n的最大整數）。n性質5：采用順序編號的完全二叉樹具有如下性質：（1）若一個分支結點的編號為i，則其左子樹的根結點（即左孩子結點）編號為2*i，右子樹的根結點（即右孩子結點）編號為2*i+1；（2）反之，若一個非根結點的編號為i，則其雙親結點的編號為i/2（其中i/2表示不大于i/2的最大整數）。5.2.2 二叉樹的基本性質二叉樹的基本性質 同線性表一樣，二叉樹中的每個結點既可以存儲單值元素，又可以存儲記錄型元

13、素。二叉樹一般需要進行下面的基本操作：n 創建一棵空二叉樹n 刪除一棵二叉樹n 先序遍歷二叉樹n 中序遍歷二叉樹n 后序遍歷二叉樹n 逐層遍歷二叉樹n 判斷二叉樹是否為空n 清空二叉樹n 以指定元素值創建根結點n 將一個結點作為指定結點的左孩子插入n 將一個結點作為指定結點的右孩子插入n 刪除以指定結點為根的子樹n 按關鍵字查找結點n 修改指定結點的元素值n 獲取指定結點的雙親結點n 計算二叉樹的深度n 計算二叉樹的葉子結點數 5.3.1 二叉樹的順序表示及其實現二叉樹的順序表示及其實現5.3.2 二叉樹的鏈式表示及其實現二叉樹的鏈式表示及其實現n2.二叉樹順序表示的實現二叉樹順序表示的實現

14、由于順序表示非完全二叉樹時空間利用率較低，因此，二叉樹的順序表示在實際中應用不多。下面主要圍繞二叉樹的創建和刪除這兩個最基本的操作介紹二叉樹順序表示的實現。n二叉樹順序表示的類模板描述如下： 【描述5-1】二叉樹順序表示的類模板描述。 分析：在類模板中，需設置以下成員變量：一維數組m_pElement用于存儲二叉樹中各結點的值，數組類型由二叉樹結點的值的類型決定；整型變量m_nMaxSize用于存儲二叉樹中的最大結點數；一個bool型一維數組m_pbUsed，用于表示結點狀態，若某個結點不存在（如圖5-9（b）中的結點4和結點5），則m_pbUsed中相應元素的值為false，否則相應元素的值

15、為true。 5.3.1 二叉樹的順序表示及其實現二叉樹的順序表示及其實現n3.二叉樹順序表示代碼復用示例二叉樹順序表示代碼復用示例【例5-1】基于二叉樹順序表示的C+實現代碼，完成如下操作： 創建圖5-9（b）所示的二叉樹，其中每一個結點保存一個字符信息，并通過逐層遍歷輸出各結點的值。 將以結點C為根結點的子樹刪除，并通過逐層遍歷輸出各結點的值。 清空二叉樹中的元素。 分析：對于由簡單數據元素構成的二叉樹，一般可以直接使用C+語言提供的基本數據類型來描述數據元素，本例中可直接使用char類型。5.3.1 二叉樹的順序表示及其實現二叉樹的順序表示及其實現n1.二叉樹的鏈式表示二叉樹的鏈式表示

16、在二叉樹的鏈式表示中，結點之間的關系通過指針來體現。根據一個結點中指針域數量的不同，二叉樹的鏈式表示又可以分為二叉鏈表表示和三叉鏈表表示。圖5-10是一個用二叉鏈表表示法存儲二叉樹的例子。由于二叉樹中每個結點最多有兩個孩子，因此在一個結點中設置兩個指針域leftchild和rightchild分別指向其左孩子和右孩子，數據域data用于存放每個結點中數據元素的值。5.3.2 二叉樹的鏈式表示及其實現二叉樹的鏈式表示及其實現 分析：創建二叉樹的方式有多種，這里采用基于隊列的層次創建方式。其創建步驟如圖5-13所示。 5.3.2 二叉樹的鏈式表示及其實現二叉樹的鏈式表示及其實現n圖5-11是一個用

17、三叉鏈表表示法存儲二叉樹的例子。在三叉鏈表表示中，雙親結點有指向其孩子結點的指針，而孩子結點也包含指向其雙親結點的指針。因此，在用三叉鏈表表示的二叉樹的每個結點中，除了具有二叉鏈表中的兩個指向孩子結點的指針域leftchild和rightchild外，還有一個指向雙親結點的指針域parent。根結點沒有雙親，所以它的parent指針為空（用NULL或0表示）。 5.3.2 二叉樹的鏈式表示及其實現二叉樹的鏈式表示及其實現n2.二叉樹鏈式表示的實現二叉樹鏈式表示的實現 二叉鏈表表示是二叉樹最常用的存儲結構，這里以二叉鏈表為例、圍繞二叉樹的創建介紹二叉樹鏈式表示的實現，其他常用操作的實現在5.4節

18、給出。詳細代碼見講義5.3.2 二叉樹的鏈式表示及其實現二叉樹的鏈式表示及其實現n3.二叉樹鏈式表示代碼復用二叉樹鏈式表示代碼復用示例示例n【例5-2】基于二叉樹二叉鏈表表示的C+實現代碼，創建圖5-12所示的二叉樹，其中每一個結點保存一個字符信息。 5.3.2 二叉樹的鏈式表示及其實現二叉樹的鏈式表示及其實現ABCDEFGHI圖5-12 例5-2創建的二叉樹 在二叉樹的應用中，常常要求在樹中查找具有某種特征的結點或者對樹中全部結點逐一進行各種處理，這時就涉及二叉樹的遍歷問題。5.4.1 二叉樹的遍歷及其實現二叉樹的遍歷及其實現5.4.2二叉樹常用操作的實現二叉樹常用操作的實現1.先序遍歷先序

19、遍歷 先序遍歷，也稱為先根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先訪問其根結點，再訪問根結點的左、右子樹；對于左、右子樹中的結點仍然是按照先序遍歷方式訪問，即先訪問根結點，再訪問根結點的左、右子樹。 提示：在先序遍歷中，只規定了根結點和其子樹的訪問順序，但沒有規定左、右子樹的訪問順序。本書中規定，在先序、中序和后序遍歷時均是先訪問左子樹后訪問右子樹。 例如，對于圖5-12所示的二叉樹，其先序遍歷的結果為：A、B、D、G、C、E、F、H、I。5.4.1 二叉樹的遍歷及其實現二叉樹的遍歷及其實現5.4.1 二叉樹的遍歷及其實現二叉樹的遍歷及其實現操作棧中元素（最左邊為棧底元素，最右邊為棧頂

20、元素）根結點A入棧A棧頂元素A出棧并訪問，將A的右孩子C和左孩子B依次入棧C、B棧頂元素B出棧并訪問，將B的左孩子D入棧C、D棧頂元素D出棧并訪問，將D的右孩子G入棧C、G棧頂元素G出棧并訪問C棧頂元素C出棧并訪問，將C的右孩子F和左孩子E依次入棧F、E棧頂元素E出棧并訪問F棧頂元素F出棧并訪問，將F的右孩子I和左孩子H依次入棧I、H棧頂元素H出棧并訪問I棧頂元素I出棧并訪問棧為空，二叉樹先序遍歷結束表5-1 圖5-12所示二叉樹的非遞歸先序遍歷過程 2.中序遍歷中序遍歷 中序遍歷，也稱為中根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先訪問根結點左子樹，再訪問根結點，最后右子樹；對于左、右

21、子樹中的結點仍然是按照中序遍歷方式訪問。 例如，對于圖5-12所示的二叉樹，其中序遍歷的結果為：D、G、B、A、E、C、H、F、I。5.4.1 二叉樹的遍歷及其實現二叉樹的遍歷及其實現3.后序遍歷后序遍歷 后序遍歷，也稱為后根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先訪問根結點的左子樹，后訪問右子樹，最后訪問根結點；對于左、右子樹中的結點仍然是按照后序遍歷方式訪問。 例如，對于圖5-12所示的二叉樹，其后序遍歷的結果為：G、D、B、E、H、I、F、C、A。5.4.1 二叉樹的遍歷及其實現二叉樹的遍歷及其實現n1.獲取指定結點的雙親結點獲取指定結點的雙親結點在二叉樹的二叉鏈表表示中，結點中

22、沒有指向其雙親結點的指針，要獲取雙親結點則需要從根結點開始遍歷二叉樹直至找到指定結點的雙親結點。因此，可以參照上一小節中給出的二叉樹遍歷算法，編寫獲取雙親結點的程序。n2.刪除以指定結點為根的子樹刪除以指定結點為根的子樹刪除以指定結點為根的子樹，一方面要將子樹從二叉樹中刪除，另一方面要將子樹中的結點釋放。將子樹從二叉樹中刪除是通過將指定結點的雙親結點的指針值置空來實現（若刪除的是整棵二叉樹，則應將根結點指針值置空）。將子樹中的結點釋放，就是采用類似于遍歷子樹中所有結點的方式將各結點占據的內存釋放。5.4.2二叉樹常用操作的實現二叉樹常用操作的實現n3.根據關鍵字查找結點根據關鍵字查找結點 根據

23、關鍵字查找結點，實質上就是按照某種規則依次訪問二叉樹中的每一結點，直至找到與關鍵字匹配的結點。因此，同遍歷算法一樣，根據關鍵字查找結點也可以采用遞歸方式和非遞歸方式。5.4.2二叉樹常用操作的實現二叉樹常用操作的實現n哈夫曼樹，又稱最優二叉樹，是指在一類有著相同葉子結點的樹中具有最短帶權路徑長度的二叉樹。哈夫曼樹在實際中有著廣泛的應用。5.5.1 基本術語基本術語5.5.3 哈夫曼碼及其編解碼方法哈夫曼碼及其編解碼方法5.5.2 哈夫曼樹及其構造方法哈夫曼樹及其構造方法1.結點的權和帶權路徑長度結點的權和帶權路徑長度n在實際應用中，往往給樹中的結點賦予一個具有某種意義的實數，該實數就稱為是結點

24、的權。結點的帶權路徑長度是指從樹根到該結點的路徑長度與結點的權的乘積。 5.5.1 基本術語基本術語2.樹的帶權路徑長度樹的帶權路徑長度n樹的帶權路徑長度是指樹中所有葉子結點的帶權路徑長度之和，記作（其中，n為葉子結點的數目，Wi為第i個葉子結點的權，Li為根結點到第i個葉子結點的路徑長度，可知WiLi為第i個葉子結點的帶權路徑長度）n例如，圖5-14中的2棵二叉樹，其帶權路徑長度分別為：WPL(a) = 2*(9+7+5)+3*(2+3) = 57WPL(b) = 1*3+3*(2+7+5+9) = 725.5.1 基本術語基本術語n在由n個葉子結點構成的一類二叉樹中，具有最短帶權路徑長度的

25、二叉樹稱為哈夫曼樹。其構造方法如下：n 已知n個權值為Wi（i = 1, 2, , n）的結點，將每個結點作為根結點生成n棵只有根結點的二叉樹Ti，形成森林F=T1, T2, , Tn。n從森林F中選出根結點權值最小的兩棵二叉樹Tp和Tq，并通過添加新的根結點將它們合并為一棵新二叉樹，新二叉樹中Tp和Tq分別作為根結點的左子樹和右子樹，且根結點的權值等于Tp和Tq兩棵二叉樹的根結點權值之和。以合并后生成的新二叉樹替代森林F中的原有二叉樹Tp和Tq。重復該步驟直至森林F中只存在一棵二叉樹。 5.5.2 哈夫曼樹及其構造方法哈夫曼樹及其構造方法n圖5-15是哈夫曼樹的構造過程示例。初始有根結點權值

26、分別為2、3、5、7、9的5棵二叉樹組成的森林，如圖5-15（a）所示。從中選取根結點權值最小的兩棵二叉樹進行合并，得到如圖5-15（b）所示的森林重復該合并操作，直至森林中只剩下一棵二叉樹，這棵二叉樹就是哈夫曼樹，如圖5-15（e）所示。 5.5.2 哈夫曼樹及其構造方法哈夫曼樹及其構造方法n哈夫曼碼是利用哈夫曼樹得到的一種不定長的二進制編碼，它在數據壓縮領域有著廣泛應用。利用哈夫曼碼進行數據壓縮的基本原理是：對于出現頻率較高的字符，使用較短的編碼；而對于出現頻率較低的字符，則使用較長的編碼，從而使得用于表示字符序列的編碼總長度最短、節省存儲空間。 5.5.3 哈夫曼碼及其編解碼方法哈夫曼碼

27、及其編解碼方法1.1.哈夫曼編碼哈夫曼編碼 哈夫曼編碼是指將用其他編碼法表示的字符序列轉成用哈夫曼碼表示以減少存儲空間，其具體方法為：以要編碼的字符集C=c1, c2, , cn作為葉子結點、字符出現的頻度或次數W=w1, w2, , wn作為結點的權，構造哈夫曼樹。規定哈夫曼樹中，從根結點開始，雙親結點到左孩子結點的分支標為0，雙親結點到右孩子結點的分支標為1。從根結點到某一葉子結點經過的分支形成的編碼即是該葉子結點所對應字符的哈夫曼碼。 5.5.3 哈夫曼碼及其編解碼方法哈夫曼碼及其編解碼方法n與雙親表示法相反，孩子表示法是通過在雙親結點中設置指向孩子結點的指針域來表示一棵樹。一個結點可以

28、有零個或多個孩子，根據結點中指向孩子結點的指針域數目是否固定可以分為定長孩子表示法和不定長孩子表示法。5.6.2 孩子表示法孩子表示法2.2.哈夫曼解碼哈夫曼解碼 哈夫曼解碼是指將用哈夫曼碼表示的字符序列轉成其他編碼法表示以讓計算機正確顯示字符內容，其具體方法為：將用于表示字符序列的哈夫曼碼逐位取出并送入哈夫曼樹中。從哈夫曼樹的根結點開始，對于每一個結點，遇到位0則經左分支到其左孩子，遇到位1則經右分支到其右孩子。重復該過程直至到達某一個葉子結點，該葉子結點所對應的字符即是解碼結果。解碼一個字符后回到哈夫曼樹的根結點開始解碼下一個字符。 例如，假設要解碼的哈夫曼碼是0100100011，則根據

29、圖5-16（b）的哈夫曼樹可得到解碼結果為FACE。5.5.2 哈夫曼樹及其構造方法哈夫曼樹及其構造方法5.5.3 哈夫曼碼及其編解碼方法哈夫曼碼及其編解碼方法5.6.1 雙親表示法雙親表示法5.6.3 孩子雙親表示法孩子雙親表示法5.6.2 孩子表示法孩子表示法5.6.3 孩子兄弟表示法孩子兄弟表示法n在樹結構中，每個結點可以有零個或多個孩子結點，但至多只有一個雙親結點，因此，通過在孩子結點中設置一個指針域記錄其雙親結點的存儲位置就可以唯一的表示一棵樹。這種表示方法稱為雙親表示法。n雙親表示法通常采用順序存儲方式，從根結點開始編號為0，其他結點按照自上而下、從左至右的順序遞增編號；每個結點除

30、了有一個數據域存儲數據外，還有一個指針域存儲其雙親結點的位置；若一個結點沒有雙親結點，則其指針域賦值為-1。例如，對于圖5-17（a）所示的樹，其雙親表示法如圖5-17（b）所示。 5.6.1 雙親表示法雙親表示法n在雙親表示法中，通過一個結點的指針域可以直接獲取到該結點的雙親結點，但要獲取一個結點的孩子結點，則可能需要遍歷整棵樹。5.6.1 雙親表示法雙親表示法n1.1.定長孩子表示法定長孩子表示法 在定長孩子表示法中，每個結點中的指針域數目是固定的。若樹的度為n，則結點中指針域數目也為n。定長孩子表示法中的節點結構如圖5-18所示。 5.6.2 孩子表示法孩子表示法n2.2.不定長孩子表示

31、法不定長孩子表示法n在不定長孩子表示法中，每個結點中的指針域數目是不固定的。若結點的度為d，則結點中指針域數目也為d。定長孩子表示法中的節點結構如圖5-20所示。 5.6.2 孩子表示法孩子表示法5.7.1 樹、森林轉換為二叉樹樹、森林轉換為二叉樹5.7.2 二叉樹轉換為樹、森林二叉樹轉換為樹、森林n可見，定長孩子表示法需要預先確定樹的度，而且空指針域數量較多從而空間浪費較大，但優點是操作方便，不需人工管理內存；不定長孩子表示法則相對靈活，可以根據結點的度動態分配指針域，沒有空間浪費，但需人工管理內存，初學者操作起來容易出錯。n與雙親表示法相反，在孩子表示法中，通過一個結點的指針域可以直接獲取到該結點的孩子結點，但要獲取一個結點的雙親結點，則可能需要遍歷整棵樹。 5.6.2 孩子表示法孩子表示法5.6.3 孩子雙親表示法孩子雙親表示法 孩子兄弟表示法，又稱為二叉鏈表表示法，與二叉樹的二叉鏈表表示法存儲結構完全相同，只是結點中指針域的含義有所不同。5.6.3 孩子兄弟表示法孩子兄弟表示法n1.樹轉換為二叉樹樹轉換為二叉