第 5 章　樹狀結構

5.1　簡介

5.1.1　專有名詞

直觀上而言，樹狀結構的觀念暗示了我們要組織資料，使其資料項的關係因分支而定。舉例而言，當我們要調查族譜時可應用樹狀結構。一般而言，有兩種族系圖可用來表示我們的資料，即血統表與直系表。

5.1.2　樹狀結構表示法

串列表示法

圖 5.2 中的樹可寫成一個串列，其中的每一子樹也是一個串列。使用這個表示法，圖 5.2 的樹狀結構可寫成：

注意，在根節點中的資訊首先寫出，其後是此節點的子樹之串列。

左子-右弟表示法 (left child-right sibling)

5.2　二元樹

5.2.1　抽象資料型態

structure 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 in BinTree, item in element

    BinTree Create()             ::= creates 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.
    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.

end Binary_Tree

結構 5.1：抽象資料型態 Binary Tree —— 「此結構僅定義一組最少的二元樹之運算，它們可作為建立其他的運算之基礎。」

5.2.2　二元樹的特性

5.2.3　二元樹表示法

typedef struct node *tree_pointer;
typedef struct node {
        int data;
        tree_pointer left_child, right_child;
        };

鏈結表示法 —— 「採用鏈結表示法即可輕易地克服這個問題。」若必須知道任一節點的父節點，可以加入第四個欄位 parent。

5.3　二元樹之尋訪

在樹狀結構上可執行多種運算，但常用的一種是尋訪樹狀結構（traversing a tree），即走訪樹中的每一個節點，且每個節點恰好被尋訪一次。完全的尋訪可產生儲存在樹裏的資訊之線性序列。

三個遞迴函數

void inorder(tree_pointer ptr)
/* inorder tree traversal */
{
   if (ptr) {
      inorder(ptr->left_child);
      printf("%d",ptr->data);
      inorder(ptr->right_child);
   }
}

程式 5.1：二元樹的中序尋訪 —— 輸出 A / B * C * D + E

void preorder(tree_pointer ptr)
/* preorder tree traversal */
{
   if (ptr) {
      printf("%d",ptr->data);
      preorder(ptr->left_child);
      preorder(ptr->right_child);
   }
}

程式 5.2：二元樹的先序尋訪 —— 輸出 + * * / A B C D E

void postorder(tree_pointer ptr)
/* postorder tree traversal */
{
   if (ptr) {
      postorder(ptr->left_child);
      postorder(ptr->right_child);
      printf("%d",ptr->data);
   }
}

程式 5.3：二元樹的後序尋訪 —— 輸出 A B / C * D * E +

迴路式中序尋訪

「雖然我們以遞迴函數來設計中序，先序和後序尋訪，我們也可以設計對等的迴路式函數。要模擬遞迴呼叫，我們必須建立自己的堆疊。我們要使用和遞迴版本處理系統堆疊的相同方法對我們的堆疊加入或刪除節點。這可幫助我們完全地瞭解遞迴版的運算方式。」

void iter_inorder(tree_pointer node)
{
   int top = -1; /* initialize stack */
   tree_pointer stack[MAX_STACK_SIZE];
   for (;;) {
      for (; node; node = node->left_child)
         add(&top, node); /* add to stack */
      node = delete(&top); /* delete from stack */
      if (!node) break; /* empty stack */
      printf("%d", node->data);
      node = node->right_child;
   }
}

程式 5.4：迴路式中序尋訪

階序尋訪 (level order)

void level_order(tree_pointer ptr)
/* level order tree traversal */
{
   int front = rear = 0;
   tree_pointer queue[MAX_QUEUE_SIZE];
   if (!ptr) return; /* empty tree */
   addq(front, &rear, ptr);
   for (;;) {
      ptr = deleteq(&front, rear);
      if (ptr) {
         printf("%d",ptr->data);
         if (ptr->left_child)
            addq(front,&rear,ptr->left_child);
         if (ptr->right_child)
            addq(front,&rear,ptr->right_child);
      }
      else break;
   }
}

程式 5.5：二元樹的階序尋訪 —— 圖 5.15 的結果為 + * E * D / C A B

void iter_preorder(tree_pointer node)
{
   int top = -1;
   tree_pointer stack[MAX_STACK_SIZE];
   if (!node) return;
   add(&top, node);
   while (top > -1) {
      node = delete(&top);
      printf("%d", node->data);
      if (node->right_child) add(&top, node->right_child);
      if (node->left_child)  add(&top, node->left_child);
   }
}

5.4　其他的二元樹運算

「利用二元樹的定義以及遞迴版的中序，先序和後序尋訪，我們可以很容易地產生其他的二元樹運算之 C 函數。」

tree_pointer copy(tree_pointer original)
/* this function returns a tree_pointer to an exact copy
of the original tree */
{
   tree_pointer temp;
   if (original) {
      temp = (tree_pointer) malloc(sizeof(node));
      if (IS_FULL(temp)) {
         fprintf(stderr, "The memory is full\n");
         exit(1);
      }
      temp->left_child = copy(original->left_child);
      temp->right_child = copy(original->right_child);
      temp->data = original->data;
      return temp;
   }
   return NULL;
}

程式 5.6：複製二元樹 ——「請留意此函數是 postorder（程式 5.3）稍作修改所得到的版本。」

int equal(tree_pointer first, tree_pointer second)
{
/* function returns FALSE if the binary trees first and
second are not equal, Otherwise it returns TRUE */
   return ((!first && !second) || (first && second &&
           (first->data == second->data) &&
           equal(first->left_child,second->left_child) &&
           equal(first->right_child, second->right_child)))
}

程式 5.7：測試二元樹是否對等 ——「以先序尋訪的改良版來測試」

判斷命題是否成立 (satisfiability)

考慮一組可以用變數 $x_1, x_2, \ldots, x_n$ 和運算符號 $\land$ (and)、$\lor$ (or) 與 $\lnot$ (not) 構成的公式。變數值只能是 true 或 false 之一。運算式的定義規則：

1. 變數是一個運算式
2. 若 $x$、$y$ 為運算式，則 $\lnot x$、$x \land y$、$x \lor y$ 也是運算式
3. 一般的計算順序為 $\lnot$ 在 $\land$ 之前，$\land$ 在 $\lor$ 之前，括號可用來改變一般的計算順序

void post_order_eval(tree_pointer node)
{
/* modified post order traversal to evaluate a
propositional calculus tree */
   if (node) {
      post_order_eval(node->left_child);
      post_order_eval(node->right_child);
      switch(node->data) {
         case not:   node->value =
                !node->right_child->value;
                break;
         case and:   node->value =
                node->right_child->value &&
                node->left_child->value;
                break;
         case or:    node->value =
                node->right_child->value ||
                node->left_child->value;
                break;
         case true:  node->value = TRUE;
                break;
         case false: node->value = FALSE;
      }
   }
}

程式 5.9：post_order_eval 函數

int leaf_count(tree_pointer ptr)
{
   if (!ptr) return 0;
   if (!ptr->left_child && !ptr->right_child) return 1;
   return leaf_count(ptr->left_child) + leaf_count(ptr->right_child);
}

5.5　引線樹 (threaded binary trees)

typedef struct threaded_tree *threaded_pointer;
typedef struct threaded_tree {
        short int left_thread;
        threaded_pointer left_child;
        char data;
        threaded_pointer right_child;
        short int right_thread;
        };

「當我們將樹狀結構儲存在記憶體時，必須能夠區別引線和一般的指標。這可以在節點構造中再加入兩個欄位來達成，即 left_thread 和 right_thread。」

引線二元樹的中序尋訪

threaded_pointer insucc(threaded_pointer tree)
{
/* find the inorder sucessor of tree in a threaded binary
tree */
   threaded_pointer temp;
   temp = tree->right_child;
   if (!tree->right_thread)
      while (!temp->left_thread)
         temp = temp->left_child;
   return temp;
}

程式 5.10：找尋一個節點的中序後續節點 ——不須使用堆疊

void tinorder(threaded_pointer tree)
{
/* traverse the threaded binary tree inorder */
   threaded_pointer temp = tree;
   for (;;) {
      temp = insucc(temp);
      if (temp == tree) break;
      printf("%3c", temp->data);
   }
}

程式 5.11：引線二元樹的中序尋訪

在引線二元樹中插入節點

「我們只討論插入新的節點作為現有的節點 parent 之右子節點之狀況，插入左子節點則留作習題。」

void insert_right(threaded_pointer parent,
                                threaded_pointer child)
{
/* insert child as the right child of parent in a threaded
binary tree */
   threaded_pointer temp;
   child->right_child = parent->right_child;
   child->right_thread = parent->right_thread;
   child->left_child = parent;
   child->left_thread = TRUE;
   parent->right_child = child;
   parent->right_thread = FALSE;
   if (!child->right_thread) {
      temp = insucc(child);
      temp->left_child = child;
   }
}

程式 5.12：在引線二元樹中插入右子節點 —— 最後三行就是處理「情況二」

5.6　累堆 (heaps)

5.6.1　累堆抽象資料型態

structure MaxHeap is
  objects: a complete binary tree of n > 0 elements organized so that
  the value in each node is at least as large as those in its children
  functions:
    for all heap in MaxHeap, item in Element, n, max_size in integer

    MaxHeap Create(max_size)     ::= create an empty heap that can hold a
                                     maximum of max_size elements.
    Boolean HeapFull(heap, n)    ::= if (n == max_size) return TRUE
                                     else return FALSE
    MaxHeap Insert(heap, item, n)::= if (!HeapFull(heap, n)) insert item
                                     into heap and return the resulting
                                     heap else return error.
    Boolean HeapEmpty(heap, n)   ::= if (n > 0) return TRUE
                                     else return FALSE
    Element Delete(heap, n)      ::= if (!HeapEmpty(heap, n)) return one
                                     instance of the largest element in
                                     the heap and remove it from the heap
                                     else return error.

end MaxHeap

結構 5.2：抽象資料型態 MaxHeap

優先佇列表示法的比較

圖 5.27：優先佇列表示法 —— 其他四種都在插入和刪除之間走極端，只有累堆兩邊都是對數時間。

5.6.2　插入與刪除

插入到最大累堆

#define MAX_ELEMENTS 200 /* maximum heap size+1 */
#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;

void insert_max_heap(element item, int *n)
{
/*insert item into a max heap of current size *n */
   int i;
   if (HEAP_FULL(*n)){
      fprintf(stderr, "The heap is full. \n");
      exit(1);
   }
   i = ++(*n);
   while ((i != 1) && (item.key > heap[i/2].key)) {
      heap[i] = heap[i/2];
      i /= 2;
   }
   heap[i] = item;
}

程式 5.13：插入元素到最大累堆

從最大累堆刪除

element delete_max_heap(int *n)
{
/* delete element with the highest key from the heap */
   int parent, child;
   element item, temp;
   if (HEAP_EMPTY(*n)) {
      fprintf(stderr, "The heap is empty\n");
      exit(1);
   }
   /* save value of the element with the highest key */
   item = heap[1];
   /* use last element in heap to adjust heap */
   temp = heap[(*n)--];
   parent = 1;
   child = 2;
   while (child <= *n) {
      /* find the larger child of the current parent */
      if ((child < *n) &&
          (heap[child].key < heap[child+1].key))
         child++;
      if (temp.key >= heap[child].key) break;
      /* move to the next lower level */
      heap[parent] = heap[child];
      parent = child;
      child *= 2;
   }
   heap[parent] = temp;
   return item;
}

程式 5.14：從最大累堆刪除節點 —— 同樣是 $O(\log_2 n)$

5.7　二元搜尋樹

5.7.1　簡介

5.7.2　找尋一個二元搜尋樹

tree_pointer search2(tree_pointer tree, int key)
{
/* return a pointer to the node that contains key.  If
there is no such node, return NULL. */
   while (tree) {
      if (key == tree->data) return tree;
      if (key < tree->data)
         tree = tree->left_child;
      else
         tree = tree->right_child;
   }
   return NULL;
}

程式 5.16：二元搜尋樹的迴路式找尋

5.7.3　在二元搜尋樹中插入元素

「要插入一個新的元素 key，首先必須檢查此鍵值和現有元素的鍵值是不同的。為了驗証這一點，我們必須找尋此樹。如果找尋不成功，我們可以在找尋結束點插入此元素。」

5.7.4　從二元搜尋樹中刪除元素

5.7.5　二元搜尋樹的高度

5.8　選取樹 (selection trees)

假設我們有 $k$ 個有順序之序列，要將它們合併成一個有順序之序列。每一序列中包含數個記錄，並依一個特定欄位 key 升冪順序排列。每一個有順序之序列稱為一個行程（run）。令 $n$ 為 $k$ 個行程中所有的記錄之個數。

5.9　樹林 (forests)

5.9.1　將樹林轉換成二元搜尋樹

「假設有一樹林具有三個樹。要將此樹林轉換成單一的二元樹，我們首先要取得樹林中的每一個樹的二元樹表示法。而後，利用根節點的兄弟欄將所有的二元樹連接起來。」

5.9.2　樹林的尋訪

5.10　集合的表示法

本節我們將學習利用樹狀結構來表示集合。為簡化問題，我們假設集合中的元素為數值 $0, 1, 2, \ldots, n-1$。在實用上，這些數值可能是儲存元素實際名稱的符號表（symbol table）的索引。我們也假設所要表示的任意兩個集合是互斥的（disjoint）。

圖 5.42：集合 $S_1=\{0,6,7,8\}$、$S_2=\{1,4,9\}$、$S_3=\{2,3,5\}$ 的陣列表示法

加權法則與折疊法則

void union2(int i, int j)
{
/* union the sets with roots i and j, i != j, using
the weighting rule. parent[i] = -count[i] and
parent[j] = -count[j] */
   int temp = parent[i] + parent[j];
   if (parent[i] > parent[j]) {
      parent[i] = j; /* make j the new root */
      parent[j] = temp;
   }
   else {
      parent[j] = i; /*make i the new root */
      parent[i] = temp;
   }
}

程式 5.19：union 函數 —— 計數存在根節點的 parent 欄位裡（存成負數），所以不需要額外的 count 陣列

int find2(int i)
{
/* find the root of the tree containing element i. Use the
collapsing rule to collapse all nodes from i to root */
   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;
}

程式 5.20：find 函數 —— 第一個迴圈找根，第二個迴圈把路徑上所有節點直接掛到根下

公設 5.5 與 Ackermann 函數

當執行一連串的 union 和 find 時，union_find 演算法的最差行為在公設 5.5 中說明。在說明此公設之前，我們先介紹一個成長非常慢的函數 $\alpha(m,n)$ 的定義如下：

在此所用的 Ackermann 函數之定義為：

5.10.2　等價類別

5.11　計算二元樹之數目

5.11.4　不同的二元樹之數目

「要得知 $n$ 個節點所產生的不同的二元樹之數目，我們必須解出遞迴方程式 (5.3)。首先我們令：」

這是二元樹數目的衍生函數（generating function）

其次，藉觀察遞迴關係式可得到下列的等式：

利用解一元二次方程式的公式和 $B(0)=b_0=1$ 的事實（5.3 式），可得知：

我們可利用二項式定理來展開 $(1-4x)^{1/2}$，得到：

比較 (5.4) 式與 (5.5) 式，可發現 $b_n$ 是在 $B(x)$ 式中 $x^n$ 的係數，其值為 $\binom{1/2}{n+1}(-1)^n 2^{2n+1}$。化簡以後可得到：

其近似值為：

5.12　精選參考文獻

本章重點回顧