資料結構 第6章　樹狀結構

6-1 認識樹 樹 (tree) 是由一或多個節點 所組成的有限集合，其特質如下： 有一個特殊節點，稱為樹根 。 6-1　認識樹 樹 (tree) 是由一或多個節點 所組成的有限集合，其特質如下： 有一個特殊節點，稱為樹根 。 其餘節點可以分為n個互斥集合T1、T2、…、Tn (n ≥ 0)，而且每個集合也都是一棵樹 。

6-1-1 樹的相關名詞 分支度 (degree) 終端節點 (terminal node) 6-1-1　樹的相關名詞 分支度 (degree) 終端節點 (terminal node) 非終端節點 (nonterminal node) 階度 (level) 父節點 (parent) 子節點 (child) 兄弟 (sibling) 祖先 (ancestor) 子孫 (descendant) 高度 (height) 或深度 (depth) 樹林 (forest)

6-1-2　樹的表示方式 我們可以使用串列 表示樹，例如右圖 的樹可以表示成 (A(B(E, F(K)), C(G, H(L, M(N)), I), D(J))) 至於每個節點在記憶體的儲存方式，我們可以使用如下的結構 : data link1 link2 … linkn

6-2　二元樹 二元樹 (binary tree) 是每個節點最多有兩個子節點的樹，節點的左邊稱為左子樹 ，節點的右邊稱為右子樹 。

範例6.2：證明二元樹第i階的最多節點個數為2i-1，i ≥ 1。 解答： 當i = 1時，第1階最多只有樹根一個節點，故 2i-1 = 21-1 = 20 = 1成立。 假設當1 ≤ i < k時，第i階的最多節點個數為 2i-1成立，故第k - 1階的最多節點個數為2k-2。 證明當i = k時，第i階的最多節點個數為2i-1亦 成立。由於第k - 1階的最多節點個數為2k-2，而 二元樹的每個節點最多有兩個子節點，故第k階 的最多節點個數為2k-2 x 2 = 2k-1。

範例6.3：證明高度為h之二元樹的最多節點個數為2h - 1，h ≥ 1。 解答：由於二元樹第i階的最多節點個數為2i-1，因此，對高度為h的二元樹來說，全部存滿的話，總共有20 + 21 + … + 2h-1 = 2h - 1個節點。

6-2-1 完滿二元樹V.S. 完整二元樹 完滿二元樹 (full binary tree) 完整二元樹 (complete binary tree)

假設完整二元樹的節點個數為n且節點依照0 ~ n - 1的順序編號，則其任意節點i (0 ≤ i ≤ n - 1) 具有下列特質： 若i = 0，表示節點i為樹根，否則節點i的父節點為 (i - 1)/2 。 若2i + 1 ≥ n，表示節點i沒有左子節點，否則節點i的左子節點為2i + 1。 若2i + 2 ≥ n，表示節點i沒有右子節點，否則節點i的右子節點為2i + 2。

範例6.6：證明節點個數為n之完整二元樹的高度為 log2n + 1。

6-2-2 二元樹的表示方式 使用陣列實作二元樹 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 6-2-2　二元樹的表示方式 使用陣列實作二元樹 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] A B C D E -- F G H I

使用鏈結串列實作二元樹 typedef struct node{ struct node *lchild; char data; struct node *rchild; }tree_node; typedef tree_node *tree_pointer;

6-2-3　將一般樹轉換為二元樹 範例6.7：將下面的一般樹轉換為二元樹。

6-3 二元樹的走訪 6-3-1 中序走訪 inorder(tree_pointer root) { if (root){ 6-3　二元樹的走訪 6-3-1　中序走訪 inorder(tree_pointer root) { if (root){ inorder(root->lchild); printf("%d ", root->data); inorder(root->rchild); } 右圖的中序走訪的結果為DBGEHACFI。

6-3-2　前序走訪 preorder(tree_pointer root) { if (root){ printf("%d ", root->data); preorder(root->lchild); preorder(root->rchild); } 右圖的前序走訪的結果為ABDEGHCFI。

6-3-3　後序走訪 postorder(tree_pointer root) { if (root){ postorder(root->lchild); postorder(root->rchild); printf("%d", root->data); } 右圖的後序走訪的結果為DGHEBIFCA。

6-3-4　決定唯一的二元樹 範例6.11：[決定唯一的二元樹] 假設二元樹的中序與前序走訪分別為DBEACGFH、ABDECFGH，試據此推算出該二元樹。

6-4 二元樹的其它運算 6-4-1 複製二元樹 範例6.13：撰寫一個函數實作複製二元樹運算。 6-4　二元樹的其它運算 6-4-1　複製二元樹 範例6.13：撰寫一個函數實作複製二元樹運算。 tree_pointer copy(tree_pointer source) { tree_pointer destination; if (source){ destination = (tree_pointer)malloc(sizeof(tree_node)); destination->lchild = copy(source->lchild); destination->rchild = copy(source->rchild); destination->data = source->data; return destination; } return NULL;

6-4-2 比較二元樹 範例6.14：撰寫一個函數實作比較二元樹運算。 6-4-2　比較二元樹 範例6.14：撰寫一個函數實作比較二元樹運算。 int equal(tree_pointer source, tree_pointer destination) { if ((!source && !destination) || (source && destination && (source->data == destination->data) && equal(source->lchild, destination->lchild) && equal(source->rchild, destination->rchild)) return 1; else return 0; }

6-5 運算式樹 運算式樹 (expression tree) 指的是滿足下列條件的二元樹： 6-5　運算式樹 運算式樹 (expression tree) 指的是滿足下列條件的二元樹： 終端節點為運算元 (operand)，而非終端節點為運算子 (operator)。 子樹為子運算式且其樹根為運算子。

6-6　引線二元樹 引線二元樹 (threaded binary tree) 的左引線 (left thread) 指向節點本身的中序前行者 (inorder predecessor)，右引線 (left thread) 指向節點本身的中序後繼者 (inorder successor) 。

6-6-1 節點結構 #define THRAED 1 #define POINTER 0 typedef struct thnode{ 6-6-1　節點結構 #define THRAED 1 #define POINTER 0 typedef struct thnode{ int lthread; struct threaded_node *lchild; char data; struct threaded_node *rchild; int rthread; }threaded_node; typedef threaded_node *threaded_pointer; lthread lchild data rchild rthread

空的引線二元樹 (只有包含首節點) 加入首節點的引線二元樹

6-6-2 中序走訪 範例6.15：撰寫一個函數在引線二元樹中找出任意節點的中序後繼者。 6-6-2　中序走訪 範例6.15：撰寫一個函數在引線二元樹中找出任意節點的中序後繼者。 threaded_pointer inorder_successor(threaded_pointer ptr) { threaded_pointer tmp; tmp = ptr->rchild; if (tmp == POINTER) while(tmp->lchild == POINTER) tmp = tmp->lchild; return tmp; }

範例6.16：利用範例6.15所撰寫的inorder_successor() 函數完成引線二元樹的中序走訪。 threaded_inorder (threaded_pointer head) { threaded_pointer tmp; for(;;){ tmp = inorder_successor(tmp); if (tmp == head) break; printf("%d ", tmp->data); }

6-6-3　插入節點 情況一： 將新節點T插入節點S的右兒子且新節點T是樹葉

將新節點T插入節點S的右兒子且新節點T不是樹葉 threaded_pointer tmp; T->rthread = S->rthread; T->rchild = S->rchild; T->lthread = THREAD; T->lchild = S; S->rthread = POINTER; S-rchild = T; if (T->rthread == POINTER){ tmp = T->rchild; while(tmp->lchild == POINTER) tmp = tmp->lchild; tmp->lchild = T; } (1) (2) (3) (4)

情況二： 將新節點T插入節點S的左兒子且新節點T是樹葉

將新節點T插入節點S的左兒子且新節點T不是樹葉 T->lthread = S->lthread; T->lchild = S->lchild; T->rthread = THREAD; T->rchild = S; S->lthread = POINTER; S-lchild = T; if (T->lthread == POINTER){ tmp = T->lchild; while(tmp->rchild == POINTER) tmp = tmp->rchild; tmp->rchild = T; } (1) (2) (3) (4)

6-7 二元搜尋樹 二元搜尋樹是滿足下列條件的二元樹： 每個節點包含唯一的鍵值 (key)。 左右子樹亦為二元搜尋樹。 6-7　二元搜尋樹 二元搜尋樹是滿足下列條件的二元樹： 每個節點包含唯一的鍵值 (key)。 左右子樹亦為二元搜尋樹。 左子樹的鍵值必須小於其樹根的鍵值 右子樹的鍵值必須大於其樹根的鍵值。

6-7-1　搜尋節點 先和樹根做比較，若指定的鍵值小於樹根，就以同樣的方式搜尋樹根的左子樹，若指定的鍵值大於樹根，就以同樣的方式搜尋樹根的右子樹，左右子樹均據此定義遞迴地搜尋下去。 寫出在右圖的二元搜尋樹搜尋70和35兩個鍵值的過程。

範例6.20：以遞迴的方式撰寫一個函數在二元搜尋樹搜尋節點。 tree_pointer search2(tree_pointer root, int key) { if (!root) return NULL; if (key == root->data) return root; if (key < root->data) return search2(root->lchild, key); else return search2(root->rchild, key); }

6-7-2　插入節點 先和樹根做比較，若新節點小於樹根，就以同樣的方式移往樹根的左子樹，若新節點大於樹根，就以同樣的方式移往樹根的右子樹，直到抵達子樹的尾端，再將新節點加入子樹的尾端。

範例6.21：[建構二元搜尋樹] 將數字串列 (25, 30, 24, 58, 45, 26, 12, 14) 建構為二元搜尋樹。

假設將數字串列 (25, 30, 24, 58, 45, 26, 12, 14) 變更為 (25, 30, 24, 58, 45, 26, 14, 12)，後面兩個資料的順序交換，則建構出來的二元搜尋樹如下：

假設將數字串列 (25, 30, 24, 58, 45, 26, 12, 14) 變更為 (12, 14, 24, 25, 26, 30, 45, 58)，資料由小到大排序，則建構出來的二元搜尋樹如下：

6-7-3　刪除節點 情況一：當欲刪除的節點是樹葉時，直接刪除該節點即可。

情況二：當欲刪除的節點有一棵子樹時，將其父節點的指標改指向其子節點，然後刪除該節點即可。

情況三：當欲刪除的節點有兩棵子樹時，以該節點的左子樹中最大節點或右子樹中最小節點填入其位置，然後刪除該節點即可。

6-8　霍夫曼樹 範例6.23：[建構霍夫曼樹] 假設A、B、C、D、E、F等六個符號的出現頻率為0.2、0.15、0.3、0.18、0.05、0.12，試據此建構霍夫曼樹並寫出各個符號的編碼。

範例6.24：[霍夫曼碼解碼] 根據範例6.23所設計的霍夫曼碼，將111110010000110進行解碼。 解答：由於A、B、C、D、E、F等六個符號分別被編碼為01、110、10、00、1110、1111，故將111110010000110解碼後會得到FCADDB。

6-9 樹林 樹林 (forest) 是由n棵互斥樹所組成的集合 (n ≥ 0)，適合用來表示互斥集合 (disjoin set)。 6-9　樹林 樹林 (forest) 是由n棵互斥樹所組成的集合 (n ≥ 0)，適合用來表示互斥集合 (disjoin set)。 樹去掉樹根後就會得到樹林 樹

範例6.26：將下面的樹林轉換為二元樹。

6-10　集合 集合 (set) 是一群相同類型、沒有順序之分的元素，而互斥集合 (disjoin set) 是沒有相同元素的集合 。

互斥集合常見的運算有下列兩種： 聯集 (union) 搜尋 (find) (a) S1 U S2 (b) S2 U S1

使用陣列存放互斥集合，以下圖的S1、S2、S3等三個集合為例，陣列的內容如下， i 1 2 3 4 5 6 7 8 parent[i] -1

呼叫聯集運算函數建立S1、S2、S3等三個集合和S1∪S2集合： 互斥集合的聯集運算函數 set_union(int i, int j) { parent[i] = j; } 呼叫聯集運算函數建立S1、S2、S3等三個集合和S1∪S2集合： set_union(0, 2); set_union(1, 2); set_union(3, 4); set_union(5, 8); set_union(6, 8); set_union(7, 8); set_union(4, 2);

互斥集合的搜尋運算函數 int find(int i) { while(parent[i] > 0 i = parent[i]; return i; }