樹狀結構 Tree Structure chapter 7 德明科技大學資訊科技系.

Presentation on theme: "樹狀結構 Tree Structure chapter 7 德明科技大學資訊科技系."— Presentation transcript:

1 樹狀結構 Tree Structure chapter 7 德明科技大學資訊科技系

2 樹狀結構 陣列與鏈結串列都是有序串列，資料以一個線性的順序串起；但是很多情形下，資料以分支的方式組成 樹狀(tree)結構
一個公司組織架構，總經理下有數個部門，每個部門又分成數個組 各部門是平行沒有管轄關係 樹狀(tree)結構 像樹一樣有許多分支，描述資料之間的關係 德明科技大學資訊科技系

3 樹狀結構 樹狀結構是由一個或多個節點組合而成的有限集合，它必須要滿足以下兩點： Tree不可以是空集合，至少有一個節點稱為root(根節點)
根節點包含T1 , T2,....., Tn 的子樹 ( subtree ) 德明科技大學資訊科技系

4 樹狀結構 樹狀結構中不可以含有迴圈、重邊或不相連的情況 以下的例子為非樹狀結構(稱為圖形) 德明科技大學資訊科技系

5 樹狀結構的專有術語 樹根(root)：每一棵樹的最上層的節點，稱為樹根，而A就是為這棵樹的樹根
節點(node)：樹的節點代表著某項資料，A、B…、L都是節點 子樹(subtree)：把A去掉之後，就剩下以B、C及D為樹根的三棵子樹 樹林(forest)：是由N≧0個互斥子樹的集合。把樹根A去掉之後，剩下的部分就叫樹林 階度(level)：表示節點的階層位置 樹根A的階度是1 B的階度是2 K的階度是4。 德明科技大學資訊科技系

6 樹狀結構的專有術語 高度(height)：一棵樹中節點的最大階度就是高度， 而此樹的高度為4
父節點(parent)：每一個節點的上一個節點就是父節點，例如B節點的父節點就是A 子節點(children)：每一個節點的下一個節點就是子節點，D的子節點就是 H、I及J 分支度(degree)：一個節點的子樹之個數稱為該節點的分支度，例如： A的分支度為3， B的分支度是2 終點節點(terminal node)： 分支度為0的節點， 又稱樹葉節點，共有 K、F、G、H、I、L 德明科技大學資訊科技系

7 二元樹(Binary tree) 二元樹是一般樹狀結構的特例 定義： 二元樹可以是空集合，若不為空，則：
具有根節點(Root)及左子樹和右子樹。 左、右子樹亦是二元樹。 簡單的說，二元樹最多只能有兩個子節點，就是分支度小於或等於2 德明科技大學資訊科技系

8 二元樹特性 1. 在二元樹的第 i 階度（Level）上節點個數最多為 2 i-1 , i >= 1 德明科技大學資訊科技系

9 二元樹特性 2. 在高度為 h 的二元樹中節點個數最多為 2h -1, h >= 1 德明科技大學資訊科技系

10 二元樹特性 3. 若一樹 T 的總節點數(Node)為 V，總邊(Edge)數為 E，則 V=E+1
4. 一棵二元樹，若 n0 為樹葉節點的數量，n2 為分支度為 2 的節點數 量，則n0 = n2 + 1 德明科技大學資訊科技系

11 二元樹特性 二元樹的應用與變化都非常多樣 常見的特殊二元樹種類有 斜曲(skew)二元樹 嚴格(strict)二元樹 完滿(full)二元樹
完整(complete)二元樹 德明科技大學資訊科技系

12 斜曲二元樹 Skew binary tree 當一個二元樹每個節點都 只有左子樹：左斜曲 只有右子樹：右斜曲 德明科技大學資訊科技系

13 嚴格二元樹 二元樹內每個非樹葉節點都有兩個子結點 也就是二元樹內，每個節點的分支度只有 0(代表樹葉)與 2(代表內部節點)兩種
德明科技大學資訊科技系

14 完滿二元樹 Full Binary Tree 一個高度為 h 的完滿二元樹即是高度為 h 且具 2h -1 個節點的二元樹
德明科技大學資訊科技系

15 完整二元樹 一個二元樹有 n 個節點且高度為 h ，若且唯若，滿足： 節點編號與高度h的完滿二元樹之前n個節點編號一致
2 h-1 -1 < n < 2h -1 節點編號與高度h的完滿二元樹之前n個節點編號一致 德明科技大學資訊科技系

16 完整二元樹 德明科技大學資訊科技系

17 二元樹表示法 二元樹可以用陣列與鏈結串列表示 以陣列(Array)表示 以鏈結串列（Linked List）表示 適合完滿二元樹
不適合斜曲樹 容易追蹤(Traversal) 以鏈結串列（Linked List）表示 適合處理斜曲樹 但Link空間約浪費一半 德明科技大學資訊科技系

18 以陣列表示二元樹 將二元樹想像成一個完滿二元樹，並使用一維陣列建立二元樹的表示方法及索引值的配置 德明科技大學資訊科技系

19 以陣列表示二元樹 假設陣列int A[n]; 優點 缺點 A[0]: root，A[1], A[2]: 第一層，以此類推
A[i]的左子節點是A[2*i+1]，左子節點是A[2*i+2] A[i]的父節點是A[i/2] 優點 非常適合完整二元樹的應用 可以計算方式取得節點的左右子節點 不必另外浪費空間紀錄左右子節點 缺點 非完整二元樹時很容易造成空間浪費 德明科技大學資訊科技系

20 以鏈結串列表示二元樹 使用動態記憶體配置來建立二元樹，類似結構陣列表示法的節點結構，只是成員變數改成兩個指向左和右子樹的指標
德明科技大學資訊科技系

21 德明科技大學資訊科技系

22 以鏈結串列表示二元樹 優點 缺點 新增與刪除節點容易 適合一般二元樹的表示 不易找到父節點 必須有一半左有的空間浪費在左右子節點的鏈結上
假設共n個節點，因此會有2n個鏈結 但是只有n-1個節點被鏈結指到 德明科技大學資訊科技系

23 二元樹的追蹤 Binary Tree Traversal 追蹤樹中的每一個節點，且每個節點恰好被尋訪一次
中序 In-order（左、中、右） 前序 Pre-order（中、左、右） 後序 Post-order（左、右、中） 德明科技大學資訊科技系

24 中序追蹤 又稱中序走訪 左子樹→樹根→右子樹 沿樹的左子樹一直往下，直到無法前進，再後退回父節點，再往右子樹一直往下 德明科技大學資訊科技系

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

26 德明科技大學資訊科技系

27 前序追蹤 又稱前序走訪 樹根→左子樹→右子樹 從根節點開始處理，根節點處理完成之後，再往左子樹走，直到無法前進，再處理右子樹
德明科技大學資訊科技系

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

29 德明科技大學資訊科技系

30 後序追蹤 又稱後序走訪 左子樹→右子樹→樹根 沿樹的左子樹一直往下完成之後，再往右子樹一直往下，直到無法前進，再後退回父節點
德明科技大學資訊科技系

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

32 德明科技大學資訊科技系

33 隨堂練習 德明科技大學資訊科技系

34 二元搜尋樹 Binary Search Tree 【定義】 二元搜尋樹是一種二元樹，它可以為空，若不為空，則必須要滿足以下條件：
1. 若左子樹不為空，則左子樹的鍵值均須要小於樹根的鍵值。 2. 若右子樹不為空，則右子樹的鍵值均須要大於樹根的鍵值。 3. 左子樹與右子樹必須也要保持二元搜尋樹。 德明科技大學資訊科技系

35 二元搜尋樹 德明科技大學資訊科技系

36 二元搜尋樹 二元搜尋樹的運作包含 二元搜尋樹的各種運作方法大致相同，只有刪除節點比較特殊 建立二元搜尋樹 搜尋某一值是否存在 插入節點
插入節點x，就是尋找x應該在樹內哪個位置 建立二元搜尋樹就是每個值都以插入節點方式運作 德明科技大學資訊科技系

37 建立二元搜尋樹 請依照下列資料來建立二元搜尋樹 28, 23, 33, 41, 22, 23+ 德明科技大學資訊科技系

38 德明科技大學資訊科技系

39 德明科技大學資訊科技系

40 二元搜尋樹插入元素 方法與建立二元搜尋樹時相同步驟 例如在下圖中要插入27元素
將27與樹根做比較，結果比28小，所以再和其他左子樹相比(27>23)，所以再往下和其他右子樹相比(27>23+)，最後，置於右子樹。 德明科技大學資訊科技系

41 二元搜尋樹刪除元素 刪除一個元素時，必須結果仍能要符合二元搜尋樹規則 如果是刪除樹葉節點時，則直接刪除即可
如果是刪除非樹葉節點時，則先從其右子樹往下找大於且最接近欲刪除的鍵值來取代它，即可刪除此鍵值 德明科技大學資訊科技系

42 二元搜尋樹刪除元素 德明科技大學資訊科技系

43 練習 對於下面的二元搜尋樹，請依照下列動作的順序進行 插入42, 插入48, 插入58, 畫出此時樹的結果
延續(1), 插入35, 刪除21, 畫出此時樹的結果 德明科技大學資訊科技系