Chapter 5 樹(Trees)

Hsin-Chang Yang@NUKIM 5.1 簡介 (a) 血統表 (b) 族系表 Dusty Honey Bear Brandy Brunhilde Terry Coyote Nugget Gill Tansey Tweed Zoe Crocus Primrose Nous Belle 5.1.1專有名詞 Germanic Osco-Umbrian Latin North West Oscan Umbrian French Italian Icelandic Swedish Low Yiddish Proto Indo-European Italic Hellenic High Spanish Norwegian Greek Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.1 簡介 定義：樹(tree)是一個或多個節點的有限集合，它滿足： 有一個特定的節點稱為根節點(root)。 其餘的節點分成n ≥ 0 個獨立的集合T1, …, Tn，其中的各個集合也是一個樹。我們稱T1, …, Tn為根節點的子樹(subtree)。 在描繪樹之結構時，通常將樹的根節點畫在最上面。 一個節點的分支度(degree)為此節點的子樹個數。 樹的分支度為在此樹中最大的節點分支度。 分支度為零的節點稱為葉節點(leaf)或終端 (terminal)節點。 具有子樹的節點，為其子樹的根之父節點(parent)，而子樹的根為此節點的子節點(children)。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.1 簡介 具有同一個父節點的節點稱為兄弟(siblings)。 一個節點的祖先(ancestors)為從根節點到此節點路徑上之所有節點。 一個節點的後代(descendants)為在他的子樹之所有節點。 我們以根節點位在階層1（有些書將其設為階層0）來定義一個節點的階層。對於其下的所有節點，其階層為父節點的階層加1。 一個樹的高度(height)或深度(depth)為此樹中任一個節點最大的階層數。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.1 簡介 圖5.2：一範例樹 Level A 1 B C D 2 3 E F G H I J 4 K L M Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.1 簡介 5.1.2 樹狀結構表示法 5.1.2.1 串列表示法 圖5.2中的樹可寫成一個串列，其中的每一子樹也是一個串列。 (A(B(E(K, L), F), C(G), D(H(M), I, J))) 圖5.3：圖5.2之串列表示法 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.1 簡介 考慮在記憶體中的樹狀結構表示法。如果要以鏈結串列表示，則一個節點會有不同的欄位個數，視其分支的個數而定。 圖5.4：樹狀結構可能的鏈結表示法 輔助定理5.1：若T為具有n個節點之k-度樹（即T之分支度為k）且每一節點為固定大小如圖5.4，則所有nk子欄位中之n(k1)+1欄位之值為0。 DATA CHILD 1 CHILD 2 … CHILD k Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.1 簡介 5.1.2.2 左子－右弟(left child-right sibling)表示法 圖5.5：左子－右弟節點結構 每一個節點剛好需要兩個鏈結(或指標)欄位。 每一個節點只有一個最左(leftmost)子節點，以及一個近右(closest right)兄弟節點。 data left child right sibling Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.1 簡介 圖5.6：圖5.2之左子－右弟表示法 A B C D E F G H I J M K L Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.1 簡介 5.1.2.3 分支度二(degree-two)表示法 要得到分支度二表示法，我們只需將左子－右弟樹之右弟指標順時針方向轉45度即可。 在此表示法中，我們稱一節點之兩子節點為左子節點(left children)與右子節點(right children)。 根節點之右子節點必為空。 分支度二樹又稱為左子－右子樹，亦稱為二元樹(binary tree)。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.1 簡介 圖5.7：圖5.2分支度二表示法 A B E C K F G D L H M I J Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.1 簡介 圖5.8：樹的表示法 樹　　 左子－右弟樹　　　　二元樹 　　 樹　　　左子－右弟樹　　　　二元樹 A A A B B B A A A B B C B C C Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.2 二元樹 5.2.1 抽象資料型態 定義：二元樹(binary tree)是節點的有限集合，它可能是空的，或者包含一個根節點及兩個獨立的二元樹，分別稱為左子樹(left subtree)跟右子樹(right subtree)。 沒有樹可以是0個節點的，但可以有空的二元樹。 在二元樹中我們要區別子樹的順序，而樹則不必。 圖5.9中的兩個樹是不同的，因為第一個樹的右子樹是空的，而第二個樹的左子樹是空的。 圖5.9：兩個不同的二元樹 A B A B Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.2 二元樹 圖5.9若視為一般的樹，則兩個樹是相同的。 圖5.10：傾斜(skewed)和完整(complete)的二元樹 A A B B C C D E F G D H I E Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.2 二元樹 ADT Binary_Tree (abbreviated BinTree) is objects: a finite set of nodes either empty or consisting of a root node, left Binary_Tree and right Binary_Tree. functions: for all bt, bt1, bt2  BinTree, item  element BinTree Create() ::= create an empty binary tree Boolean IsEmpty(bt) ::= if (bt == empty binary tree) return TRUE else return FALSE BinTree MakeBT(bt1, item, bt2) ::= return a binary tree whose left subtree is bt1, whose right subtree is bt2, and whose root node contains the data item Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.2 二元樹 BinTree Lchild(bt) ::= if (IsEmpty(bt)) return error else return the left subtree of bt. element Data(bt) ::= if (IsEmpty(bt)) return error else return the data in the root node of bt. BinTree Rchild(bt) ::= if (IsEmpty(bt)) return error else return the right subtree of bt. Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.2 二元樹 5.2.2 二元樹之特性 輔助定理5.2［節點的最多個數］： 在二元樹的階層i上最多的節點個數為2i-1 ， i  1。 在深度為k的二元樹中最多的節點個數為2k – 1 ， k  1。 輔助定理5.3［葉節點個數與分支度為2的節點個數之間的關係］：對任何一個非空的二元樹T，如果n0為葉節點的個樹， n2為分支度為2的節點個數，則n0 = n2 + 1。 定義：一個深度為k的完全二元樹(full binary tree)即是深度為k， k ≥ 0，且具有2k – 1個節點的二元樹。 定義：一個二元樹有n個節點且深度為k之二元樹為完整的(complete)，若且惟若它的節點和一個深度為k的完全二元樹中編號從1到n的節點一致時。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.2 二元樹 圖5.11：節點以循序編號，深度為4之完全二元樹 level 1 1 2 2 3 3 4 5 6 7 4 8 9 10 11 12 13 14 15 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.2 二元樹 5.2.3 二元樹表示法 5.2.3.1陣列表示法 根據圖5.11我們可以用一維陣列來表達二元樹。編號i的節點對應至陣列的元素i。我們不用陣列中的第0個位置。 引理5.4：如果一個完整二元樹有n個節點以循序法表示，則任一節點i， 1 ≤ i ≤ n，我們可得到 parent(i)位在i/2，若i ≠ 1。如果i = 1，則i為根節點，且沒有父節點。 leftChild(i)位在2i，若2i ≤ n。如果2i > n，則i沒有左子節點。 rightChild(i)位在2i + 1，若2i + 1 ≤ n。如果2i + 1 > n，則i沒有右子節點。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.2 二元樹 圖5.12：圖5.10中的二元樹之陣列表示法 A B C D E [1] [2] [3] [4] [5] [6] [7] [8] [9] [16] [1] A [2] B [3] C [4] D [5] E [6] F [7] G [8] H [9] I Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.2 二元樹 5.2.3.2 鏈結表示法 雖然陣列表示法用來表達完整二元樹是非常有效的，但對其他的樹而言則會造成浪費。且此表達法也承襲了循序表示法的缺點。 我們可以用鏈結表示法來克服上述問題。 每一節點包含三個欄位：leftChild, data, rightChild。 在C中可定義為： typedef struct node *treePointer; typedef struct node { int data; treePointer leftChild, rightChild; } Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.2 二元樹 圖5.13：節點表示法 圖5.14：圖5.10之節點表示法 leftChild data rightChild Left Child root root A A B C B C D E F G D E H I Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.3 二元樹之尋訪 尋訪(traverse) 樹狀結構是我們常進行的一個動作。完整的尋訪可以產生樹的節點的線性順序。 當搜尋一個樹狀結構時，我們以相同的走訪方式來對待每一個節點及其子樹。 令L 、 V 、 R代表在一節點時向左移、訪問此節點、與向右移等三個動作，則有六種可能的尋訪順序：LVR 、LRV 、VLR 、VRL 、RVL 、RLV。 假設我們接受一種慣用法，先尋訪左邊，後尋訪右邊，則只剩下三種尋訪順序：LVR、LRV、VLR。 對這些尋訪順序我們分別命名為中序法(inorder)，後序法(postorder)以及先序法(preorder)。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.3 二元樹之尋訪 樹的尋訪與方程式之中序、後序與先序表示法有自然的關聯。 我們以圖5.16中的二元樹為例來說明這三種尋訪方式。 圖5.16：以二元樹表示一個運算式 + * E * D / C A B Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.3 二元樹之尋訪 5.3.1 中序尋訪 往左下直到無法繼續，拜訪此節點，往右繼續。如果無法往右，回到上一個節點再繼續。 精確的動作可用程式5.1的遞迴來描述。 程式5.1：二元樹的中序尋訪 void inorder(treePointer ptr) { if (ptr) { inorder(ptr->leftChild); printf(“%d”, ptr->data); inorder(ptr->rightChild); } + 1-1 1-3 1-2 * E 2-1 2-3 2-2 * D 3-1 3-3 3-1 3-3 3-2 3-2 / C 4-1 4-3 4-1 4-3 4-2 4-2 A B 5-1 5-3 5-1 5-3 5-2 5-2 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.3 二元樹之尋訪 圖5.17：程式5.1之執行歷程 圖5.16之資料欄位輸出的順序為：A/B*C*D+E Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.3 二元樹之尋訪 5.3.2 先序尋訪 拜訪節點，往左尋訪，若無法繼續，往右尋訪。若無法往右，往回直到可以往右為止。 程式5.2：二元樹之先序尋訪 void preorder(treePointer ptr) { if (ptr) { printf(“%d”, ptr->data); preorder(ptr->leftChild); preorder(ptr->rightChild); } 圖5.16之資料欄位輸出的順序為： + * */A B C D E Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.3 二元樹之尋訪 5.3.3 後序尋訪 程式5.3：二元樹之後序尋訪 void postorder(treePointer ptr) { if (ptr) { postorder(ptr->leftChild); postorder(ptr->rightChild); printf(“%d”, ptr->data); } 圖5.16之資料欄位輸出的順序為：A B / C * D * E + Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.3 二元樹之尋訪 5.3.4 迴圈式中序尋訪 雖然前面我們都以遞迴來實作，我們亦可使用迴圈。 程式5.4：迴圈式中序尋訪 void iterInorder(treePointer node) { int top = -1; treePointer stack[MAX_STACK_SIZE]; for (;;) { for (; node; node = node->leftChild) push(node); node = pop(); if (!node) break; printf(“%d”, node->data); node = node->rightChild; } Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.3 二元樹之尋訪 5.3.5 階序尋訪(Level-Order Traversal) 首先拜訪根節點，而後是根的左子節點，接著是根的右子節點。持續以這種方式拜訪每一階層中的節點，由最左邊的節點到最右邊的節點。 圖5.16之階序尋訪之結果：+ * E * D / C A B 程式5.5：二元樹的階序尋訪 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.3 二元樹之尋訪 void levelOrder(treePointer ptr) { int front = rear = 0; treePointer queue[MAX_QUEUE_SIZE]; if (!ptr) return; addq(ptr); for (;;) { ptr = deleteq(); if (ptr) { printf(“%d”, ptr->data); if (ptr->leftChild) addq(ptr->leftChild); if (ptr->rightChild) addq(ptr->rightChild); } else break; Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.4 其他的二元樹運算 5.4.1 複製二元樹 利用二元樹的定義以及遞迴版的中序，先序，和後序尋訪，我們可以很容易的產生其他的二元樹運算之C函數。 複製二元樹的程式如程式5.6。注意它其實只是將後序尋訪程式（程式5.3）作些微的修改。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.4 其他的二元樹運算 程式5.6：複製二元樹 treePointer copy(treePointer original) { treePointer temp; if (original) { MALLOC(temp, sizeof(*temp)); temp->leftChild = copy(original->leftChild); temp->rightChild = copy(original->rightChild); temp->data = original->data; return temp; } return NULL; Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.4 其他的二元樹運算 5.4.2 測試相等 相等的二元樹具有相同的構造，且在對應的節點中之資訊也是相同的。 程式5.7：測試二元樹之相等 int equal(treePointer first, treePointer second) { return ((!first && !second) || (first && second && (first->data == second->data) && equal(first->leftChild, second->leftChild) && equal(first->rightChild, second->rightChild))) } Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.4 其他的二元樹運算 5.4.3 判斷命題是否成立 考慮一組可以用變數x1, x2, ..., xn和運算子(and)， (or)與 (not)構成的公式。變數值只能是true或false之一。以這些變數和運算符號所形成的運算式由下列規則定義： 變數為一運算式。 若x與y為運算式，則x，x  y，x  y亦為運算式。 一般的計算順序為在之前，在之前，括號可用來改變一般的計算順序。 判斷命題是否成立是在問是否有一組變數的真假值組合會使得此命題為真。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.4 其他的二元樹運算 假設命題(x1  x2)  (x1  x3)  x3已表達成二元樹 圖5.18：用二元樹表達命題      x3 x1   x3 x2 x1 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.4 其他的二元樹運算 為了計算運算式之值，我們可以用後序法，對每一個子樹作計算，直到整個運算式變成單一值。 這個問題的節點構造如圖5.19。leftChild和rightChild欄位與先前所採用的方法類似。data欄儲存變數值或命題學的運算子之真假值，而value欄儲存一個TRUE或FALSE值。 圖5.19：命題是否成立問題所用的節點構造 leftChild data value rightChild Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.4 其他的二元樹運算 C中結構的定義： typedef enum {not, and, or, true, false} logical; typedef struct node *treePointer; typedef struct node { treePointer leftChild; logical data; short int value; treePointer rightChild; } Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.4 其他的二元樹運算 程式5.8：命題成立演算法之第一個版本 for (all 2n possible combinations) { generate the next combination; replace the variables by their values; evaluate root by traversing it in postorder; if (root->value) { printf(<combination>); return; } printf(“No satisfiable combination\n”); Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.4 其他的二元樹運算 程式5.9：後序評估函數 void postOrderEval(treePointer node) { if (node) { postOrderEval (node->leftChild); postOrderEval (node->rightChild); switch (node->data) { case not : node->value = !node->rightChild->value; break; case and : node->value = node->rightChild->value && node->leftChild->value ; case or : node->value = node->rightChild->value || node->leftChild->value; Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.4 其他的二元樹運算 case true: node->value = TRUE; break; case false: node->value = FALSE; } Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.5 引線二元樹 5.5.1 引線(threads) 當使用鏈結表示法時，我們發現存在著許多空鏈結（2n個鏈結裏有n+1個是空的）。Perlis與Thornton發展了一個方法來利用些空鏈結。 使用指向其他節點的指標，稱為引線，來取代空鏈結。 要建立引線樹，採用下列的規則（假設ptr表示一節點） 如果ptr->leftChild為空的，將ptr->leftChild以指向一個節點的指標取代，此節點是中序尋訪時在ptr之前拜訪的節點。亦即，我們將空鏈結替換成指向ptr的中序前行節點(inorder predecessor)之指標。 如果ptr->rightChild為空的，將ptr->rightChild以指向一個節點的指標取代，此節點是中序尋訪時在ptr之後拜訪的節點。亦即，我們將空鏈結替換成指向ptr的中序後續節點(inorder successor)之指標。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.5 引線二元樹 圖5.21：與圖5.10(b)對應的引線樹 root A B C D E F G H I Inorder sequence: H, D, I, B, E, A, F, C, G Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.5 引線二元樹 當我們將樹狀結構儲存在記憶體時，必須能夠區分引線和一般鏈結。這可以在節點構造中在加入兩個欄位來達成，即leftThread和rightThread。 如果ptr->leftThread = TRUE，則ptr->leftChild包含一個引線。否則它包含指向左子節點的指標。 如果ptr->rightThread = TRUE，則ptr->rightChild包含一個引線。否則它包含指向右子節點的指標。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.5 引線二元樹 C中之宣告 typedef struct threadedTree *threadedPointer; typedef struct threadTree { short int leftThread; threadedPointer leftChild; char data; threadedPointer rightChild; short int rightThread; } 圖5.21中有兩個懸空的引線。為了不遺留懸空引線，我們使用一標頭節點。原來的樹為此標頭節點之左子節點。這表示空的引線樹永遠包含一個標頭節點。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.5 引線二元樹 圖5.22：空的引線二元樹 圖5.23：引線樹的記憶體表示法 leftThread leftChild data rightChild rightThread TRUE FALSE root f - f f = FALSE t = TRUE f A f f B f f C f f D t E t t F t t G t t H t t I t Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.5 引線二元樹 5.5.2 引線二元樹之中序尋訪 對任意節點ptr而言，如果ptr->rightThread = TRUE，其中序後續節點即為ptr->rightChild。否則我們可以從ptr的右子節點開始，一直循著左子節點鏈結尋找直到找到一節點其leftThread = TRUE為止。 程式5.10：尋找一節點之中序後續節點 threadedPointer insucc(threadedPointer tree) { threadedPointer temp; temp = tree->rightChild; if (!tree->rightThread) while (!temp->leftThread) temp = temp->leftChild; return temp; } Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.5 引線二元樹 程式5.11：引線二元樹之中序尋訪 void tinorder(threadedPointer tree) { threadedPointer temp = tree; for (;;) { temp = insucc(temp); if (temp == tree) break; printf(“%3c”, temp->data); } Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.5 引線二元樹 5.5.3插入一個節點到引線二元樹 我們現在想要將r插入為節點s之右子節點。 如果s之右子樹為空，則此插入十分簡單，如圖5.24(a)所示。 如果s的右子樹不為空，則其右子樹在插入後會成為r的右子樹。完成後，r會成為具有leftThread = TRUE之節點的中序前行節點，造成有一個引線應該指向r。包含此引線的節點即為s之前的中序後續節點。如圖5.24(b)。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.5 引線二元樹 圖5.24：將r插入為s的右子節點 s s r r 插入前 插入後 ( a ) Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.5 引線二元樹 s s r r 插入前 插入後 (b) Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.5 引線二元樹 程式5.12：在引線二元樹中插入右子節點 void insertRight(threadedPointer s, threadedPointer r) { threadedPointer temp; r->rightChild = s->rightChild; r->rightThread = s->rightThread; r->leftChild = s; r->leftThread = TRUE; s->rightChild = r; s->rightThread = FALSE; if (!r->rightThread) { temp = insucc(r); temp->leftChild = r; } Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.6 堆積(Heaps) 5.6.1 優先權佇列(Priority Queues) 優先權佇列可以刪除具有最高（或最低）優先權的元素。在任何時候我們可以加入具有任意優先權的元素到優先權佇列中。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.6 堆積(Heaps) ADT MaxPriorityQueue is objects: a collection of n > 0 elements, each element has a key. functions: for all q  MaxPriorityQueue, item  Element, n  integer MaxPriorityQueue Create(max_size)::= create an empty priority queue Boolean isEmpty(q, n) ::= if (n > 0) return TRUE else return FALSE Element top(q, n) ::= if (!isEmpty(q, n) return an instance of the largest element in q else return error. Element pop(q, n) ::= if (!isEmpty(q, n) return an instance of the largest element in q and remove it from the heap else return error. MaxPriorityQueue push(q, item, n) ::= insert item into q and return the resulting queue. Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.6 堆積(Heaps) 5.6.2 最大堆積之定義 定義：最大（最小）樹(max (min) tree)是一種樹，其中每一節點的鍵值不小（大）於他的子節點的( 如果有存在的話 )鍵值。最大堆積(max heap)為一種也是最大樹的完整二元樹。最小堆積(min heap)為也是最小樹的完整二元樹。 圖5.25：最大堆積範例 14 9 30 12 7 6 3 25 10 8 6 5 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.6 堆積(Heaps) 圖5.26：最小堆積範例 在最小樹中之根節點的鍵值為整個樹中最小的；在最大樹中之根節點的鍵值為整個樹中最大的。 最大堆積的基本運算和最大優先權佇列相同(ADT 5.2)。 由於最大堆積為完整二元樹，我們用陣列heap來表示它。 2 10 11 7 4 20 83 21 10 8 6 50 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.6 堆積(Heaps) 5.6.3 插入一個節點至最大堆積 圖5.27：插入至最大堆積 20 15 2 (b) 新節點起始位置 14 10 20 21 (a)插入前的堆積 15 5 15 20 14 10 2 14 10 2 (c) 在堆積(a)插入5 (d) 在堆積(a)插入21 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.6 堆積(Heaps) 要實作我們所說的插入策略，我們必須由一個元素走到它的父節點。輔助定理5.4讓我們可以很容易的找到任何元素的父節點。 堆積的C語言宣告 #define MAX_ELEMENTS 20 #define HEAP_FULL(n) (n == MAX_ELEMENTS – 1) #define HEAP_EMPTY(n) (!n) typedef struct { int key; /* other fields */ } element; element heap[MAX_ELEMENTS]; int n = 0; Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.6 堆積(Heaps) 程式5.13：插入至最大堆積 void push(element item, int *n) { int i; if (HEAP_FULL(*n)) { fprintf(stderr, “The heap is full.\n”); exit(EXIT_FAILURE); } i = ++(*n); while ((i != 1) && (item.key > heap[i / 2].key)) { heap[i] = heap[i / 2]; i /= 2; } /* bubbling up */ heap[i] = item; Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.6 堆積(Heaps) 5.6.4 自最大堆積刪除 圖5.28：自堆積刪除 20 15 2 (b) 刪除20後之樹結構 15 14 10 (a) 自5.27(d)堆積結構刪除21，其結果為5.27(a) 14 2 10 (c) 形成的堆積 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.6 堆積(Heaps) 程式5.14：自最大堆積刪除 element pop(int *n) { int parent, child; element item, temp; if (HEAP_EMPTY(*n)) { fprintf(stderr, “The heap is empty\n”); exit(EXIT_FAILURE); } item = heap[1];/*儲存最大鍵值之元素*/ temp = heap[(*n)--];/*使用最後的元素來調整堆積*/ parent = 1; child = 2; Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.6 堆積(Heaps) while (child <= *n) { if ((child < *n) && (heap[child].key < heap[child + 1].key)) child++;/*找出較大的孩子*/ if (temp.key >= heap[child].key) break; heap[parent] = heap[child];/*移至下一層*/ parent = child; child *= 2; } heap[parent] = temp; return item; Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.7 二元搜尋樹 5.7.1 定義 一字典(dictionary)為一配對(pair)之集合，每一配對包含一鍵值與其所對應之值。 在此假設沒有任何配對具有相同的鍵值。 ADT 5.3：抽象資料型態Dictionary Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.7 二元搜尋樹 當要執行的動作為搜尋、插入、或刪除時，二元搜尋樹比之前所提到的任何樹都更有效率。 上述動作皆可依鍵值或依排行進行。 例：找出鍵值為k之項目，找出排行倒數第五的項目。 定義：二元搜尋樹(binary search tree)是一種二元樹。它可能是空的。如果不是空的具有下列特性： 每一個節點有一鍵值，而每一節點之鍵值都不一樣。 在非空的左子樹上的所有鍵值必小於在該子樹的根節點中的鍵值。 在非空的右子樹上的所有鍵值必大於在該子樹的根節點中的鍵值。 左子樹和右子樹都是二元搜尋樹。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.7 二元搜尋樹 圖5.29：二元樹 30 5 40 2 20 15 25 14 10 22 (a) (b) 60 70 80 65 (c) Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.7 二元搜尋樹 5.7.2 搜尋二元搜尋樹 假設我們要搜尋一鍵值為k之節點。我們由根節點開始。 如果根節點是NULL，則搜尋樹是空的，且搜尋是失敗的。 如果根點不是NULL，則比較k與根節點之鍵值： 如果k和根節點的鍵值相等，則搜尋成功且結束。 如果k小於根節點的鍵值，則右子樹沒有任何一個節點的鍵值可能等於k。所以搜尋根節點的左子樹。 如果k大於根節點的鍵值，則搜尋根節點的右子樹。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.7 二元搜尋樹 程式5.15：二元搜尋樹之遞迴式搜尋 element* search(treePointer root, int k) { if (!root) return NULL; if (k == root->data.key) return &(root->data); if (k < root->data.key) return search(root->leftChild, k); return search(root->rightChild, k); } Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.7 二元搜尋樹 程式5.16：二元搜尋樹的迴圈式搜尋 element iterSearch(treePointer tree, int k) { while (tree) { if (k == tree->data.key) return &(tree->data); if (k < tree->data.key) tree = tree->leftChild; else tree = tree->rightChild; } return NULL; Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.7 二元搜尋樹 5.7.3 在二元搜尋樹中插入元素 要插入一個鍵值為k之配對，首先必須檢查此鍵值和現有配對的鍵值是不同的。 為了驗證這一點，我們必須搜尋此樹。如果搜尋不成功，我們可以在搜尋結束點插入此配對。 圖5.30：插入至二元搜尋樹 30 30 5 40 5 40 2 80 2 35 80 (a) 插入80至圖5.29(b) (b) 插入35 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.7 二元搜尋樹 程式5.17：插入一配對至二元搜尋樹 void insert(treePointer *node, int k, iType theItem) { treePointer ptr, temp = modifiedSearch(*node, k); if (temp || !(*node)) { MALLOC(ptr, sizeof(*ptr)); ptr->data.key = k; ptr->data.item = theItem; ptr->leftChild = ptr->rightChild = NULL; if (*node) if (k < temp->data.key) temp->leftChild = ptr; else temp->rightChild = ptr; else *node = ptr; } Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.7 二元搜尋樹 5.7.4 從二元搜尋樹中刪除元素 要刪除葉節點，只要將它的父節點之左節點欄位設定為NULL並釋回此節點即可。 刪除只有一個子節點的內部節點：將節點刪除，而後將它的單一子節點放在被刪除的節點之位置上即可。 刪除具有兩個子節點的內部節點： 以被刪除的節點之左子樹中最大的配對來取代它的位置。 或以被刪除的節點之右子樹中最小的配對來取代它的位置。 而後自其所屬之子樹刪除此配對。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.7 二元搜尋樹 圖5.31：從二元搜尋樹中刪除元素 5 5 2 40 5 40 2 80 80 (b) 刪除後 (a) 自圖5.30(a)刪除30 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.7 二元搜尋樹 5.7.5 合併與分開二元樹 除了搜尋、插入與刪除之外，下列運算也常被用到： threeWayJoin(small, mid, big)：建立一包含small與big此二個二元搜尋樹及配對mid之二元搜尋樹。在此假設small中的所有鍵值皆小於mid.key，在big中的所有鍵值皆大於mid.key。在合併後，small與big皆為空。 twoWayJoin(small, big)：建立一包含small與big此二個二元搜尋樹之二元搜尋樹。在此假設small中的所有鍵值皆小於big中的所有鍵值。在合併後，small與big皆為空。 split(theTree, k, small, mid, big)：二元搜尋樹theTree被分成三個部份：small為包含theTree中所有鍵值小於k之配對的二元搜尋樹；mid為theTree中鍵值為k的配對（若存在）； big為包含theTree中所有鍵值大於k之配對的二元搜尋樹。分開後theTree為空。當theTree中並無鍵值為k之配對時，mid.key設為-1。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.7 二元搜尋樹 5.7.6 二元搜尋樹之高度 若不小心，具有n個元素的二元搜尋樹之高度可高達n。 例如：依序插入鍵值為1, 2, ..., n之元素。 若隨機插入元素，則二元搜尋樹之平均高度為O(log n)。 若搜尋樹之高度最差情形為O(log n)時，稱為平衡搜尋樹(balanced search tree)。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.8 選取樹(selection tree) 5.8.1 簡介 假設我們想要將k個稱為行程(run)的序列合併為一。每一行程皆依某一鍵值由小而大排列之記錄。令n為k個行程中所有的記錄之各數。 要達成合併可以重覆的輸出具有最小鍵值的記錄，它一定是此k個行程中之一的第一個記錄。 要合併k個行程最直接的方法是經過k-1次的比較來決定下一個要輸出的紀錄。當k>2，利用選取樹的觀念，可以減少找到下一個最小的元素所需要的比較次數。 選取樹有兩種：勝者樹(winner tree)與敗者樹(loser tree)。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.8 選取樹(selection tree) 5.8.2 勝者樹 勝者樹為一完整二元樹，其中每一個節點代表它的兩個子節點中的較小者。所以，根節點代表樹結構中最小的節點。 勝者樹之建立很像比賽時之賽程表，其中勝者代表具有較小鍵值的記錄。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.8 選取樹(selection tree) 圖5.32：k=8時的勝者樹，它顯示八個行程中各個行程的前三個鍵值 1 6 2 3 6 8 4 5 7 6 9 6 8 17 8 9 10 11 12 13 14 15 10 9 20 6 8 9 90 17 15 20 20 15 15 11 95 18 16 38 30 25 50 16 99 20 28 run1 run2 run3 run4 run5 run6 run7 run8 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.8 選取樹(selection tree) 圖5.33：圖5.32中的選取樹在輸出一個記錄後重整的結果 1 8 2 3 9 8 4 5 7 6 9 15 8 17 8 9 10 11 12 13 14 15 10 9 20 15 8 9 90 17 15 20 20 25 15 11 95 18 16 38 30 28 50 16 99 20 run1 run2 run3 run4 run5 run6 run7 run8 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.8 選取樹(selection tree) 5.8.3 敗者樹 當圖5.32之最小記錄輸出後，我們必須重建勝者樹。 將行程4之下一個記錄插入至此樹中。此記錄之鍵值為15。 之前的競賽發生於節點11至根節點之路徑中，由於此路徑代表之前之兄弟節點競賽之敗者，我們可以藉由將此徑中之非葉節點指向敗者來簡化重建之過程。 每一非葉節點皆具有一指向敗者的指標之選取樹稱為敗者樹。 開始重建時，我們只需重新進行從節點11至根節點之賽事。要比賽的對象已記錄在此賽程之根節點中。 因此，由節點11至根節點之路徑中之兄弟節點皆不用被存取。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.8 選取樹(selection tree) 圖5.34：對應於圖5.32之敗者樹 6 Overall winner 1 8 2 3 9 17 4 5 7 6 10 20 9 90 9 10 11 12 13 14 15 10 9 20 6 8 9 90 17 run 1 2 3 4 5 6 7 8 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.9 樹林 定義：樹林(forest)是一組n個，n0的不同的樹之集合。 樹林的觀念和樹的觀念很接近，因為，我們若將一樹的根節點刪除，即可形成樹林。 圖5.35：三樹之樹林 5.9.1 將樹林轉換成二元搜尋樹 要將樹林轉換為二元搜尋樹，我們首先將每一個樹轉換為二元樹，再將這些二元樹藉由根節點之rightChild欄位連結起來。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.9 樹林 圖5.36：圖5.35之樹林之二元樹表示法 定義：如果T1, …, Tn為樹林，則此樹林對應的二元樹B(T1, …, Tn) 是： 空的，若n = 0 根節點與root(T1)相同；左子樹與B(T11, T12,…, T1m),相同，其中T11, T12,…, T1m為root (T1)的子樹；右子樹為B(T2, …, Tn)。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.9 樹林 5.9.2 樹林之尋訪 一樹林F對應的二元樹T之先序，中序和後序尋訪，與F的先序，中序和後序尋訪有自然的關聯。 樹林先序(forest preorder)： 若F為空則返回。 拜訪F的第一個樹的根節點。 依樹林先序尋訪第一個樹的子樹。 依樹林先序尋訪F中的其他樹。 樹林中序(forest inorder)： Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.9 樹林 樹林後序(forest postorder)： 若F為空則返回。 依樹林先序尋訪第一個樹的子樹。 依樹林先序尋訪F中的其他樹。 拜訪F的第一個樹的根節點。 樹林之階序尋訪由拜訪每一個樹的根節點開始，然後在每一階層中，依序由左至右拜訪。 樹林之階序尋訪與其所對應之二元樹之階序尋訪不一定會產生相同的結果。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.10 互斥集合的表示法 5.10.1 簡介 樹狀結構也可以用來表示集合。 圖5.37：集合可能的樹林表示法（將0...9分成三集合） 在這些集合上我們希望進行的至少有下列運算： 互斥集合之聯集(Disjoint Set Union)：如果Si 和 Sj為兩個互斥的集合，則其聯集Si ∪Sj = {x，x為在集合 Si 或 Sj中的元素}。 Find (i)：找尋包含元素i的集合。 4 1 9 2 3 5 6 7 8 S1 S2 S3 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.10 互斥集合的表示法 5.10.2 Union與Find運算 要進行聯集，我們只需將一集合作為另一集合之子樹。 圖5.38： S1 ∪ S2 可能的表示法 6 7 8 4 1 9 S1 ∪ S2 　　　　 或 　　　　　　 S1 ∪ S2 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.10 互斥集合的表示法 要實作集合的聯集運算，我們只要將一個根節點的parent欄位設定成另一個根節點即可。 如果每一個根節點有一個指向集合名稱的指標，則根據parent鏈結，我們可以由一個元素找到其根節點，再傳回指向集合名稱的指標，就可以找到原屬在哪一個集合中。 圖5.39：S1, S2, S3的資料表示法 S1 S2 S3 4 1 9 2 3 5 6 7 8 集合名稱 指標 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.10 集合的表示法 為了簡化表達，我們使用根節點來表達集合。 要找出集合名稱很容易。假設集合名稱存在name[]中。如果i是根節點為j的樹中的一個元素，而j有一個指標指向集合名稱表格中第k項，則集合名稱即為name[k]。 因為樹中節點的編號從0到n-1，所以我們可以利用節點的編號作索引。 因此每一節點只需一欄位，即其父節點之索引，來指向其父節點。因此我們只需使用陣列即可。 圖5.40： S1, S2, S3 的陣列表示法 i [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] parent -1 4 -1 2 -1 2 4 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.10 集合的表示法 要找到節點i所在之集合，我們只需由i開始依其parent值尋找，直到遇見負的parent值為止。 union(i,j)也很容易。若有兩樹其根節點各為i與j。如果我們採用將第一個樹作為第二個樹之子樹的作法。那我們只需使用parent[i] = j指令即可完成聯集運算。 程式5.19：union與find程式的初步嘗試 int simpleFind(int i) { for (; parent[i] > 0; i = parent[i]) ; return i; } Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.10 集合的表示法 void simpleUnion(int i, int j) { parent[i] = j; } 分析：如果Si = {i}，0  i < p，則一開始的架構是具有p個節點的樹林，且parent[i] = 1， 0  i < p。接下來的運算： union(0, 1), find(0) union(1, 2), find(0) … union(n2, n1), find(0) 這個順序會產生退化樹(degenerate tree)。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.10 集合的表示法 圖5.41：退化樹 為了避免產生退化樹，我們可以採用下列的加權規則。 定義：union(i, j)的加權規則。如果樹狀結構i中的節點個數少於樹狀結構j中的節點個數，則令j為i的父節點；否則，令i為j的父節點。 n-1 n-2 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.10 集合的表示法 圖5.42：使用加權規則所得的樹 1 n-1 2 n-1 3 n-1 1 1 2 union(0,2) initial union(0,1) 4 n-1 1 2 3 1 2 3 n-1 union(0,3) union(0,n-1) Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.10 集合的表示法 要實作加權規則，我們必須知道在每一樹中有多少節點。若i為根節點，則count[i]等於此樹之節點數。 我們將節點數以負值存放在根節點中。 程式5.20：使用加權規則的聯集函數 void weightedUnion(inti, int j) { /* parent[i] = -count[i]; parent[j] = -count[j]; */ int temp = parent[i] + parent[j]; if (parent[i] > parent[j]) { parent[i] = j; parent[j] = temp; } else { parent[j] = i; parent[i] = temp; Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.10 集合的表示法 定義[塌陷規則collapsing rule]：如果j是從i到其根節點的路徑上的一個節點，且parent[i]  root[i]，則令parent[j]為root[i]。 程式5.21：塌陷規則 int collapsingFind(int i) { int root, trail, lead; for (root = i; parent[root] >= 0; root = parent[root]) ; for (trail = i; trail != root; trail = lead) { lead = parent[trail]; parent[trail] = root; } return root; Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.11 二元樹之計數 5.11.1 不同的二元樹 令n為節點數。當n = 0或n = 1時，只有一個二元樹。當n = 2時，有兩個不同的二元樹。當n = 3時，有5個不同的二元樹。 當節點數為n時，有多少個不同的二元樹呢？ 5.11.2 堆疊排列 假設某一樹之先序尋訪序列為A B C D E F G H I，其中序尋訪序列為B C A E D G H F I。這兩序列是否可義一唯一的樹？另一種說法，這兩個序列是否可以來自不同的樹？ Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.11 二元樹之計數 根據先序序列的第一個字母A，我們知道它一定是此樹之根節點。再根據中序序列，我們可知A之前的節點(B C)為A之左子樹，其餘的節點(E D G H F I)為右子樹。如圖5.47(a)所示。 繼續看先序序列，我們得到B為下一根節點。由於在中序序列中之B之前已無節點，B之左子樹為空，因此C為其右子樹，如圖5.47(b)所示。 繼續使用上述方法，我們可以得到圖5.48(a)之結果。 每一二元樹有唯一之先序／中序序列配對。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.11 二元樹之計數 圖5.47：由先序與中序序列建立二元樹 A A B, C D, E, F, G, H, I B D, E, F, G, H, I C ( a ) ( b ) Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.11 二元樹之計數 圖5.48：依先序與中序序列建立之二元樹 A 1 B D 2 4 C 3 E F 5 6 7 9 G I 8 H (a) (b) Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.11 二元樹之計數 令一n節點之二元樹之節點由1至n號。由此二元樹所定義之中序排列(inorder permutation)定義為此樹在進行中序尋訪時所拜訪之節點之順序。先序排列之定義類似。 例如，令圖5.48(a)之二元樹之節點順序如圖5.48(b)所示。則其先序排列為1, 2, ..., 9。其中序排列為2, 3, 1, 5, 4, 7, 8, 6, 9。 如果一樹的節點編號後之先序排列為1, 2, ..., n，則不同的中序排列定義了不同的二元樹。因此，不同的二元樹數量等於不同的中序排列數。 將數字1至n藉由堆疊傳遞並依所有可能方式取出之方法數會等於具有n個節點之不同二元樹之數量。 Hsin-Chang Yang@NUKIM

Hsin-Chang Yang@NUKIM 5.11 二元樹之計數 假設有數值1, 2, 3，則由堆疊所得之可能排列為(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 2, 1)。(3, 1, 2)不可能獲得。這五種排列各自對應至具有三節點之二元樹的其中一種。如圖5.49所示。 圖5.49：對應至五種排列的二元樹 1 1 1 1 1 2 2 2 3 2 2 3 3 3 3 (1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 2, 1) Hsin-Chang Yang@NUKIM