第 七 章 樹狀結構 課程名稱：資料結構 授課老師：________ 2019/1/1.

Presentation on theme: "第 七 章 樹狀結構 課程名稱：資料結構 授課老師：________ 2019/1/1."— Presentation transcript:

1 第 七 章 樹狀結構 課程名稱：資料結構 授課老師：________ 2019/1/1

2 本章學習目標 1.讓讀者了解樹狀結構的相關名詞的定義。 2.讓讀者了解二元樹的建立及各種追蹤方式。 2019/1/1

3 本章內容 7-1 樹狀結構 7-2 樹狀結構表示法 7-3 二元樹(binary tree)
7-4 二元樹的追蹤(Binary Tree Traversal) 7-5 二元搜尋樹(Binary Search Tree) 2019/1/1

4 7-1 樹狀結構 【定義】 樹狀結構是由一個或多個節點組合而成的有限集合，它必須要滿足 以下兩點：
1. Tree不可以為空，至少有一個節點稱為Root(根節點)。 2. 其餘的節點分成T1 , T2,.....,Tn個互斥集合。亦即稱T1 , T2,....., Tn 為根節點的子樹 ( Sub tree ) 。 2019/1/1

5 由於，樹狀結構和我們一般樹的形狀是差不多的，所以才稱為樹狀結構，以下我們就以圖形來做簡單的說明。
2019/1/1

6 注意： 樹狀結構中不可以含有迴圈、重邊或不相連的情況。以下的例子為非樹狀結構。 2019/1/1

7 【樹狀結構的專有術語介紹】 在認識樹狀結構之前，您必須了解相關的專有術語。我們先以圖7-1的樹狀結構來為您說明：
樹根(root)：每一棵樹的最上層的節點，稱為樹根，而A就是為這棵樹 的樹根。 節點(node)：樹的節點代表著某項資料，A、B…、L都是節點。 子樹(subtree)：把A去掉之後，就剩下以B、C及D為樹根的三棵子樹。 樹林(forest)：是由N≧0個互斥子樹的集合。把樹根A去掉之後，剩下 的部分就叫樹林。 階度(level)：表示節點的階層位置。樹根A的階度是1，B的階度是2， K的階度是4。 2019/1/1

8 就是A。 子節點(children)：每一個節點的下一個節點就是子節點，D的子節點
高度(height)：一棵樹中節點的最大階度就是高度， 而此樹的高度為4。 父節點(parent)：每一個節點的上一個節點就是父節點，B節點的父節點 就是A。 子節點(children)：每一個節點的下一個節點就是子節點，D的子節點 就是 H、I及J。 分支度(degree)：一個節點的子樹之個數稱為該節點的分支度。 例如：A的分支度為3，B的分支度是2。 終點節點(terminal node)：分支度為0的節點，這棵樹的終點節點 (又稱樹葉節點)共有K、F、G、H、I、L。 2019/1/1

9 【老師上課動態展示】檔案在附書光碟中。 2019/1/1

10 7-2 樹狀結構表示法 【方法一】直接利用Link List表示 【作法】假設樹有n個節點, 樹的分支度為k，則節點結構如下：
2019/1/1

11 【實例】以下有一棵三個階度的樹狀結構，請利用Linklist來表示。
【解答】 2019/1/1

12 【說明】(1)總共的Link空間為：n×k (2)有用的Link空間為：n-1 ∴浪費的Link數為：n×k-(n-1)
2019/1/1

13 當k=2時，它的鏈結浪費率最低，所以為了改進記空間浪費的缺點，我們將樹化成二元樹(Binary tree)的結構。
【浪費比例】 (1)k=2時2元樹的鏈結浪費率約為1/2 (2)k=3時3元樹的鏈結浪費率約為2/3 (3)k=4時4元樹的鏈結浪費率約為3/4 當k=2時，它的鏈結浪費率最低，所以為了改進記空間浪費的缺點，我們將樹化成二元樹(Binary tree)的結構。 【方法二】將Tree化成Binary Tree後再儲存在下一單元會詳細介紹。 2019/1/1

14 7-3 二元樹(Binary tree) 【定義】二元樹可以為空，若不為空，則： 1.具有根節點(Root)及左子樹和右子樹。
2.左、右子樹亦是二元樹。 簡單的說，二元樹最多只能有兩個子節點，就是分支度小於或等於2。 2019/1/1

15 【二元樹和一般樹的不同之處】 2019/1/1

16 【特性】 １、在二元樹的第 i 階度（Level）上最多的節點個數為 2 i-1 , i >= 1 。 2019/1/1

17 ２、在高度為 h 的二元樹中最多的節點個數為 2 h -1 , h >= 1 。
2019/1/1

18 3. 若一樹 T 的總節點數（Node）為 V，總邊（Edge）數為 E，則 V=E+1
4. 一棵二元樹，若 n0 為樹葉節點的數量，n2 為分支度為 2 的節點 數 量，則n0 = n2 + 1 2019/1/1

19 【n個節點可組成多少不同的二元樹】 2019/1/1

20 7-3.1 斜曲二元樹 ( Skewed binary tree )
【定義】 當一個二元樹完全沒有右節點或左節點時，我們就把它稱為左斜曲樹或右斜曲樹。它可分為二種： 1.左斜曲(Left-skewed)二元樹 2.右斜曲(Right-skewed)二元樹 2019/1/1

21 1.左斜曲(Left-skewed)二元樹 表示二元樹，只有左兒子，無右兒子。如圖7-3所示。 2019/1/1

22 2.右斜曲(Right-skewed)二元樹
表示二元樹，只有右兒子，無左兒子。如圖7-4所示。 2019/1/1

23 7-3.2 嚴格二元樹(Strictly binary tree)
【定義】 若二元樹的每個非終端節點(1,2,4)均有非空的左右子樹。如圖7-5所示。 2019/1/1

24 7-3.3 完滿二元樹 ( Full Binary Tree )
【定義】一個高度為 h 的完滿二元樹 ( Full Binary Tree ) 即是高度為 h 且具 2h -1 個節點，h >= 0 的二元樹。如圖7-6所示。 2019/1/1

25 7-3.4 完整二元樹 ( Complete Binary Tree )
【定義】一個二元樹有 n 個節點且高度為 h ，若且唯若，滿足： 1. 2 h-1 -1 < n < 2 h -1 2. 節點編號與高度h的Full Binary Tree之前n個節點編號一致。 如圖7-7所示。 2019/1/1

26 2019/1/1

27 【基本性質】 2019/1/1

28 7-3.5 二元樹表示法 一般而言，二元樹的表示法有兩種： 1.以陣列(Array)表示
二元樹表示法 一般而言，二元樹的表示法有兩種： 1.以陣列(Array)表示 (1)適合完滿二元樹（ Full Binary Tree ） (2)不適合斜曲樹（ Skew Tree ） (3)容易追蹤 （ Traversal ） 2.以鍵結串列（Linked List）表示 (1)適合處理斜曲樹。 (2)但Link空間約浪費一半。 2019/1/1

29 一.以陣列(Array)表示 要使用一維陣列來儲存二元樹的話，首先將二元樹想像成一個完滿二元樹，並使用一維陣列建立二元樹的表示方法及索引值的配置。 [作法] 假設Binary Tree之高度為h，則準備一維陣列A[1…2h-1]， 依照節點編號依序存入陣列中。 2019/1/1

30 2019/1/1

31 對於Full Binary Tree之儲存完全沒有空間的浪費。 【缺點】 節點之插入與刪除較困難。
【優點】 容易取得左、右子點及父節點。 對於Full Binary Tree之儲存完全沒有空間的浪費。 【缺點】 節點之插入與刪除較困難。 對於斜曲二元樹(Skewed B.T.)的儲存極度浪費空間。 【說明】 假設有一個斜曲二元樹高度為h 其準備2h-1空間 實際有用空間為h 浪費的空間為(2h-1)-h 2019/1/1

32 【老師上課動態展示】檔案在附書光碟中。 2019/1/1

33 二、以鏈結串列(Link List)表示 二元樹鏈結串列表示法是使用動態記憶體配置來建立二元樹，類似結構陣列表示法的節點結構，只是成員變數改成兩個指向左和右子樹的指標。 [作法] Node Structure設計如下： 2019/1/1

34 2019/1/1

35 節點之Insert / Delete 容易。(∵只要更改指標即可) 對於斜曲二元樹儲存較Array節省空間。 【缺點】
【優點】 節點之Insert / Delete 容易。(∵只要更改指標即可) 對於斜曲二元樹儲存較Array節省空間。 【缺點】 不易找到父節點。 Link空間約浪費一半。 【說明】 二元樹有n個Nodes總共Link空間為2n 有用的Links空間為n-1 無用(空)Links空間為2n-(n-1)=n+1 2019/1/1

36 【老師上課動態展示】檔案在附書光碟中。 2019/1/1

37 7-3.6 一般樹化為二元樹 在樹狀結構中，二元樹在處理時，是比較節省記憶體空間的，因此，我們可以將一般樹轉換成二元樹，其方法如下：
步驟一：將樹的各階層兄弟節點利用平行線連接起來。 步驟二：刪掉所有右邊父子節點間的連結，只留最左邊的父子節點。 步驟三：右邊的兄弟節點順時鐘轉45度。 2019/1/1

38 【實例】請將下面的一般樹化為二元樹 2019/1/1

39 2019/1/1

40 7-3.7 森林化為二元樹 一般而言，將森林轉換成二元樹的方法如下： 步驟一：先將各樹的樹根由左至右連接起來。
步驟二：再利用樹(tree)化為二元樹的方法，將其化為二元樹。 2019/1/1

41 【實例】將下面的兩棵森林化為一棵二元樹。
2019/1/1

42 2019/1/1

43 7-4 二元樹的追蹤 (Binary Tree Traversal)
【定義】即追蹤樹中的每一個節點，且每個節點恰好被尋訪一次。 【註】 M(Middle)：中間(指樹根) L(Left)：左邊(指左子樹) R(Right)：右邊(指右子樹) 2019/1/1

44 【尋訪的種類】 中序 In-order（左、中、右） 前序 Pre-order（中、左、右） 後序 Post-order（左、右、中）
2019/1/1

45 中序追蹤 ( Inorder ) 中序追蹤的順序為：左子樹→樹根→右子樹。就是沿樹的左子樹一直往下，直到無法前進，再後退回樹根(即父節點)，再往右子樹一直往下。其中序式追蹤步驟如下： 2019/1/1

46 中序追蹤的遞迴函數如果是Inorder()，指標T是二元樹指標，中序追蹤的遞迴操作步驟如下所示：
Step 1：檢查是否可以繼續前進，即指標T不等於NULL。 Step 2：如果可以前進，其處理方式如下所示： (1) 遞迴呼叫Inorder(T→Lchild)往左走。 (2) 處理目前的節點(Print (T->Data))。 (3) 遞迴呼叫Inorder(T→Rchild)往右走。 2019/1/1

47 【中序追蹤的演算法】 2019/1/1

48 【老師上課動態展示】檔案在附書光碟中。 2019/1/1

49 前序追蹤 ( preorder ) 前序追蹤的順序為：樹根→左子樹→右子樹。前序追蹤就是從根節點開始處理，根節點處理完成之後，再往左子樹走，直到無法前進，再處理右子樹。其前序式追蹤步驟如下： 2019/1/1

50 前序追蹤的遞迴函數是Preorder()，傳入的參數是樹指標T，前序追蹤的遞迴操作可以分為幾個步驟，如下所示：
Step 1：先檢查是否已經到達葉節點，也就是指標T等於NULL。 Step 2：如果不是葉節點表示可以繼續走，此時的處理方式如下所示： (1) 處理目前的節點(Print (T->Data))。 (2) 遞迴呼叫Preorder(T→Lchild)往左走。 (3) 遞迴呼叫Preorder(T→Rchild)往右走。 2019/1/1

51 【前序追蹤的演算法】 2019/1/1

52 【老師上課動態展示】檔案在附書光碟中。 2019/1/1

53 後序追蹤 ( postorder ) 後序追蹤的順序為：左子樹→右子樹→樹根。就是沿樹的左子樹一直往下完成之後，再往右子樹一直往下，直到無法前進，再後退回樹根(即父節點)。其後序式追蹤步驟如下： 2019/1/1

54 後序追蹤的遞迴函數是Postorder()，傳入的參數是樹指標T，此時後序追蹤的遞迴操作可以分為幾個步驟，如下所示：
Step 1： 先檢查是否已經到達葉節點，就是指標T等於NULL。 Step 2： 如果不是葉節點表示可以繼續走，此時的處理方式如下所示： (1) 遞迴呼叫Postorder(T→Lchild)往左走。 (2) 遞迴呼叫Postorder(T→Rchild)往右走。 (3) 處理目前的節點(Print (T->Data))。 2019/1/1

55 【後序追蹤的演算法】 2019/1/1

56 【隨堂練習】 2019/1/1

57 【老師上課動態展示】檔案在附書光碟中。 2019/1/1

58 決定唯一的二元樹 在二元樹的三種追蹤方法中，如果有中序與前序的追蹤結果或者中序與後序的追蹤結果，可由這些結果求得唯一的二元樹。不過如果只具備前序與後序的追蹤結果就無法決定唯一的二元樹。 2019/1/1

59 例如：二元樹的中序追蹤為HBJAFDGCE， 後序追蹤為HJBFGDECA。
2019/1/1

60 2019/1/1

61 【重要題型】 給予{中序與前序}或{中序與後序}之配對可以決定一個唯一(unique)的Binary Tree，但是如果給予{前序與後序}就無法決定(unique)之二元樹。 2019/1/1

62 請繪出此二元樹(Binary Tree)？ 分析：
【實例一】給予前序：ABCDEFGHI 中序：BCAEDGHFI 請繪出此二元樹(Binary Tree)？ 分析： 2019/1/1

63 2019/1/1

64 請繪出此二元樹(Binary Tree)？
【實例二】給予後序：HIDEBFGCA 中序：HDIBEAFCG 請繪出此二元樹(Binary Tree)？ 2019/1/1

65 2019/1/1

66 7-5 二元搜尋樹 (Binary Search Tree)
【定義】 二元搜尋樹是一種二元樹，它可以為空，若不為空，則必須要滿足以下 條件： 1. 若左子樹不為空，則左子樹的鍵值均須要小於樹根的鍵值。 2. 若右子樹不為空，則右子樹的鍵值均須要大於樹根的鍵值。 3. 左子樹與右子樹必須也要保持二元搜尋樹。 2019/1/1

67 2019/1/1

68 【建立二元搜尋樹】 1. 依據原始資料輸入順序來建立 2. 第一個輸入的資料(數)當作樹根 3. 接下來輸入的數從樹根的節點資料開始比較
4. 如果比樹根大，就再和其他右子樹相比（如果沒有右子樹，就將新 輸入的數當作其右子樹） 5. 如果比樹根小，就再和其他左子樹相比（如果沒有左子樹，就將新 輸入的數當作其左子樹） 6. 遞迴執行前二步驟直到位置確定 7. 重複前四步驟直到資料輸入結束 2019/1/1

69 【實例】請依照下列資料來建立二元搜尋樹： 28, 23, 33, 41, 22, 23+
2019/1/1

70 2019/1/1

71 2019/1/1

72 7-5.1 二元搜尋樹插入元素 在建立完成二元搜尋樹之後，接下來如果我們想要再插入一個元素時，也必須要符合二元搜尋樹的條件。假設在下圖中，我們又要插入27元素時，其方法與建立二元搜尋樹時相同步驟。 2019/1/1

73 方法：將27與樹根做比較，結果比28小，所以，再和其他左子樹 相比(27>23)，所以，再往下和其他右子樹相比(27>23+)，
最後，置於右子樹。 2019/1/1

74 7-5.2 二元搜尋樹刪除元素 在建立完成二元搜尋樹之後，並且插入一個元素時，必須要符合二
元搜尋樹的條件，同樣的，刪除一個元素時，也必須要符合二元搜 尋樹規則。假設在下圖中，我們想要刪除28元素時，其方法如下： 1. 如果是刪除樹葉節點時，則直接刪除即可。 2. 如果是刪除非樹葉節點時，則先從其右子樹往下找大於且最接近欲刪除的鍵值來取代它，即可刪除此鍵值。 2019/1/1

75 2019/1/1