鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/ 資料結構 第六章：樹（Tree） 鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/

Presentation on theme: "鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/ 資料結構 第六章：樹（Tree） 鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/"— Presentation transcript:

1 鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/
資料結構 第六章：樹（Tree） 鄧姚文

2 樹的概念 具有層次關係 家族族譜 組織架構 生物演化樹 運算樹 維繫大小關係的樹 具有遠近關係的樹 2019/1/14

3 樹狀結構 A C G B D E F J K L H I M N 高度（或深度）等於 4 的樹 2019/1/14

4 定義 樹（Tree）為節點（Node）組成的有限集合，其中
存在一特殊節點R稱為樹根（Root） 其他節點可分割成n個無交集的集合T1,T2,…,Tn，n0，而T1,T2,…,Tn本身皆為樹，稱為R的子樹（Subtree）。 樹林（Forest）是由 n （n0）個互斥樹（Disjoint Tree）所組成的 一樹移去樹根節點後即形成樹林 2019/1/14

5 專有名詞 節點（Node）：代表資料 邊（Edge）：代表連結（Link），單向
祖先（Ancestor）節點 VS 子孫（Descendant）節點 根節點（Root Node）：為所有節點的祖先 父節點：Father Node或Parent Node，指子樹的上層節點 子節點：Child Node指一節點之子樹的根 兄弟節點（Sibling Node）同父節點的子節點 2019/1/14

6 專有名詞（續） 非終點節點（Non-Terminal Node）有子節點者
終點節點（Terminal Node）：又稱為樹葉節點（Leaf Node），沒有子節點者 分支度（Degree）：一節點的子樹數目 分支度=0者稱為樹葉（Leaf Node）或終端節點（Terminal Node） 分支度>0者稱為Non-terminal Node或Internal Node 定義：一棵樹的分支度等於其所有節點分支度的最大值 2019/1/14

7 專有名詞（續） 階度（Level）：又譯為階層 定義樹根的階度=1，階層 L 的節點其子節點的階度為 L+1 高度（Height）：
節點的高度：此節點至樹葉節點的最長路徑（Path）長度 深度（Depth）： 節點的深度：根節點至此節點的路徑長度 樹的高度與深度相同，定義為該樹節點中所擁有的最大階度 2019/1/14

8 基本性質 若一樹 T 的總節點數（Node）為 V，總邊（Edge）數為 E，則 V=E+1
以數學歸納法證明 Apply Induction on V R T1 T2 Tm … 除了 Root 之外， 每一個 Node 上方都有一個 Edge 2019/1/14

9 樹的表示法 k = Degree of the tree Data Subtree 1 Subtree 2 Subtree k ….
2019/1/14

10 樹的表示法 一般化串列（Generalized List）
T=(R,T1,T2,…,Tn) 例： (A,(B,(E,K),(F,L,M),G),(C,H),(D,(I,N),(J,O,P))) T=(A,T1,T2,T3) T1=(B,(E,K),(F,L,M),G) T2=(C,H) T3=(D,(I,N),(J,O,P)) 此法又稱為『巢狀括弧法』 2019/1/14

11 (A,(B,(E,K),(F,L,M),G),(C,H),(D,(I,N),(J,O,P)))
2019/1/14

12 樹的表示法 左子右兄弟表示法 Left Child, Right Sibling Representation
Left-Most-Child Data Right-Most-Sibling 最左邊的兒子 最右邊的兄弟 優點：不管樹的 Degree 是多少，只需要 2 個指標 2019/1/14

13 左子右兄弟表示法 2019/1/14

14 二元樹（Binary Tree） 分支度為2的樹：二元樹（Binary Tree） 左子右兄弟樹是二元樹 Left Child Data
Right Child 左兒子 右兒子 2019/1/14

15 二元樹（Binary Tree） 定義： 二元樹是一個由節點組成的有限集合，可以是空集合，或是包含了： 一般樹與二元樹的差異：
一個樹根節點 其他節點分割成兩個沒有交集的二元樹，其一為左子樹（Left Subtree），另一為右子樹（Right Subtree） 一般樹與二元樹的差異： 二元樹的節點數可以為零，一般樹至少由一個節點組成 一般樹的子樹沒有順序，而二元樹的子樹有左右之分 二元樹的分支度至多為 2，一般樹則無此限制 任何一樹皆可轉換成二元樹 2019/1/14

16 分辨二元樹 二元樹的子樹有左右之分 A B A B 不同的兩棵二元樹 2019/1/14

17 歪斜樹（Skew Tree） A B C D E 2019/1/14

18 基本性質 一棵二元樹在第 i 階度（Level）上最多有2i-1 個節點，i1 一棵深度為 k 的二元樹，最多有 2k-1 個節點，k1
一棵二元樹，若 n0 為樹葉節點的數量，n2 為分支度為 2 的節點數量，則 n0 = n2 + 1 2019/1/14

19 基本性質 滿枝二元樹（Full Binary Tree）
定義：滿枝二元樹（Full Binary Tree） 一個高度為 k 的二元樹， 且其節點數為 2k-1，k0 2019/1/14

20 基本性質 完備二元樹（Complete Binary Tree）
定義：深度為 k，節點數為 n的二元樹稱為完備二元樹（或譯為完整二元樹），若且為若當 1i<k時，階層 i 有 2i-1 個節點，且第 k 層的節點皆由第 k-1 層的分支由左向右逐一連接而成 2019/1/14

21 基本性質 n 個節點的 Complete Binary Tree 或 Full Binary Tree 其深度為 log2(n+1)
2019/1/14

22 基本性質 正規二元樹（Formal Binary Tree）
若二元樹的所有內部節點恰有2個子節點，則稱之為正規二元樹 2019/1/14

23 二元樹表示法 以陣列表示 以鍵結串列（Linked List）表示 適合 Full Binary Tree
不適合 Skew Tree（歪斜樹） 容易 Traversal 以鍵結串列（Linked List）表示 動態配置 2019/1/14

24 Complete Binary Tree基本性質
若一個具有 n 個節點的 Complete Binary Tree 以循序的方式編號，並依序存放在陣列A中，即第 i 個節點存放在 A[i] 中，1in，則 根節點位於 A[1] 節點 i 的父節點位在 A[i/2]，i1 若 2in，則節點 i 的左兒子位在 A[2i]，若 2i>n，則節點 i 沒有左兒子 若 2i+1n，則節點i的右兒子位在 A[2i+1]，若2i+1>n，則節點 i 沒有右兒子 以歸納法證明 2019/1/14

25 以一維陣列儲存 Binary Tree 以陣列表示 Binary Tree A[i] 的兒子在 A[2i]、A[2i+1]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I 以陣列表示 Binary Tree A[i] 的兒子在 A[2i]、A[2i+1] 適合 Full Binary Tree 不適合 Skew Tree 2019/1/14

26 以鍵結串列（Linked List）表示樹
動態配置 2019/1/14

27 二元樹追蹤（Traversal） Depth-First Traversal 深先追蹤
中序 In-order（左、中、右） 前序 Pre-order（中、左、右） 後序 Post-order（左、右、中） Breadth-First Traversal 廣先追蹤 階層走訪 Level-order Traversal 2019/1/14

28 中序追蹤（In-order Traversal）
void inorder(Node_type *node) { if(node != NULL) inorder(node->llink); printf("%d\n", node->data); inorder(node->rlink); } 2019/1/14

29 前序追蹤（Preorder Traversal）
void preorder(Node_type *node) { if(node != NULL) printf("%d\n", node->data); preorder(node->llink); preorder(node->rlink); } 2019/1/14

30 後序追蹤（Postorder Traversal）
void postorder(Node_type *node) { if(node != NULL) postorder(node->llink); postorder(node->rlink); printf("%d\n", node->data); } 2019/1/14

31 廣先追蹤（Breadth First Traversal）
void bft(Node_type *root) { Node_type *node; if (NULL == root) return; init_queue(); enqueue(root); while (!queue_empty()) { node = dequeue(); printf("%d\t", node->data); if (node->llink != NULL) { enqueue(node->llink); } if (node->rlink != NULL) { enqueue(node->rlink); 2019/1/14

32 Traversal Example Depth First: 中序：A/B%C*D+E 前序：+*/A%BCDE 後序：ABC%/D*E+
Breadth First: +*E/DA%BC 2019/1/14

33 二元搜尋樹（Binary Search Tree）
定義： 二元搜尋樹是一個二元樹，可能是空二元樹，若不為空二元樹則滿足： 每一節點均含有一鍵值（Key），每個鍵值都不一樣 左子樹的所有鍵值均小於樹根的鍵值 右子樹的所有鍵值均大於樹根的鍵值 左子樹和右子樹亦是二元搜尋樹 搜尋、插入、刪除 詳見程式範例 2019/1/14

34 引線二元樹（Threaded Binary Tree）
V=E+1 共有 2V 個指標，其中 2V–E = 2V-(V-1) = V+1 個指標是浪費掉的 Threaded Binary Tree 將原本浪費掉的指標廢物利用，讓 In-Order Traversal 更迅速 Left-Child -> In-Order Predecessor Right-Child -> In-Order Successor 用一個額外的 Bit 判斷指標內容是 Link 還是 Thread 2019/1/14

35 引線二元樹表示法 Lbit=1, Llink 正常指標 Lbit=0, Llink 引線 Rbit=1, Rlink 正常指標
2019/1/14

36 面對現實，引線二元樹真的好嗎？ 在現實的系統環境中，引線二元樹的 RBIT 和 LBIT 都不以 bit 實作，而是以 Integer 實作
引線二元樹為了善用 V+1 個指標，又增加了 2V 的空間實作引線。 優點：引線二元樹做中序追蹤不需要堆疊 缺點：加入節點、刪除節點的程序變得更複雜了 2019/1/14

37 如何將一般樹化為二元樹 一般樹轉為二元樹 樹林轉為二元樹 左子右兄弟法 順時針旋轉45度 每一棵樹各自做左子右兄弟法 把所有樹的樹根節點連結
2019/1/14

38 決定唯一的二元樹 每一棵二元樹皆有唯一的一對 中序＋前序 中序＋後序 前序＋後序無法決定二元樹 2019/1/14

39 TEST 一二元搜尋樹（Binary Search Tree）的Traversal結果如下，請畫出此二元搜尋樹：
中序：20,40,43,45,50,60,70,80 後序：20,43,45,40,60,80,70,50 在此二元搜尋樹中加入一節點key=65後，請畫出此二元搜尋樹。 在此二元搜尋樹中刪除根節點（root），經重整後此二元搜尋樹變成如何？ 將此二元搜尋樹轉換成引線二元樹（Threaded Binary Tree） 在此引線二元樹中，在節點key=70的左方插入一節點key=68，經重整後此引線二元樹變成如何？ 2019/1/14