Tree（樹） 什麼是「樹」？ 「樹」的範例 「樹」的定義 「樹」的表示法.

Presentation on theme: "Tree（樹） 什麼是「樹」？ 「樹」的範例 「樹」的定義 「樹」的表示法."— Presentation transcript:

1 Tree（樹） 什麼是「樹」？ 「樹」的範例 「樹」的定義 「樹」的表示法

2 什麼是「樹」？

3 「樹」的範例 家族樹（family tree） 賽程樹 目錄樹（directory tree）
組織圖（organization chart） 算式樹（expression tree）

4 家族樹（family tree） 林大樹 林成功 林成福 林成香 林全勝 林全忠 林全進 林全民 林福洋 林福地 林福佳 林福客

5 賽程樹 靜宜 兄弟 靜宜 兄弟 時報 統一 靜宜 兄弟 俊國 三商 時報 興農 統一 台糖 靜宜

6 目錄樹（directory tree） / usr bin sbin etc home local bin X ls tin passwd
rc tsay kmchao course mail

7 組織圖 靜宜董事會 校長 總務處 學務處 教務處 計算中心 人事室 秘書室 保管組 修繕組 採購組 教官室 輔導組 註冊組 體育組

8 算式樹（expression tree） + a b a + b a + b * c (a + b) * c + a * b c + a *

9 算式樹的構建 a + b * c / (d - e) * b c - d e / + a

10 nodes & directed edges node: 資料 edge: 關係 directed edge node

11 「樹」的定義 樹是一種由節點連結而成，且具有下列 兩個性質的圖形（graph） connected circuit-free

12 樹的範例

13 非樹的範例

14 測驗題

15 「有根樹」的定義 有根樹（rooted tree）T 是由一群有限個數的節點（node）和節點之間的有向連線（directed edges）所組成，並滿足下面的遞迴性質： T 中有一個特定節點，此節點稱為根（root）。 其餘的節點可以分割成 n 個不相交的集合 T1, T2, …, Tn，而且每一個集合也都是樹。我們稱 T1, T2, …, Tn 為 T 的子樹。

16 directed edges 如果我們在繪製樹的圖形時，限定有向連線的方向一致朝下 的話，我們可以省去連線的箭頭。

17 關於「樹」的一些術語 節點間的關係 節點的類別 層次和高度 子樹 節點次元（degree） 樹的次元

18 節點間的關係 parent (父母） children (子女） 節點A稱為節點B 的父母節點（或 B是A的子女節點） ，如果A直接連至B。

19 節點間的關係 siblings (兄弟） 節點A和節點B 是兄弟，如果 它們有共同的 父母節點。 A B

20 節點間的關係 ancestor (祖先） descendant (子孫） A B

21 節點的類別 沒有父母的節點 root node (根節點） internal nodes (內部節點） 沒有子女的節點
leave nodes (葉節點）

22 層次和高度 level 1 2 3 4 height = 4

23 子樹（subtrees）

24 節點次元（degree） 節點的子女個數稱之為其次元（degree） 3 2 1

25 樹的次元 樹中所有節點次元的最大值稱為該樹的次元 零元樹 一元樹 二元樹 三元樹

26 二元樹（Binary Tree） 什麼是二元樹？ 左子樹和右子樹 一些特殊的二元樹 二元樹的一些性質 二元樹的表示法 二元樹的遊走

27 什麼是二元樹？ 定義：若樹中每一個節點的子女個數（即次元） 都不超過 2，則該樹為一個二元樹。 範例：下列何者為「二元樹」？

28 左子樹和右子樹 左子樹 右子樹 ? 一個二元樹的左子樹和右子樹必定也是二元樹？

29 一些特殊的二元樹 Full Binary Tree（完整二元樹） Complete Binary Tree（完全二元樹）
Balanced Binary Tree（平衡二元樹） Completely Balanced Binary Tree （完全平衡二元樹）

30 Full Binary Tree（完整二元樹）
定義 1. 若 T 是一個空樹，則 T 是一個高度為 0 的完整二元樹。 2. 若 T 不是一個空樹，且其高度為 h > 0，如果其根節點 之下的左右子樹都是高度為 h -1 的完整二元樹，則 T 是一個完整二元樹 範例：下列何者為完整二元樹？

31 Complete Binary Tree（完全二元樹）
定義 T 是一個高度為 h 的完全二元樹，如果 T 滿足： 1. 所有在 h - 2 層及其上的節點均有兩個子女點。 2. 若一個在 h - 1 層的節點有兩個子女點，則其 左方所有的兄弟節點均有兩個子女點。 3. 若一個在 h - 1 層的節點只有一個子女節點， 則此子女節點必定在左邊，又該節點右方所有 的兄弟節點均無子女點。

32 範例：下列何者為完全二元樹？ ? 一個完整二元樹必定也是完全二元樹？

33 Balanced Binary Tree（平衡二元樹）
定義 如果二元樹 T 中的每一個節點具有性質： 其左右子樹的高度最多相差 1 則 T 稱為「平衡的二元樹」。 定義 如果二元樹 T 中的每一個節點具有性質： 其左右子樹的高度相同 則 T 稱為「完全平衡的二元樹」。

34 範例：下列何者為平衡二元樹？完全平衡二元樹？
? 一個完全平衡二元樹必定也是完整二元樹，反之亦然？

35 二元樹 平衡二元樹 完全二元樹 完整二元樹 = 完全平衡二元樹

36 二元樹的一些性質 1. 二元樹中的第 i（i > 0）層最多有 節點。 證明：（運用數學歸納法） 範例：

37 證明： Base: 當二元樹 T 只有一層時，T 只有 21-1 = 1 個葉節點（即 根節點），所以成立。 Hypothesis:
假定 T 在第 k-1 層有 2k-2 個節點。 Induction: 現在考慮 T 有 i = k 層的情形。已知 T 在第 k -1層最多 有 2k-2 個節點，又這些節點每一個最多只有兩個子女節 點（因為 T 是一個二元樹），所以 k 層最多會有 2  2k-2 = 2k-1。 因此，此定理對所有的 i > 0 都成立。

38 2. 高度為 k（k > 0）的二元樹最多有 節點。
證明：（利用前一個定理）

39 3. 令 T 為一個含有 n 個節點的二元樹，則 T 的高度 h 滿足

40 證明： (i) h  n 假定 h > n，由於每一層最少有一個節點，因此節點數
(ii) log2(n+1)  h 由前面的定理得知 n  2h - 1，因此 n + 1  2h。在不等式 兩邊取對數，我們得到 log2(n+1)  h，又 h 是一個整數， 因此此不等式可寫成 log2(n+1)  h。 故得證。

41 二元樹的表示法 陣列表示法 指標表示法

42 二元樹的陣列表示法 對每一個節點，我們 必須記錄其資料值和 左右子女節點為何。 a d g n s z h f w k data Left
Right d g h

43 步驟一：將節點編號（此編號將用為陣列的 index）
1 2 3 4 5 6 7 8 9 a d g n s z h f w k i 2i+1 2(i+1) (i-1)/2 i/2 -1

44 步驟二：宣告底下的節點結構型態： typedef struct { dataType Data; int Left; int Right;
} treeNode; typedef treeNode arrayType[MAX_NODES]; arrayType Tree; Data Left Right Data: 存放節點的資料值。 Left: 存放節點的左子女節點的編號（若無則存值 -1）。 Right: 存放節點的右子女節點的編號（若無則存值 -1）。

45 範例： Data Left Right a d k g h f w n s z -1 a d g n s z h f w k 1 2 3 4
1 2 3 4 5 6 7 8 9 . Data Left Right a d k g h f w n s z -1 a d g n s z h f w k 1 2 3 4 5 6 7 8 9

46 練習題：寫出代表底下二元樹的陣列。 Data Left Right q r d z e a c t y q r y d a c t z e
1 2 3 4 5 6 7 8 q r y d a c t z e 1 3 5 -1 8 2 4 6 7 1 2 3 4 5 6 7 8 .

47 練習題：繪出以下陣列所表之二元樹。 Data Left Right s a b z w k c u n -1 s a k z c b u n
1 2 3 4 5 6 7 8 . Data Left Right s a b z w k c u n -1 s a k z c b 1 2 5 3 6 u n w 4 7 8

48 二元樹的指標表示法 對每一個節點，我們儲存其資料 值之外，用兩個指標：Left 和 Right 來指到其左右子樹。 a d g n s z
w k Data Left Right 左子樹 右子樹

49 節點結構型態 typedef struct tagTreeNode *nodePtr;
dataType Data; nodePtr Left; nodePtr Right; } treeNode; nodePtr Tree; Data Left Right Data: 存放節點的資料值。 Left: 存放節點的左子女節點的位址（若無則存值 null）。 Right: 存放節點的右子女節點的位址（若無則存值 null）。

50 範例： a d g h f w k d k g h a f w

51 範例：樹的拷貝 d k g h a f w T d k g h a f w S COPY

52 nodePtr CopyTree (nodePtr TreeRoot)
{ nodePtr Node; if (TreeNode == NULL) return NULL; Node = NEW1(treenode); assert(Node != NULL); Node->Data = TreeRoot->Data; Node->Left = CopyTree(TreeRoot->Left); Node->Right = CopyTree(TreeRoot->Right); return Node; }

53 二元樹的遊走 前序遊走（Preorder Traversal） 中序遊走（Inorder Traversal）
後序遊走（Postorder Traversal）

54 前序遊走（Preorder Traversal）
Preorder (Tree T) { if ( T is not empty) { Display the data in the root of T Preorder ( Left subtree of T’s root ) Preorder ( Right subtree of T’s root ) } T 左子樹 右子樹

55 範例： 60 20 10 70 40 30 50 Preorder (Tree T) { if ( T is not empty) { Display the data in the root of T Preorder ( Left subtree of T’s root ) Preorder ( Right subtree of T’s root ) } Preorder; 60, 20, 10, 40, 30, 50, 70

56 中序遊走（Inorder Traversal）
Inorder (Tree T) { if ( T is not empty) { Inorder ( Left subtree of T’s root ) Display the data in the root of T Inorder ( Right subtree of T’s root ) } T 左子樹 右子樹

57 範例： 60 20 10 70 40 30 50 Inorder (Tree T) { if ( T is not empty) { Inorder ( Left subtree of T’s root ) Display the data in the root of T Inorder ( Right subtree of T’s root ) } Inorder; 10, 20, 30, 40, 50, 60, 70

58 後序遊走（Postorder Traversal）
Postorder (Tree T) { if ( T is not empty) { Postorder ( Left subtree of T’s root ) Postorder ( Right subtree of T’s root ) Display the data in the root of T } T 左子樹 右子樹

59 範例： 60 20 10 70 40 30 50 Postorder (Tree T) { if ( T is not empty) { Postorder ( Left subtree of T’s root ) Postorder ( Right subtree of T’s root ) Display the data in the root of T } Postorder; 10, 30, 50, 40, 20, 70, 60

60 Binary Search Tree 定義： 二元搜尋樹（binary search tree）是一個具有 下列性質的二元樹：
每一個節點上的 search key 值 不小於其左子樹所有節點上的 search key 值 不大於其右子樹所有節點上的 search key 值

61 範例： 45 30 52 20 38 27 64 60 77 10 45 30 52 38 64 70 a binary search tree NOT a binary search tree

62 一些 binary search tree 的性質
(I) 中序遊走一個 binary search tree 所產生的 search key 序列是由小至大排列。 (II) 若一個 binary search tree 含有 n 個節點，則其高度 h 滿足不等式：

63 節點宣告 Typedef { keyType Key; /* other fields */ } dataType;
typedef sruct node { dataType Data; struct node *Left; struct node *Right; } nodeType, *nodePtr; Data Left Right

64 Retrieve nodePtr Retrieve (nodePtr TreeRoot, keyType SearchKey) {
if (TreeRoot != NULL) { if (SearchKey < TreeRoot->Data.Key) /* search left subtree */ return Retrieve(TreeRoot->Left, SearchKey); else if (SearchKey > TreeRoot->Data.Key) /* search right subtree */ return Retrieve(TreeRoot->Right, SearchKey); else return TreeRoot; /* found */ } return NULL; /* not found */

65 nonrecursive version nodePtr Retrieve (nodePtr Tree, keyType SearchKey) { nodePtr p = Tree; while (p != NULL) { if (SearchKey < p->Data.Key) p = p->Left; /* search left subtree */ else if (SearchKey > p->Data.Key) p = p->Right; /* search right subtree */ else return p; /* found */ } return NULL; /* not found */

66 45 30 52 20 38 64 Insert insert 10 insert 60 45 30 52 20 38 10 64 45 30 52 20 38 10 60 64

67 #define NEW1(Type) ((Type *) malloc(sizeof(Type)))
Insert (nodePtr Tree, dataType NewItem) { nodePtr *p = &Tree; while (*p != NULL) { if (NewItem.Key < (*p)->Data.Key) p = &((*p)->Left); /* insert to the left subtree */ else p = &((*p)->Right); /* insert to the right subtree */ } /* allocate a new node to store NewItem */ *p = NEW1(nodeType); (*p)->Data = NewItem; (*p)->Left = NULL; (*p)->Right = NULL;

68 練習題 將 1, 2, 3, 4, 5, 6, 7, 8 依序加入一個空的二元搜尋樹， 所得到的二元搜尋樹為何？ 1 2 3 4 5 6 7

69 練習題 將 4, 2, 3, 6, 5, 1, 7, 8 依序加入一個空的二元搜尋樹， 所得到的二元搜尋樹為何？ 4 8 2 1 3 6 5

70 Deletion (I) Delete a leaf node
remove the leaf node from the binary search tree. 範例： 45 30 52 20 38 64 45 30 52 20 64 delete 38

71 (II) Delete a node N with one child C
C replaces N as the child of N’s parent. P N C P N C P N C P N C

72 範例： 45 30 52 20 38 10 60 64 45 30 52 10 38 60 64 delete 20

73 範例： 45 30 52 10 38 60 64 45 30 64 10 38 60 delete 52

74 (III) Delete a node N with two children
replaces N by its inorder successor M and then remove M from the tree. P N M P M P N M P M

75 範例： 45 30 52 20 38 10 60 64 35 45 35 52 20 38 10 60 64 delete 30

76 練習題 45 30 52 20 38 10 60 64 35 52 30 64 20 38 10 60 35 delete 45

77 Traversal(Visit) Inorder (nodePtr TreeRoot, funcPtr Visit) {
if (TreeRoot, != NULL) { Inorder (TreeRoot->Left, Visit); /* visit the left subtree */ Visit(TreeRoot); /* visit the root */ Inorder (TreeRoot->Right, Visit); /* visit the right subtree */ }

78 引線二元樹（Threaded Binary Tree）
當以指標的方式來儲存二元樹時，若節點沒有左子女點（右子女點）時，其左指標（右指標）存放的是空值（如下圖所示）。這種作法似乎並沒有好好利用到這些空值指標。引線二元樹的 目的就是將這些空值指標 改存入其他節點的位址， 以利於中序遊走。 d k g h a f

79 引線二元樹的製作 我們用以下的步驟將二元樹改換成引線二元樹：
（1）若一個節點的左指標為空值的話，則將此 左指標設成此節點的中序前節點（inorder predecessor）的位址。 （2）若一個節點的右指標為空值的話，則將此 右指標設成此節點的中序後節點（inorder successor）的位址。

80 範例： 1 3 2 5 4 6 7 9 8 A H I D E B C F G

81 引線二元樹的節點設計 我們必須區別節點中的引線 link 和普通 link，因此每一個節點多了兩個 flags：
typedef enum {FALSE, TRUE} flag; typedef struct threaded_tree *threaded_pointer; typedef struct threaded_tree { flag LeftThread; threaded_pointer LChild; char Data; threaded_pointer RChild; flag RightThread; }; LeftThread Lchild Data Rchild RightThread

82 範例： head node f: FALSE t: TRUE f f f A f f B f f C f f D f t E t t F t
G t t H t t I t

83 中序遊走引線二元樹 若一個節點的右指標是引線的話，則其中序後節點為引線 所指的節點，否則為其右子樹最左下方的節點。 A B C D E F
6 A 4 8 B C 2 D E F G 5 7 9 H I 1 3

84 threaded_pointer insucc (threaded_pointer Tree)
{ threaded_pointer Temp; Temp = Tree->RChild; if (!Tree->RightThread) while (!Temp->LeftThread) Temp = Temp->LChild; return Temp; } 找尋最左下方的節點

85 void tinorder (threaded_pointer Tree)
{ threaded_pointer Temp = Tree; for (;;) { Temp = insucc(Temp); if (Temp == Tree) break; printf(“%3c”, Temp->Data); } 回到了 head node

86 加入一個新節點至引線二元樹 假定我們要將一個新的節點加為節點 parent 的右子女點。 我們考慮下面兩種情形：

87 （1）parent 沒有右子樹 root root parent A A parent B B child C D C D parent->RightThread = FALSE; child->RightThread = child->LeftThread = TRUE; child->LChild = parent; child->RChild = parent->RChild; parent ->RChild = child;

88 （2）parent 有右子樹 root root parent parent A A B B child C D C X E F D E F child X

89 void insert_right (threaded_pointer Parent, threaded_pointer Child)
{ threaded_pointer Temp; Child->RChild = Parent->RChild; Child->RightThread = Parent->RightThread ; Child->LChild = Parent; Child->LeftThread = TRUE ; Parent->Rchild = Child; Parent->RightThread = FALSE; if (!Child->RightThread) { Temp = insucc(Child); Temp->LChild = Child; }

90 一般樹的表示法 A B C D E F G H I J K L M

91 Left Child-Right Sibling
A B C D E F G H I J K L M

92 Heap 定義：A max tree is a tree in which the value in each node is no smaller than the values in its children (if any). A max heap is a complete binary tree that is also a max tree. 範例：max heap 14 10 8 12 7 6 9 5 3 30 25

93 定義：A min tree is a tree in which the value in each node is no larger than the values in its children (if any). A min heap is a complete binary tree that is also a min tree. 範例：min heap 2 10 8 7 4 6 50 20 83 11 21

94 Heap 陣列表示法 const int MAX_HEAP = 100; /* heap 中可存的最多資料個數 */
typedef struct { unsigned Size; /* heap 中目前所存的資料個數 */ dataType Item[MAX_HEAP]; } heap; #define HEAP_FULL(h) ( (h).Size >= MAX_HEAP) #define HEAP_EMPTY(h) ( (h).Size == 0)

95 20 14 10 15 2 1 3 4 20 15 2 14 10 1 3 4

96 求父母/子女節點的所在（index） 由於 heap 是一個 complete binary tree，我們可以從節點的
index 很容易地推算出它的父母點的 index 和它的子女點的 index。假定此節點的 index 為 i，推算公式如下圖所示： i 2i+1 2(i+1) 左子女點 右子女點 (i-1)/2 i 左子女點 父母點 i 為奇數 父母點 i/2 -1 i 右子女點 i 為偶數

97 我們定義底下的 macro 來求節點 i 的父母點與子女點：
#define PARENT(i) (((i)%2 == 0) ? (i)/2-1 : ((i)-1)/2) #define LCHILD(i) (2*(i)+1) #define RCHILD(i) (2*((i)+1))

98 Priority Queue（優先序佇列）
普通的佇列是一種 FIFO 結構，用於「先進先出」之類 的資料處理上。而 priority queue 並不然，其資料的處 理順序是依照資料的優先等級而定 — 等級高者先處理， 等級低者後處理 — 而不是照著資料「出現」的順序。 譬如： 靜宜大學校車教職員工優先上車 OS process queue 視窗系統的 event queue Priority queue 通常是用 heap 來製作。

99 Insertion Into A Max Heap
新節點加入此 heap，由於 heap 是一個 complete 二元 樹，在加入的動作完成後，新 heap 的結構必須如右 下圖所示： 20 新增的節點 1 2 3 4 5 ? 15 2 14 10 20 15 2 14 10 1 2 3 4

100 Insert 1 底下，我們示範 heap 新增節點後的幾種變化情形： 20 14 10 15 2 20 14 10 15 2 1 20
3 4 5 20 15 2 14 10 1 2 3 4

101 Insert 5 20 14 10 15 2 1 3 4 20 14 10 15 2 5 1 3 4 不是 heap 20 14 10 15 5 2 1 3 4 5 和 2 對調

102 Insert 21 20 14 10 15 2 1 3 4 20 14 10 15 2 21 1 3 4 5 不是 heap 20 14 10 15 21 2 1 3 4 5 不是 heap 21 14 10 15 20 2 1 3 4 5

103 從上面的例子，我們可以歸納出下面加入一個新的節點資料到 max heap 的步驟：
（2）依照下列的規則將此新節點逐漸地移至正確的位置： 若新節點目前的位置不在根節點上，則與其上 的父母節點比較。 （a）如果父母節點的值比較大，則找到了新 節點的正確位置； （b）反之，則將此新節點與父母節點對調， 然後繼續與新的父母點比較對調。

104 例：insert 21 void insert_max_heap (heap *h, dataType Data) { int k, p;
if (HEAP_FULL(*h)) { frpintf(stderr, “The heap is full\n”); exit(-1); } k = (h->Size)++; while ( k > 0 ) { p = PARENT(k); /* parent’s index */ if (Data.Key > h->Item[p].Key) { h->Item[k] = h->Item[p]; k = p; else break; h->Item[k] = Data; 例：insert 21 20 15 2 14 10 k =? p = ? Size = 5 1 3 4 5 20 15 2 14 10 ? k =5 p = ? Size = 6 1 3 4 5 20 15 2 14 10 k =2 p = 2 Size = 6 1 3 4 5 20 15 14 10 2 k =0 p = 0 Size = 6 1 3 4 5 21 15 20 14 10 2 k =0 p = 0 Size = 6 1 3 4 5

105 Insertion 的分析 由於一個高度為 h 的 heap 其節點個數 n 滿足條件 2h-1 -1 < n  2h -1
反過來說，節點個數為 n 的 heap 其高度 h 滿足條件 log(n + 1)  h < log(n + 1) + 1 亦即高度為 O(log n)。 由於上列 insert_max_heap 函式中的 while 迴圈執行 次數等於 heap 的高度，因此函式所花的時間為 O(log n)。

106 Deletion From A Max Heap
也就是說，刪除根節點上的資料。譬如： 14 10 15 2 刪除20 20 14 10 15 2 15 10 14 2 重整 由於刪除資料之後，根節點成為空節點，因此我們必須 重整 heap 的結構。

107 刪除節點後的 Heap 重整： 將最後一個節點 提為新的根節點 (1) 20 14 10 15 2 10 14 15 2 若小於子女
節點，則與 較大的子女 點對調 (2) 14 15 10 2 不是 heap 15 10 14 2 重複步驟(2)於 其下的子樹

108 dataType delete_max_heap (heap *h)
{ int Parent, Child; dataType Data, Temp; if (HEAP_EMPTY(*h)) { frpintf(stderr, “The heap is empty\n”); exit(-1); } Data = h->Item[0]; Temp = h->Item[h->Size]; h->Size--; Parent = 0; Child = 1; while ( Child < h->Size ) { if ( (Child < h->Size-1) && (h->Item[Child].Key < h->Item[Child+1].Key) ) Child++; if (Temp.Key >= h->Item[Child].Key) break; /* 移至下一層 */ h->Item[Parent] = h->Item[Child]; Parent = Child; Child = LCHILD(Child); } h->Item[Parent] = Temp; return Data;

109 若 Heap 是用指標的方式製作，則可用以下的遞迴式作法：
x y 若 x > y，則 將 x 移為 root 然後用同樣的 方式將 x 從左 子樹中刪除 x y x y 若 y > x，則 將 y 移為 root 然後用同樣的 方式將 y 從右 子樹中刪除 x y