樹狀結構 Tree Structure chapter 7 德明科技大學資訊科技系
樹狀結構 陣列與鏈結串列都是有序串列,資料以一個線性的順序串起;但是很多情形下,資料以分支的方式組成 樹狀(tree)結構 一個公司組織架構,總經理下有數個部門,每個部門又分成數個組 各部門是平行沒有管轄關係 樹狀(tree)結構 像樹一樣有許多分支,描述資料之間的關係 德明科技大學資訊科技系
樹狀結構 樹狀結構是由一個或多個節點組合而成的有限集合,它必須要滿足以下兩點: Tree不可以是空集合,至少有一個節點稱為root(根節點) 根節點包含T1 , T2,....., Tn 的子樹 ( subtree ) 德明科技大學資訊科技系
樹狀結構 樹狀結構中不可以含有迴圈、重邊或不相連的情況 以下的例子為非樹狀結構(稱為圖形) 德明科技大學資訊科技系
樹狀結構的專有術語 樹根(root):每一棵樹的最上層的節點,稱為樹根,而A就是為這棵樹的樹根 節點(node):樹的節點代表著某項資料,A、B…、L都是節點 子樹(subtree):把A去掉之後,就剩下以B、C及D為樹根的三棵子樹 樹林(forest):是由N≧0個互斥子樹的集合。把樹根A去掉之後,剩下的部分就叫樹林 階度(level):表示節點的階層位置 樹根A的階度是1 B的階度是2 K的階度是4。 德明科技大學資訊科技系
樹狀結構的專有術語 高度(height):一棵樹中節點的最大階度就是高度, 而此樹的高度為4 父節點(parent):每一個節點的上一個節點就是父節點,例如B節點的父節點就是A 子節點(children):每一個節點的下一個節點就是子節點,D的子節點就是 H、I及J 分支度(degree):一個節點的子樹之個數稱為該節點的分支度,例如: A的分支度為3, B的分支度是2 終點節點(terminal node): 分支度為0的節點, 又稱樹葉節點,共有 K、F、G、H、I、L 德明科技大學資訊科技系
二元樹(Binary tree) 二元樹是一般樹狀結構的特例 定義: 二元樹可以是空集合,若不為空,則: 具有根節點(Root)及左子樹和右子樹。 左、右子樹亦是二元樹。 簡單的說,二元樹最多只能有兩個子節點,就是分支度小於或等於2 德明科技大學資訊科技系
二元樹特性 1. 在二元樹的第 i 階度(Level)上節點個數最多為 2 i-1 , i >= 1 德明科技大學資訊科技系
二元樹特性 2. 在高度為 h 的二元樹中節點個數最多為 2h -1, h >= 1 德明科技大學資訊科技系
二元樹特性 3. 若一樹 T 的總節點數(Node)為 V,總邊(Edge)數為 E,則 V=E+1 4. 一棵二元樹,若 n0 為樹葉節點的數量,n2 為分支度為 2 的節點數 量,則n0 = n2 + 1 德明科技大學資訊科技系
二元樹特性 二元樹的應用與變化都非常多樣 常見的特殊二元樹種類有 斜曲(skew)二元樹 嚴格(strict)二元樹 完滿(full)二元樹 完整(complete)二元樹 德明科技大學資訊科技系
斜曲二元樹 Skew binary tree 當一個二元樹每個節點都 只有左子樹:左斜曲 只有右子樹:右斜曲 德明科技大學資訊科技系
嚴格二元樹 二元樹內每個非樹葉節點都有兩個子結點 也就是二元樹內,每個節點的分支度只有 0(代表樹葉)與 2(代表內部節點)兩種 德明科技大學資訊科技系
完滿二元樹 Full Binary Tree 一個高度為 h 的完滿二元樹即是高度為 h 且具 2h -1 個節點的二元樹 德明科技大學資訊科技系
完整二元樹 一個二元樹有 n 個節點且高度為 h ,若且唯若,滿足: 節點編號與高度h的完滿二元樹之前n個節點編號一致 2 h-1 -1 < n < 2h -1 節點編號與高度h的完滿二元樹之前n個節點編號一致 德明科技大學資訊科技系
完整二元樹 德明科技大學資訊科技系
二元樹表示法 二元樹可以用陣列與鏈結串列表示 以陣列(Array)表示 以鏈結串列(Linked List)表示 適合完滿二元樹 不適合斜曲樹 容易追蹤(Traversal) 以鏈結串列(Linked List)表示 適合處理斜曲樹 但Link空間約浪費一半 德明科技大學資訊科技系
以陣列表示二元樹 將二元樹想像成一個完滿二元樹,並使用一維陣列建立二元樹的表示方法及索引值的配置 德明科技大學資訊科技系
以陣列表示二元樹 假設陣列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] 優點 非常適合完整二元樹的應用 可以計算方式取得節點的左右子節點 不必另外浪費空間紀錄左右子節點 缺點 非完整二元樹時很容易造成空間浪費 德明科技大學資訊科技系
以鏈結串列表示二元樹 使用動態記憶體配置來建立二元樹,類似結構陣列表示法的節點結構,只是成員變數改成兩個指向左和右子樹的指標 德明科技大學資訊科技系
德明科技大學資訊科技系
以鏈結串列表示二元樹 優點 缺點 新增與刪除節點容易 適合一般二元樹的表示 不易找到父節點 必須有一半左有的空間浪費在左右子節點的鏈結上 假設共n個節點,因此會有2n個鏈結 但是只有n-1個節點被鏈結指到 德明科技大學資訊科技系
二元樹的追蹤 Binary Tree Traversal 追蹤樹中的每一個節點,且每個節點恰好被尋訪一次 中序 In-order(左、中、右) 前序 Pre-order(中、左、右) 後序 Post-order(左、右、中) 德明科技大學資訊科技系
中序追蹤 又稱中序走訪 左子樹→樹根→右子樹 沿樹的左子樹一直往下,直到無法前進,再後退回父節點,再往右子樹一直往下 德明科技大學資訊科技系
中序追蹤 中序追蹤的遞迴函數是Inorder(),指標T是二元樹指標,中序追蹤的遞迴操作步驟如下所示: Step 1:檢查是否可以繼續前進, 即指標T不等於NULL。 Step 2:如果可以前進,其處理方式如下所示: (1) 遞迴呼叫Inorder(T→Lchild)往左走 (2) 處理目前的節點(Print (T->Data)) (3) 遞迴呼叫Inorder(T→Rchild)往右走 德明科技大學資訊科技系
德明科技大學資訊科技系
前序追蹤 又稱前序走訪 樹根→左子樹→右子樹 從根節點開始處理,根節點處理完成之後,再往左子樹走,直到無法前進,再處理右子樹 德明科技大學資訊科技系
前序追蹤 前序追蹤的遞迴函數是Preorder(),傳入的參數是樹指標T,前序追蹤的遞迴操作如下所示: Step 1:先檢查是否已經到達葉節點, 也就是指標T等於NULL。 Step 2:如果不是葉節點表示可以繼續走,此時的處理方式如下所示: (1) 處理目前的節點(Print (T->Data))。 (2) 遞迴呼叫Preorder(T→Lchild)往左走。 (3) 遞迴呼叫Preorder(T→Rchild)往右走。 德明科技大學資訊科技系
德明科技大學資訊科技系
後序追蹤 又稱後序走訪 左子樹→右子樹→樹根 沿樹的左子樹一直往下完成之後,再往右子樹一直往下,直到無法前進,再後退回父節點 德明科技大學資訊科技系
後序追蹤 後序追蹤的遞迴函數是Postorder(),傳入的參數是樹指標T,後序追蹤的遞迴操作如下所示: Step 1: 先檢查是否已經到達葉節點, 就是指標T等於NULL。 Step 2: 如果不是葉節點表示可以繼續走,此時的處理方式如下所示: (1) 遞迴呼叫Postorder(T→Lchild)往左走。 (2) 遞迴呼叫Postorder(T→Rchild)往右走。 (3) 處理目前的節點(Print (T->Data))。 德明科技大學資訊科技系
德明科技大學資訊科技系
隨堂練習 德明科技大學資訊科技系
二元搜尋樹 Binary Search Tree 【定義】 二元搜尋樹是一種二元樹,它可以為空,若不為空,則必須要滿足以下條件: 1. 若左子樹不為空,則左子樹的鍵值均須要小於樹根的鍵值。 2. 若右子樹不為空,則右子樹的鍵值均須要大於樹根的鍵值。 3. 左子樹與右子樹必須也要保持二元搜尋樹。 德明科技大學資訊科技系
二元搜尋樹 德明科技大學資訊科技系
二元搜尋樹 二元搜尋樹的運作包含 二元搜尋樹的各種運作方法大致相同,只有刪除節點比較特殊 建立二元搜尋樹 搜尋某一值是否存在 插入節點 插入節點x,就是尋找x應該在樹內哪個位置 建立二元搜尋樹就是每個值都以插入節點方式運作 德明科技大學資訊科技系
建立二元搜尋樹 請依照下列資料來建立二元搜尋樹 28, 23, 33, 41, 22, 23+ 德明科技大學資訊科技系
德明科技大學資訊科技系
德明科技大學資訊科技系
二元搜尋樹插入元素 方法與建立二元搜尋樹時相同步驟 例如在下圖中要插入27元素 將27與樹根做比較,結果比28小,所以再和其他左子樹相比(27>23),所以再往下和其他右子樹相比(27>23+),最後,置於右子樹。 德明科技大學資訊科技系
二元搜尋樹刪除元素 刪除一個元素時,必須結果仍能要符合二元搜尋樹規則 如果是刪除樹葉節點時,則直接刪除即可 如果是刪除非樹葉節點時,則先從其右子樹往下找大於且最接近欲刪除的鍵值來取代它,即可刪除此鍵值 德明科技大學資訊科技系
二元搜尋樹刪除元素 德明科技大學資訊科技系
練習 對於下面的二元搜尋樹,請依照下列動作的順序進行 插入42, 插入48, 插入58, 畫出此時樹的結果 延續(1), 插入35, 刪除21, 畫出此時樹的結果 德明科技大學資訊科技系