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

什麼是「樹」？

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

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

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

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

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

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

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

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

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

樹的範例

非樹的範例

測驗題

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

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

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

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

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

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

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

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

子樹（subtrees）

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

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

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

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

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

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

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

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

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

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

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

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

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

證明： 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 都成立。

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

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

證明： (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。 故得證。

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

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

步驟一：將節點編號（此編號將用為陣列的 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

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

範例： 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

練習題：寫出代表底下二元樹的陣列。 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 .

練習題：繪出以下陣列所表之二元樹。 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

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

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

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

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

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; }

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

前序遊走（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 左子樹 右子樹

範例： 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

中序遊走（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 左子樹 右子樹

範例： 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

後序遊走（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 左子樹 右子樹

範例： 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

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

範例： 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

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

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

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 */

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 */

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

#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;

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

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

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

(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

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

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

(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

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

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

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 */ }

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

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

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

引線二元樹的節點設計 我們必須區別節點中的引線 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

範例： 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

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

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

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

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

（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;

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

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; }

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

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

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

定義：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

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)

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

求父母/子女節點的所在（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 為偶數

我們定義底下的 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))

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

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

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

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 對調

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

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

例：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

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)。

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

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

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;

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