# Chap. 05 - Tree
> 課程內容 : 中興大學應用數學系 顏增昌教授 (111 學年度第 1 學期)
> 參考書目 : Fundamentals of Data Structures in C (2nd), Ellis H., Sartaj S., Susan A.-F.
>
>其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)
## Content
* [Sec. 5.1 Introduction](#Sec-51-Introduction)
* [1. Some terminology](#1-Some-terminology)
* [2. Representation](#2-Representation)
* [2.1 List Representation](#21-List-Representation)
* [2.2 LCRS representation](#22-LCRS-representation)
* [Sec. 5.2 Binary tree](#Sec-52-Binary-tree)
* [1. ADT of binary tree](#1-ADT-of-binary-tree)
* [2. Properties of binary tree](#2-Properties-of-binary-tree)
* [3. Representation of binary tree](#3-Representation-of-binary-tree)
* [3.1 Array representation](#31-Array-representation)
* [Sec. 5.2 Binary tree traversal](#Sec-52-Binary-tree-traversal)
* [1. Inorder traversal](#1-Inorder-traversal)
* [2. Preorder traversa](#2-Preorder-traversa)
* [3. Preorder traversal](#3-Preorder-traversal)
* [4. Inorder traversal for stack](#4-Inorder-traversal-for-stack)
* [5. Level-order traversal](#5-Level-order-traversal)
* [6. Implement of traversal](#6-Implement-of-traversal)
* [Sec. 5.4 More binary tree operation](#Sec-54-More-binary-tree-operation)
* [1. Copy](#1-Copy)
* [2. Equality](#2-Equality)
* [3. Satisfiability problem (暫略)](3-Satisfiability-problem-暫略)
* [4. Implement of other operation](#4-Implement-of-other-operation)
* [Sec. 5.5 Threaded binary tree](#Sec-55-Threaded-binary-tree)
* [1. Representation of threaded binary tree](#1-Representation-of-threaded-binary-tree)
* [2. Traversal of thread binary tree](#2-Traversal-of-thread-binary-tree)
* [3. Insertion of thread binary tree (暫略)](#3-Insertion-of-thread-binary-tree-暫略)
* [Sec. 5.6 Heap](#Sec-56-Heap)
* [1. Priority queue](#1-Priority-queue)
* [2. Maximum heap](#2-Maximum-heap)
* [3. Push](#3-Push)
* [4. Pop](#4-Pop)
* [5. Implement of max heap](#5-Implement-of-max-heap)
* [Sec. 5.7 Binary search tree](#Sec-57-Binary-search-tree)
* [1. Search](#1-Search)
* [2. Add](#2-Add)
* [3. Delete](#3-Delete)
* [4. Implement of binary search tree](#4-Implement-of-binary-search-tree)
## Sec. 5.1 Introduction
> **Definition**
> 樹是由 1 或多個節點(node)所組成的有限(finite)集合
> * 存在一個特殊節點，稱為根節點(root)
> * 其餘節點可以分割成 $n \ge 0$ 個互斥(disjoint)的集合，且每個集合都是一個樹，稱為子樹(subtree)
:::info
「樹」指的是將資料以階層性組織的形式表示，是一種遞回(recursive)結構
:::
### 1. Some terminology
| 名詞 | 解釋 | 其他 |
| :-: |:-: |:-: |
| Node(節點) | 儲存資訊或連結到其他節點的分支(branch) |
| Degree(分支度) | 節點的子數(或分支)數量 |
| Degree of tree(最大分支度) | 所有節點的 degree 的最大值 |
| Leaf(樹葉) | Degree = 0 的節點 | 也可稱為終端節點(terminal) |
| Non-terminal node(非終端節點) | Degree != 0 的節點 |
| Children(孩子) | 節點的子數的根節點 | Ex: 節點 X 的子樹的樹根，稱為 X 的 child，又稱為子節點 |
| Parent(父親) | 承上，節點 X 稱為 parent | 父節點 |
| Siblings(兄弟) | 具有相同 parent 的節點 |
| Ancestor(祖先) | 節點往上回推到 root 所經過的所有節點 |
| Level(階層) | 由 root 所在位置設為 level 1，則他的子節點的 level 為 2，以此推類 | 有時 root 所在位置稱為 level 0 |
| Height/Depth(高度/深度) | Level 的最大值 |
如上圖所示做舉例
1. _____ is the root node ? <font color="ff0000"> A </font>
2. _____ is the parent of E and F ? <font color="ff0000"> B </font>
3. _____ is the siblings of B ? <font color="ff0000"> C, D</font>
5. E and F are the _____ of B ? <font color="ff0000"> Children </font>
6. F, G, I, J, K, M are _____ ? <font color="ff0000"> Leaf </font>
7. A, B, C, H are _____ nodes ? <font color="ff0000"> Non-terminal </font>
8. The level of E is _____ ? <font color="ff0000"> 2 or 3 </font>
9. The height(depth) of the tree is _____ ? <font color="ff0000"> 3 or 4 </font>
10. The degree of node B is _____ ? <font color="ff0000"> 2 </font>
11. The degree of the tree is _____ ? <font color="ff0000"> 3 </font>
12. The ancestor of node M is _____ ? <font color="ff0000"> H, D, A </font>
13. The descendants of node D is _____ ? <font color="ff0000"> H, I, J, M </font>
### 2. Representation
#### 2.1 List Representation
樹狀結構可以使用串列(list)的方式來呈現，原則如下
$$
\text{parent}(\text{children_1, children_2, ...})
$$
以上圖的數節結構舉例，串列表示法如下
$$
(A(B(E(K, L), F), C(G), D(H(M), I, J)))
$$
#### 2.2 LCRS representation
另一種樹狀結構的表示法稱為左子右兄表示法(**L**eft-**C**hildren-**R**ight-**S**iblings, LCRS)，使用這種表示法的原因如下
* 對於任意的 node 而言，只會有一個最左邊的 children，且每個 children 只會有一個鄰近右邊的 sibling
* 對於任意的 node 而言，它的 children 的順序不重要
因此可以把每個 node 的 sub-tree 分成 left children 與 right sibling。
要將一個樹狀結構以 LCRS 的表示法呈現
* 每個 node 的左邊指向最左側的 children
* 每個 node 的右邊指向 sibling
此外，如果將 LCRS 表示法順時針旋轉 45 度，即可變成一個二元樹(binary tree)。二元樹指的是樹的 degree = 2 的表示法
* 看到 children 就往左畫
* 看到 sibling 就往右畫
透過上述方式可以將所有的樹轉換成二元樹。
## Sec. 5.2 Binary tree
> **Definition**
> A binary tree is a finite set of node that is either empty or consists of a root and two disjoint binary trees called the left subtree and the right subtree
換句話說，二元樹也可以是空的沒有任何節點，這點與一般的樹不太一樣。此外，所有的樹狀結構都可以使用 LCRS 表示法轉換為 binary tree。
### 1. ADT of binary tree
在 binary tree 中還有兩種不同的特別結構，skewed tree(歪斜樹，下圖 a)與 complete binary tree(完整二元樹，下圖 b)
### 2. Properties of binary tree
在探討二元樹的表示法前，需先觀察二元樹中節點數量的計算與節點之間的關係。
在 binary tree 中，節點數量有以下兩種性質(證明省略)
> * Binary tree 中，第 $n \ge 1$ 層的節點數最多有 $2^{n-1}$ 個
> * 深度為 $k \ge 1$ 的 binary tree 中，節點數最多有 $2^{k-1}$ 個
此外，葉節點(leaf)與分支度(degree)為 2 的節點也有以下關係(證明省略)
> * 對於所有非空的 binary tree T，如果 $n_0$ 是葉節點(leaf)的數量且 $n_2$ 為分支度(degree)為 2 的節點數量，則 $n_0 = n_2 + 1$
有了上述性質後，可衍生完全二元樹(full binary tree)的定義
> 一個深度(depth)為 k 的 full binary tree 有以下性質
> * 是一個深度(depth)為 k 的 binary tree
> * 具有 $2^{k-1}$ 個節點
如下圖所示為一個 full binary tree
將 full binary tree 從根節點(root)開始對所有節點編號，這些編號可以輔助定義一個完整二元樹(complete binary tree)。
> 一個深度(depth)為 k 的 binary tree 是一個 binary tree，若且唯若它的節點與深度(depth)為 k 的 full binary tree 編號一致。
如上圖所示，左邊是一個深度(depth)為 3 的完全二元樹(fully binary tree)並對節點紀錄編號，右邊是一個深度(depth)為 3 的完整二元樹(complete binary tree)。
此外，一個具有 n 個節點的 complete binary tree，他的高度為 $=\log_2(n+1)$
### 3. Representation of binary tree
#### 3.1 Array representation
根據上述對 binary tree 的編號方式，可以使用這些編號作為 index，並以 array 來表示一個 binary tree。使用 array 表示 binary tree 時，inedx = 0 的位置閒置不用，從 index = 1 開始計算。編號 i 的節點所在位置是 index = i。
以 array 來表示 binary tree 時，對於一個 index = i 的節點可用以下函數計算它的父節點與子節點的相對位置。
> If a complete tree with $n$ nodes is represented sequentially, then for any node with index $i$ where $1 \le i \le n$, we have
> * $Parent(i)$ is at $\lfloor \cfrac{i}{2} \rfloor$.
> * But if $i = 1$, then it has no parent (since it is root)
> * $LeftChild(i)$ is at $2i$ if $2i \le n$.
> * If $2i \ge n$, then it has no left child.
> * $RightChild(i)$ is at $2i + 1$ if $2i+1 \le n$.
> * If $2i + 1 \ge n$, then it has no left child.
如上圖所示，以 array 可以表示 binary tree 的所有節點。以編號 3 的節點 C 為例 :
* 節點 C 的父節點編號為 $Parent(3) = \lfloor \cfrac{3}{2} \rfloor = 1$，節點 A
* 節點 C 的左子節點編號為 $LeftChild(3) = 2 \cdot 3 = 6$，節點 D
* 節點 C 的右子節點編號為 $RightChild(3) = 2 \cdot 3 + 1 = 7$，節點 E
雖然 array 可以表示一個二元樹的節點相對位置，但缺點也如上圖所示
* 如果不是 fully binary tree 的話會造成空間上的浪費
* 新增或刪除節點時會造成過度的複製與移動
#### 3.2 Linked representation
另一種方式可以使用鏈結(link)的方式來表示一個樹，這種方式可以改善 array 所帶來的缺點。如上右圖所示，一個節點左邊會指向他的左子節點，右邊指向他的右子節點，可以使用兩個 linked 欄位的資料結構來呈現一個節點。完整的 linked 二元樹表示法如下
'
> The following code is saved in `TreeADT.h`.
```c=
typedef struct node *treePointer;
struct node {
treePointer leftChild;
int data;
treePointer rightChild;
};
```
## Sec. 5.3 Binary tree traversal
樹的走訪(traversal)指的是拜訪(visit)樹的每個節點，拜訪節點時在針對節點的值做某些運算。由於在二元樹中每個節點只會以兩個子節點，所以在樹中移動的方向可以分為三種方式：往左移動(L)、往右移動\(R)與拜訪節點(V)。三種方向經過排列組合後總共有 $3! = 6$ 種不同路徑(LRV、RLV，...等)。
但考量到節點的排列與編號順序是由左往右，依照拜訪的位置不同經過縮減後有三種走訪方式：中序走訪(LVR)、後序走訪(LRV)與前序走訪(VLR)
:::info
不論是哪種走訪路線，每當往左(L)或往右\(R)移動到下一層節點時，就將該節點視為父節點並再次做遞迴般的走訪，直到該節點的子樹都做完才重回上一層父節點
:::
### 1. Inorder traversal
中序走訪(LVR)會依照以下順序對整顆樹進行 traversal
* 往左子節點移動直到不能移動(NULL)為止
* 印出該節點(即 NULL 前一層)的資料
* 移動到該節點的右子節點重複第一步
以上圖為例進行 LVR traversal，過程如下：
* 從根節點(+)開始往左移動，直到節點 A 的左側為 NULL 不能再繼續 **(L)**
* 打印節點 A 的資料 **(V)**
* 移動到節點 A 的右子節點作為根節點，重回第一步 **\(R)**
* 節點為 NULL，停止移動 **(L)**
* 節點 A 處理完成，往上處理節點 /
* 節點 / 的左子節點已經完成不能再移動 **(L)**
* 打印節點 / **(V)**
* 移動到節點 / 的右子節點 B 繼續進行第一步 **\(R)**
依照上步驟，上圖的二元樹經過 inorder traversal 後的節點順序為：
$$
A\ /\ B\ *\ C\ *\ D\ +\ E
$$
> The following code is saved in `traversal.c`.
```c=
void InOrder(treePointer ptr){
if (ptr){
InOrder(ptr -> leftChild);
printf("%d ", ptr -> data);
InOrder(ptr -> rightChild);
}
}
```
### 2. Preorder traversal
前序走訪(VLR)會依照以下順序對整顆樹進行 traversal
* 印出(父)節點資料
* 往左移動到左子節點並視為父節點，印出後繼續往左直到不能動(NULL)為止
* 往右子節點移動並視為父節點
* 再往右移動到右子節點並重複第一步
以下圖為例進行 VLR 的 preorder traversal，過程如下：
* 印出父節點 / 的資料 **(V)**
* 往左移動到左子節點 A 並視為父節點 **(L)**
* 打印父節點 A 資料 **(V)**
* 往左移動到左子節點 NULL 後不能移動 **(L)**
* 往右移動到右子節點 NULL 也不能動，至此節點 A 完成 **\(R)**
* 重回上層父節點 / 後再往右移動到右子節點 B 並視為父節點重回第一步 **\(R)**
* 打印父節點 B 的資料 **(V)**
* 往左移動到子節點 NULL 後不能移動 **(L)**
* 往右移動到右子節點 NULL 也不能動，至此節點 B 完成 **\(R)**
* 重回上一層父節點 /，至此節點 / 完成
依照 preorder traversal 的路徑，下圖的二元樹拜訪節點順序為
$$
+\ *\ *\ /\ A\ B\ C\ D\ E
$$
> The following code is saved in `traversal.c`.
```c=
void PreOrder(treePointer ptr){
if (ptr){
printf("%d ", ptr -> data);
PreOrder(ptr -> leftChild);
PreOrder(ptr -> rightChild);
}
}
```
### 3. Preorder traversal
後序走訪(LRV)會依照以下順序對整顆樹進行 traversal
* 往左子節點移動直到不能移動(NULL)為止
* 往該節點(即 NULL 前一層)的右子節點移動到不能移動(NULL)為止
* 打印該節點(即 NULL 前一層)的資料
以下圖為例進行 LRV 的 postorder traversal，過程如下：
* 往父節點 / 的左子節 A 點移動並視為新的父節點 **(L)**
* 往父節點 A 的左子節點 NULL 移動並停止 **(L)**
* 再往父節點 A 的右子節點 NULL 移動並停止 **\(R)**
* 兩側移動完，印出父節點 A 的資料，至此節點 A 完成 **(V)**
* 重回上一層父節點 / 並往右節點 B 移動後視為新的父節點 **\(R)**
* 往父節點 B 的左子節點 NULL 移動並停止 **(L)**
* 再往父節點 B 的右子節點 NULL 移動並停止 **\(R)**
* 兩側移動完，印出父節點 B 的資料，至此節點 B 完成 **(B)**
* 重回上一層父節點 / 後因為兩側移動完，印出父節點 / 的資料 **(V)**
依照 preorder traversal 的路徑，下圖的二元樹拜訪節點順序為
$$
A\ B\ /\ C\ *\ D\ *\ E\ +
$$
> The following code is saved in `traversal.c`.
```c=
void PostOrder(treePointer ptr){
if (ptr){
PostOrder(ptr -> leftChild);
PostOrder(ptr -> rightChild);
printf("%d ", ptr -> data);
}
}
```
### 4. Inorder traversal for stack
以 stack 的方式模擬 traversal 時，可以避免遞迴式的走訪路徑。每當往下移動一層節點並重新開始做 traversal 時，就將該節點進行 push 操作。當要拜訪印出該節點時，就進行 pop 操作。
以 inorder traversal 為例，每當往左(L)移動到子節點並重新開始 LVR 時，就將該子節點 push 到 stack 之中。要拜訪要出節點資料時就將該節點從 stack 中 pop 取出。
> The following code is saved in `traversal.c`.
```c=
void IterInorder(treePointer ptr){
int top = -1;
treePointer node;
treePointer stack[MAX_STACK_SIZE];
for (;;){
for (; ptr; ptr = ptr -> leftChild){
push(&top, ptr, stack);
}
ptr = pop(&top, stack);
if (!ptr) break;
printf("%d ", ptr -> data);
ptr = ptr -> rightChild;
}
}
void push(int *top, treePointer node, treePointer stack[]){
if (*top == MAX_STACK_SIZE-1)
fprintf(stderr, "The stack is FULL.\n");
else
stack[++(*top)] = node;
}
treePointer pop(int *top, treePointer stack[]){
if (*top == -1){
fprintf(stderr, "The stack is EMPTY.\n");
return NULL;
}
else
return stack[(*top)--];
}
```
### 5. Level-order traversal
以 queue 的方式進行 traversal 稱為階序走訪(level-order traversal)。階序走訪會依照節點的編號順序來歷遍整顆樹，會先拜訪父節點，再來是左子節點與右子節點，每一層都會由最左邊拜訪到最右邊。
依照 level-order traversal 的走訪方式，下圖的節點拜訪順序為
$$
+\ *\ E\ *\ D\ /\ C\ A\ B
$$
參考環狀佇列的方式，階序走訪的步驟與實作具體如下
* 加入根節點 root
* 打印節點時使用從 front 端刪除節點
* 往下層移動節點時從 rear 端加入節點
<!-- 程式碼
> The following code is saved in
```c=
```
-->
### 6. Implement of traversal
實作前包含了最基本的 binary tree 的建構以及記憶體空間的釋放，其中每個節點的釋放採用 postorder traversal 的方式歷遍每個節點。
> The following code is saved in `basic.c`.
```c=
/* basic.c */
#include <stdio.h>
#include <stdlib.h>
#include "TreeADT.h"
/** an example tree
* A(1)
* / \
* B(2) C(3)
* / \
* D(4) E(5)
*/
treePointer exampleTree(){
treePointer a, b, c, d, e;
MALLOC(a, sizeof(*a));
MALLOC(b, sizeof(*b));
MALLOC(c, sizeof(*c));
MALLOC(d, sizeof(*d));
MALLOC(e, sizeof(*e));
// node A
a -> data = 1;
a -> leftChild = b;
a -> rightChild = c;
// node B
b -> data = 2;
b -> leftChild = d;
b -> rightChild = e;
// node C
c -> data = 3;
c -> leftChild = NULL;
c -> rightChild = NULL;
//node D
d -> data = 4;
d -> leftChild = NULL;
d -> rightChild = NULL;
//node E
e -> data = 5;
e -> leftChild = NULL;
e -> rightChild = NULL;
return a;
}
void FreeTree(treePointer ptr){
// use postorder traversal to relase
if (ptr){
FreeTree(ptr -> leftChild);
FreeTree(ptr -> rightChild);
free(ptr);
}
}
```
以下為所有 traversal 方法的應用(不包含 level-order traversal 的走訪方式)
> The following code is saved in `traversal-implement.c`.
```c=
#include <stdio.h>
#include <stdlib.h>
#include "TreeADT.h"
int main(void){
treePointer root;
root = exampleTree();
// inorder: 4 2 5 1 3
printf("Inorder traversal: ");
InOrder(root);
printf("\n");
// preorder: 1 2 4 5 3
printf("Preorder traversal: ");
PreOrder(root);
printf("\n");
// Postorder: 4 5 2 3 1
printf("Postorder traversal: ");
PostOrder(root);
printf("\n");
// IterInorder: 4 2 5 1 3
printf("IterInorder traversal: ");
IterInorder(root);
FreeTree(root);
return 0;
}
```
## Sec. 5.4 More binary tree operation
### 1. Copy
參考 postorder traversal 的方式可以複製一顆樹的所有節點資料，過程如下，並以資料複製來代替實際 traversal 中存取節點資料
* (L) 不斷往左直到 NULL
* \(R) 轉到右子節點直到 NULL
* (V) 複製資料後重回第一步
> The following code is saved in `OtherOperation.c`.
```c=
treePointer treeCopy(treePointer ori){
treePointer temp;
if (ori){ // original tree is not empty
MALLOC(temp, sizeof(struct node));
temp->leftChild = treeCopy(ori->leftChild);
temp->rightChild = treeCopy(ori->rightChild);
temp->data = ori->data;
return temp;
}
return NULL;
}
```
### 2. Equality
當兩顆樹有相同的節點與分支，且每個節點具有相同資訊，則可以說兩個樹是相同的。可以使用修改過的 preorder traversal 實作測試兩顆樹是否相等。
在判斷時兩棵樹的結構時要注意以下幾點：
1. 先檢查兩棵樹狀態是否一樣(`!first && !second`)
* 同時非空或同時空
2. 兩棵樹都非空且節點資料相同(`first && second && (first->data && second->data)`)
3. 遞迴判斷左子樹
4. 遞迴判斷右子樹
> The following code is saved in `OtherOperation.c`.
```c=
int treeEqual(treePointer first, treePointer second){
return ((!first && !second) ||
(first && second && (first->data == second->data)) &&
treeEqual(first->leftChild, second->leftChild) &&
treeEqual(first->rightChild, second->rightChild));
}
```
### 3. Satisfiability problem (暫略)
:::info
僅描述滿足性問題為何，省略他的樹狀結構表示與解法
:::
滿足性問題(Satisfiability problem)指的是給定一組邏輯運算式，能否找到一組解使得這個運算式的結果為真。
$$
(x_1 \land \neg x_2) \lor (\neg x_1 \land x_3) \lor \neg x_3
$$
以上述的邏輯運算式為例，能否找到一組 $(x_1, x_2, x_3)$ 使得結果為 True
### 4. Implement of other operation
> The following code is saved in `OtherOperation-implement.c`.
```c=
#include <stdio.h>
#include <stdlib.h>
#include "TreeADT.h"
int main(void){
treePointer treeA, treeB;
treeA = exampleTree();
printf("treeA: "); // treeA: 4 2 5 1 3
PrintTree(treeA);
printf("\n");
treeB = treeCopy(treeA);
printf("treeB: "); // treeB: 4 2 5 1 3
PrintTree(treeB);
printf("\n");
if (treeEqual(treeA, treeB))
printf("The two trees are equal.\n");
else
printf("The two trees are NOT equal.\n");
FreeTree(treeA);
FreeTree(treeB);
return 0;
}
```
> 註：`PrintTree()` 函式使用 inorder traversal 的方式印出節點資料
## Sec. 5.5 Threaded binary tree
二元樹表示法中，有一個缺點是具有太多的空節點，這些空節點在指標中都會指向 `NULL`。如下圖所示，具有 9 個空的鏈結(H, I, E, F, G)。
改善方式可以將這些空的鏈結指向其他的節點，稱為 threaded binary tree(引線二元樹)。以節點 node 為例：
* 若 node 的左子樹為空(`node->leftChild == NULL`)
* 指向中序表示法中 node 的前一個節點
* 即使用 node 的中序表示法中的前一個節點取代鏈結
* 若 node 的右子樹為空(`node->rightChild == NULL`)
* 指向中序表示法中 node 的後一個節點
* 即使用 node 的中序表示法中的後一個節點取代鏈結
以上圖的二元樹為例，中序表示法(LVR)為
$$
H\ D\ I\ B\ E\ A\ F\ C\ G
$$
節點 I 中
* (下圖紅虛線)左子樹為空，所以指向中序表示法的前一個節點 D
* (下圖藍虛線)右子樹為空，所以指向中序表示法的後一個節點 B
:::info
引線(thread)欄位的用意是來判斷該節點在中序表示法中有無前項或後項。
:::
### 1. Representation of threaded binary tree
因為 threaded binary tree 的表示法在空節點的位置新增了指向其他節點的鏈結，所以表示在結構體上也必須做出相應的改變。
中間三個欄位與普通的二元樹表示法一樣，左右兩個新增欄位 leftThreaded 與 rightThreaded 分別表示該節點是否有左或右引線。有引線 $\rightarrow$ 欄位值為 True $\rightarrow$ 該節點沒有左/右子樹。
```c=
typedef struct threadTree *threadedPointer;
struct threadTree {
shotrint leftThread;
threadedPointer leftChild;
int data;
threadedPointer rightChild;
shortint rightThread;
};
```
此外，從上圖可以看到，某些節點在中序表示法中可能不存在前項或後項(例如：節點 H)。為了統一表示方式與指向，所以為每顆樹設置一個標頭(header)節點，原來的根節點設為 header 的左子樹。thread 沒東西指向時(例如節點 H 與 G)就指向 header。
### 2. Traversal of thread binary tree
利用 thread 的概念，可以做到不用 stack 的 inorder traversal。對於任意一個節點 node：
* 如果 `node->rightThread == True` 表示具有右引線
* 根據 thread 的定義，表示節點 node 的中序表示法具有後項節點(`node->rightChild`)
* 換句話說，節點 node 沒有右子樹
* 如果 `node->rightThread == False` 表示不具有右引線
* 根據 thread 的定義，表示節點 node 的中序表示法沒有後項節點
* 換句話說，節點 node 具有右子樹，需要繼續執行下一層的 LVR
以下程式碼用來尋找某節點(`ptr`)的後項節點
* 如果有右引線(rightThread)，則該節點指向的右節點就是後項節點，直截回傳
* 如果沒有右引線(`if (!ptr->rightThread)`)，表示具有右子樹
* 跳到下層右子樹(`temp`)檢查有無左引線(`temp->leftThread`)
* 沒有左引線，表示有左子樹，則繼續做 LVR 中的 L 搜尋
* 有左引線，表示沒有左子樹，回傳
```c=
threadedPointer insucc(threadedPointer ptr){
threadedPointer temp;
temp = ptr->rightChild;
if (!ptr->rightThread)
while (!temp->leftThread)
temp = temp->leftChild;
return temp;
}
```
以上述尋找後項的方法可以做到 inorder traversal
```c=
void threadInorder(threadedPointer tree){
threadedPointer temp = tree;
for (;;){
temp = insucc(temp);
if (temp = tree) // 後項節點 = 根節點
break;
printf("%d ", temp->data); // 印出後項節點
}
}
```
### 3. Insertion of thread binary tree (暫略)
## Sec. 5.6 Heap
### 1. Priority queue
堆積(heap)常用來表示一個優先佇列(priority queue, PQ)。優先佇列與一般佇列的差別在於
* 欲刪除的元素是具有最高/最低優先權的元素
* 可插入任意優先權的元素
優先佇列的表示法可以使用一個沒有排序過的線性串列(list)表示，以循序(sequential)表示法或鏈結(linked)表示法都可以。
優先佇列的 ADT 的時間複雜度如下：
* `isEmpty()`：判斷優先佇列是否為空，時間複雜度 $O(1)$
* `top()`：取出優先佇列中的最大值，時間複雜度 $\Theta(n)$
* `push()`：加入元素到優先佇列，時間複雜度 $O(1)$
* `pop()`：從優先佇列中刪除最大/小優先權元素，時間複雜度 $\Theta(n)$
### 2. Maximum heap
> **Definition**
> 最大樹(maximum tree)：每個節點的值都必須不小於它的子節點
> 最小樹(minimum tree)：每個節點的值都必須不大於它的子節點
> 最大堆積(maximum heap)：一個 completed binary tree 且是 max tree
> 最小堆積(minimum heap)：一個 completed binary tree 且是 min tree
如下圖所示為三個最大堆積，每個節點的值都必須 $\ge$ 它的(所有)子節點。根據定義可以推斷最大堆積的根節點必為整個樹的最大值。
如下圖所示為三個最小堆積，每個節點的值都必須 $\le$ 它的(所有)子節點。根據定義可以推斷最小堆積的根節點必為整個樹的最小值。
最大/最小堆積排列方式與優先佇列類類似，所以這裡使用樹的[陣列表示法](#31-Array-representation)來表示最大/最小堆積
:::info
後面的運算都以最大堆積(max heap)為例
:::
先定義堆積中的元素的結構(也可以不用)
> The following code is saved in `HeapADT.h`.
```c=
#define MAX_ELEMENT 15
#define HEAP_FULL(n) (n == MAX_ELEMENT - 1)
#define HEAP_EMPTY(n) (!n)
// struct of heap element
typedef struct
{
int key;
} element;
```
此處定義一個函式並以動態配置記憶體的方式產生一個固定的最大堆積。
> The following code is saved in `HeapOperation.c`.
```c=
/** an example max heap
* 82
* / \
* 49 44
* / \ / \
* 16 31 7 6
* / \
* 5 2
*
*/
element *exampleMaxHeap(){
element *MaxHeap = (element *) malloc(MAX_ELEMENT * sizeof(element));
if (!MaxHeap){
fprintf(stderr, "Memory Insufficient.\n");
exit(EXIT_FAILURE);
}
MaxHeap[0].key = 0;
MaxHeap[1].key = 82;
MaxHeap[2].key = 49;
MaxHeap[3].key = 44;
MaxHeap[4].key = 16;
MaxHeap[5].key = 31;
MaxHeap[6].key = 7;
MaxHeap[7].key = 6;
MaxHeap[8].key = 5;
MaxHeap[9].key = 2;
return MaxHeap;
}
```
:::warning
二元樹的陣列表示法中，為了方便計算父節點與子節點的編號，所以根節點會放在 index = 1 的位置，index = 0 的位置通常會放置 0 或 -1。
:::
### 3. Push
將元素加到最大堆積中，需要使用一種類似氣泡上升(bubbling up)的過程。將新增的元素放到 max heap 的末端(編號最尾端)，並依序跟它的父節點做比較：
* 若大於父節點的值，則交換往上升
* 若小於父節點的值，則位置不變，形成 max heap
簡單來說就是每插入一個元素，都要重新調整樹的結構，使其再度形成 max heap 的形式。實作上的重點是要找到該節點的父節點位置，有了父節點位置才可以取值做比較。也因為 heap 的表示法是使用 array 表示，所以可以通過計算來找到父節點/子節點位置，見 [3.1 Array representation](#31-Array-representation)。
> The following code is saved in `HeapOperation.c`.
```c=
void push(element *heap, element item, int *n){
int i;
if (HEAP_FULL(*n)){
fprintf(stderr, "The heap is FULL.\n");
exit(EXIT_FAILURE);
}
i = ++(*n); // index of new element
// bubbling up
while ((i != 1) && (item.key > heap[i / 2].key)){
heap[i] = heap[i / 2]; // parent down
i = i / 2; // new node up
}
heap[i] = item;
}
```
在排序的過程中，新添加的元素必須由下往上逐層做比較，所以 `while` 迴圈迭代的次數等於樹的高度(height)，時間複雜度為 $O(\log n)$，其中 n 為樹的節點數量。
### 4. Pop
將最大堆積的元素刪除，就是刪除具有最大優先權(最大值)的元素，也就是刪除根節點。與新增過程類似，刪除根節點後的樹就不是最大堆積的形式，必須再把樹經過調整。實作上會使用最末端的元素來重新調整整個樹的順序，將末端元素放到最上層後再慢慢往下沉(trickle down)
* 刪除根節點
* 找到末端元素放到根節點位置
* 不斷比較，將新的根節點往下沉
* 先比較左右子節點，找較大的子節點
* 較大的子節點再跟父節點比較
> The following code is saved in `HeapOperation.c`.
```c=
element pop(element *heap, 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]; // the root element
temp = heap[(*n)--]; // take the last element and minor 1
parent = 1;
child = 2;
while (child <= *n){
// compare the value of two children
if ((child < *n) && heap[child].key < heap[child+1].key)
child++;
// correct index for the last element
if (temp.key > heap[child].key)
break;
heap[parent] = heap[child]; // bubbling up
parent = child; // scan next level
child = parent * 2; // scan next level
}
heap[parent] = temp;
return item;
}
```
在排序的過程中，放到根節點的末端元素必須由上往下逐層做比較，所以 `while` 迴圈迭代的次數等於樹的高度(height)，時間複雜度為 $O(\log n)$，其中 n 為樹的節點數量。
### 5. Implement of max heap
> The following code is saved in `HeapOperation.c`.
```c=
void printHeap(element *heap, int n){
printf("length of tree = %d\n", n);
for (int i=1; i<=n; i++)
printf("Heap[%d] = %d\n", i, (heap+i)->key);
}
```
> The following code is saved in `Heap-implement.c`.
```c=
#include <stdio.h>
#include <stdlib.h>
#include "HeapADT.h"
int main(void){
element *MaxHeap = exampleMaxHeap(); // length = 9
element item1 = {7}, item2 = {50}, item3;
int n = 9;
printHeap(MaxHeap, n);
printf("--- Push: heap[%d] = %d ---\n", n+1, item1.key);
push(MaxHeap, item1, &n);
printHeap(MaxHeap, n);
printf("--- Push: heap[%d] = %d ---\n", n+1, item2.key);
push(MaxHeap, item2, &n);
printHeap(MaxHeap, n);
printf("--- Pop: heap[1] = %d ---\n",MaxHeap[1].key);
item3 = pop(MaxHeap, &n);
printHeap(MaxHeap, n);
free(MaxHeap);
return 0;
}
```
## Sec. 5.7 Binary search tree
字典(dictornary)是資料對(data pair)的集合，每個資料對(key,item)都包含了一個鍵值(key)與它的項目(item)
一般來說字典可以有相同的 key 值，但此處假設所有 key 都是唯一的。
> **Definition** Binary search tree
> A binary tree is call binary search tree if it satisfy the following statement
> * Each element have a unique key
> * Key of left sub-tree are less than key of root
> * Key of right sub-tree are greater than key of root
> * The left and right sub-tree are binary search tree also
(假設節點的資料欄位是 `element` 型態)
> The following code is save in `BST.h`.
```c=
typedef struct node *treePointer;
typedef struct{
int key;
char ch;
} element;
struct node{
treePointer leftChild;
element data;
treePointer rightChild;
};
```
:::info
事實上 binary search tree 中的節點資料不一定要使用字典對的形式，如果資料本身是可以做排序的(Ex: 整數)也可以直接將資料排序取代定義中的 key 值
:::
### 1. Search
二元樹的搜索其實就是在尋找 key = k 的節點資料：
* `root = NULL`：回傳 `False`
* `root.key > k`：往較小的左子節點繼續搜尋
* `root.key < k`：往較大的右子節點繼續搜尋
從上述的尋找方式中可以看出 search 的過程中是其實就是做一顆樹的遞迴運算
> The following code is saved in `BSToperation.c`.
```c=
element *search(treePointer root, int key){
/* recursion ver. */
if (!root) return NULL;
if (key == root->data.key) return &root->data;
if (key < root->data.key)
return search(root->leftChild, key);
else
return search(root->rightChild, key);
}
```
除了使用遞迴外，也可以使用不斷迭代的方式來做二元樹的搜索
> The following code is saved in `BSToperation.c`.
```c=
element *iterSearch(treePointer tree, int key){
/* iteration ver. */
while (tree){
if (key == tree->data.key) return &tree->data;
if (key > tree->data.key)
tree = tree->rightChild;
else
tree = tree->leftChild;
}
return NULL;
}
```
### 2. Add
要新增 dictionary pair 到 binary search tree 中時，需先檢查樹的內部有沒有這個 dictionary pair，也就是檢查有沒有相同的鍵值。所以必須先做 search
* 存在：沒事
* 不存在：找適合的位置插入
> The following code is saved in `BSToperation.c`.
```c=
void insert(treePointer *ptr, int k, char ch){
treePointer node, lastNode = modifiedSearch(*ptr, k);
if (lastNode){
MALLOC(node, sizeof(struct node));
node->data.ch = ch;
node->data.key = k;
node->leftChild = node->rightChild = NULL;
if (*ptr){
if (k < lastNode->data.key)
lastNode->leftChild = node;
else
lastNode->rightChild = node;
}
else
*ptr = node;
}
else
printf("key exist.\n");
}
```
:::info
需要注意的是，因為當傳入值是一個空樹(`ptr` 指向 `NULL`)時，新加入了的節點就是這棵樹的根節點。所以必須去修改 `ptr` 指向的位址。因此傳入值是使用雙重指標(`*ptr`)
:::
上述程式碼中，函式 `modifiedSearch()` 是修改過的 `iterSearch()` 函式，它會去搜索 binary search tree 中有沒有對應的 key
* key 存在，回傳 `NULL`
* key 不存在，回傳搜索到的最後一個節點
> The following code is saved in `BSToperation.c`.
```c=
treePointer modifiedSearch(treePointer node, int key){
for(;;){
if (key == node->data.key) return NULL;
if (key > node->data.key){
if (!(node->rightChild))
return node;
else
node = node->rightChild;
}
else{
if (!(node->leftChild))
return node;
else
node = node->leftChild;
}
}
}
```
### 3. Delete
刪除一個 binary search tree 的字典對，依照該節點的特性可以分成 3 種情況處理：
* 葉節點：直接把要刪除的葉節點設為 0
* 有一個子節點：直接由子節點取代被刪除的節點，並將前一層的父節點指向新的子節點
* 有兩個子節點：被刪除的節點會由以下兩種可能取代，再由前一層父節點指向新節點
* 由左子樹的最大 key 的節點取代
* 由右子樹的最小 key 的節點取代
### 4. Implement of binary search tree
先建立一個實作的用的 binary search tree 以及 traversal 與 free 等常用函式
> The following code is saved in `BSToperation.c`.
```c
/** example of binary search tree
* 20
* / \
* 15 25
* / \ /
* 12 10 22
*/
treePointer exampleBST(){
element data1 = {20, 'a'}, data2 = {15, 'b'}, data3 = {25, 'c'}, data4 = {12, 'd'};
element data5 = {17, 'e'}, data6 = {22, 'f'};
treePointer nodeA, nodeB, nodeC, nodeD, nodeE, nodeF;
MALLOC(nodeA, sizeof(struct node));
MALLOC(nodeB, sizeof(struct node));
MALLOC(nodeC, sizeof(struct node));
MALLOC(nodeD, sizeof(struct node));
MALLOC(nodeE, sizeof(struct node));
MALLOC(nodeF, sizeof(struct node));
nodeA->leftChild = nodeB;
nodeA->data = data1;
nodeA->rightChild = nodeC;
nodeB->leftChild = nodeD;
nodeB->data = data2;
nodeB->rightChild = nodeE;
nodeC->leftChild = nodeF;
nodeC->data = data3;
nodeC->rightChild = NULL;
nodeD->leftChild = NULL;
nodeD->data = data4;
nodeD->rightChild = NULL;
nodeE->leftChild = NULL;
nodeE->data = data5;
nodeE->rightChild = NULL;
nodeF->leftChild = NULL;
nodeF->data = data6;
nodeF->rightChild = NULL;
return nodeA;
}
void traversalBST(treePointer root){
/* LVR */
if (root){
traversalBST(root->leftChild);
printf("%d ", root->data.key);
traversalBST(root->rightChild);
}
}
void freeBST(treePointer root){
if (root){
freeBST(root->leftChild);
freeBST(root->rightChild);
free(root);
}
}
```
> The following code is saves in `BST-implement.c`.
```c=
#include <stdio.h>
#include <stdlib.h>
#include "BST.h"
int main(void){
treePointer ptr = exampleBST();
element *itemPtr;
int insertKey = 27;
char insertCh = 'g';
printf("org: ");
traversalBST(ptr);
printf("\n");
// search
itemPtr = search(ptr, 12);
if (itemPtr)
printf("(key, value) = (%d, %c)\n", itemPtr->key, itemPtr->ch);
else
printf("Not exixt");
// iter search
itemPtr = iterSearch(ptr, 12);
if (itemPtr)
printf("(key, value) = (%d, %c)\n", itemPtr->key, itemPtr->ch);
else
printf("Not exixt");
insert(&ptr, insertKey, insertCh);
traversalBST(ptr);
freeBST(ptr);
return 0;
}
```
Sign in with Wallet
Connect another wallet