# Binary Search Tree 二元搜尋樹
**參考:** http://squall.cs.ntou.edu.tw/cpp/103spring/labtest/test1/BinarySearchTree.html
## 介紹
### (一)定義
為一種Binary Tree，若不為空則滿足 :
1. 左子樹所有Nodes之值均小於Root。
2. 柚子樹所有Nodes之值均大於Root。
3. 左右子樹亦是Binary Search Tree。
```graphviz
graph{
10--5
10--15
5--3[weight=2]
5--9
3--2
3--4
15--12
15--19[weight=2]
}
```
### (二)利用B.S.T.進行有小到大之排序
**Step1:**
將input data建成B.S.T.
**Step2:**
對B.S.T.進行**Inorder traversal**即得出小$\rightarrow$大排序
## 相關函式及其程式碼
在Binary Search Tree的Struct已建構完畢之下，我們來介紹以下函式。
### Search (搜尋資料)
此操作是藉由Binary Search Tree的特徵==Data(**L**)<Data(**V**)<Data(**R**)==，來判斷該向右走還是向左走。
```graphviz
digraph{
find[label="Find 10";style=dashed]
a1[label=9]
b1[label=5]
c1[label=2]
d1[label=7]
e1[label=10]
{rank=same;find,a1}
find->a1[style=dashed]
a1->b1
a1->c1
b1->d1
b1->e1
}
```
```graphviz
digraph{
a2[label=9;color=red;fontcolor=red]
b2[label=5;color=red;fontcolor=red]
c2[label=2]
d2[label=7]
e2[label=10;color=red;fontcolor=red]
a2->b2[color=red;style=bold]
a2->c2
b2->d2
b2->e2[color=red;style=bold]
}
```
#### 程式碼
```C=
BST_Node* FindNode(BST_Node* root, int value){
while(root!=NULL){
if (root->data==value){
return root; /*若找到目標，則回傳此節點*/
}
else if (root->data>value){
root = root->left; /*若目標比此節點之data小，則向左移動*/
}
else{
root = root->right; /*若目標比此節點之data大，則向右移動*/
}
}
return NULL; /*找不到*/
```
### Insert (新增資料)
此函數的操作可以視為Search( )的延伸，先利用 ==Data(**L**)<Data(**V**)<Data(**R**)== 的性質找到新增的節點適合的位置，在將新的節點接上Binary Search Tree。在尋找「適合的位置」時，會多假設一個節點(parent)來記錄目前所在位置(current)的父節點的位置，而在找到「適合的位置」後，在從父節點的位置接上新的節點。
```graphviz
digraph{
N[label="N=NULL";fontcolor=red;color=none]
a[label=9]
b[label=5]
c[label=10]
d[label=2]
e[label=7]
f[label=N;fontcolor=red;style=dashed]
g[label=N;fontcolor=red;style=dashed]
insert[label="Insert 13";style=dashed]
{rank=same;insert,a}
insert->a[style=dashed]
a->b
a->c
b->d[weight=2]
b->e
c->f[style=dashed]
c->g[weight=2;style=dashed]
}
```
```graphviz
digraph{
a[label=9;color=red;fontcolor=red]
b[label=5]
c[label=10;color=red;fontcolor=red]
d[label=2]
e[label=7]
f[label=N;fontcolor=red;style=dashed]
g[label=13;color=blue;fontcolor=blue]
a->b
a->c[color=red;style=bold]
b->d[weight=2]
b->e
c->f[style=dashed]
c->g[weight=2;color=red;style=bold]
}
```
#### 程式碼
```C
BST_Node* InsertNode(BST_Node* root, int val){
BST_Node* newnode;
BST_Node* current;
BST_Node* parent;
newnode = (BST_Node*)malloc(sizeof(BST_Node));
newnode->data = val;
newnode->left = NULL;
newnode->right = NULL;
if (root==NULL){
return newnode;/*若為空，則回傳newnode當作Binary Search Tree的root*/
}
else{
current = root;
while(current!=NULL){/*藉由判斷val的大小，將current移動到適當的位置*/
parent = current;
if (current->data>val){
current = current->left;
}
else{
current = current->right;
}
}
/*while()迴圈結束後，parent是在leaf的位置*/
if (parent->data>val){
parent->left = newnode;/*若val值較小，則將newnode接在parent的左子點*/
}
else{
parent->right = newnode;/*若val值較大，則將newnode接在parent的右子點*/
}
}
return root;
}
```
### Delete (刪除資料)
此為Binary Search Tree的函式中最難的部分。
在Binary Search Tree上刪除資料，必須在刪除後依然符合 ==Data(**L**)<Data(**V**)<Data(**R**)== 的性質，因此所有指向「欲刪除之節點」的pointer必須修改指向新的記憶體位置。另外，我們還需要再利用一個函式來找出「欲刪除之節點」的parent，而這個函式與尋找節點的函式非常相像，差別在於回傳其父節點。
以下根據「欲刪除之節點」的child pointer 個數分成三類：
* **Case1.** 沒有child pointer
* **Case2.** 只有一個child pointer
* **Case3.** 有兩個child pointer
#### Case1：沒有child pointer
只需要考慮原本指向此節點的父點parent，將其 left child/right child 指向NULL即可。
#### Case2：只有一個child pointer
假如「欲刪除之節點」有一個left child，則需要將其父點 parent 的 left child/right child 重新指向「欲刪除之節點」的 left child。
#### Case3：有兩個child pointer
須先從「欲刪除之節點」的==左子樹中尋找最大值==或是==右子樹中尋找最小值==作為取代點(假設此節點為X)，來取代「欲刪除之節點」的data，再來對於X進行刪除的動作。
* 左子樹尋找最大值的方法：不斷地向右移動，直到碰到NULL為止。
```C=
/*尋找欲刪除節點之父節點*/
BST_Node* FindParent(BST_Node* root, int value, int* pos){
BST_Node *parent;
parent = root;
*pos = 0; /*pos用來標記是向左移動還是向右移動*/
while(root!=NULL){
if (root->data == value){
return parent; /*找到目標，回傳此節點之父節點*/
}
else{
parent = root;
if (root->data > value){
root = root->left;
*pos=-1; /*向左移動，並以*pos=-1表示*/
}
else{
root = root->right;
*pos =1; /*向右移動，並以*pos=1表示*/
}
}
}
return NULL; /*找不到，回傳NULL*/
}
/*刪除節點*/
BST_Node* DeleteNode(BST_Node* root, int value){
BST_Node *parent;
BST_Node *ptr;
BST_Node *next;
int pos;
parent = FindParent(root, value, &pos);/*利用函式找出父節點*/
if (parent!=NULL){
switch(pos) /*判斷節點在父節點的哪裡*/
{
case -1:
ptr = parent->left;
break;
case 1:
ptr = parent->right;
break;
case 0:
ptr = parent;
break;
}
if (ptr->left==NULL){ /*若節點之左子節點為NULL*/
if (parent == ptr){ /*父節點即為節點本身，即節點為root*/
root = root->right; /*將root移向其右子節點*/
}
else{
if (pos == 1){
/*欲刪除的節點在父節點右方,所以將父節點的右節點*/
/*指向欲刪除節點的右節點*/
parent->right = ptr->right;
}
else{
/*欲刪除的節點在父節點左方,所以將父節點的左節點*/
/*指向欲刪除節點的左節點*/
parent->left = ptr->right;
}
}
free(ptr);
}
else if (ptr->right==NULL){
if (parent == ptr){
root = root->left;
}
else{
if (pos==1){
/*欲刪除的節點在父節點右方,所以將父節點的右節點*/
/*指向欲刪除節點的左節點*/
parent->right = ptr->left;
}
else{
/*欲刪除的節點在父節點左方,所以將父節點的左節點*/
/*指向欲刪除節點的左節點*/
parent->left =ptr->left;
}
}
free(ptr);
}
else{/*欲刪除節點有左右子樹*/
parent = ptr;
next = ptr->left;/*從欲刪除節點之左子樹中尋找最大值之取代點*/
while(next->right!=NULL){
parent = next;
next = next->right;
}
ptr->data = next->data;/*取代!*/
if (parent == ptr){/*取代點之父節點即為欲刪除點，表示取代點無右子樹*/
ptr->left = next->left;
}
else{
parent->right = next->left;/*將取代點之左子樹接上其父節點的右方*/
}
free(next);
}
}
return root;
}
```
### Sort (排序資料)
由於Binary Search Tree具有==Data(**L**)<Data(**V**)<Data(**R**)== 之特性，只要利用Inorder Traversal的方式，即可得到由小到大的排序。
```C
void inorder_traversal(BST_Node* root){
if (root != NULL){
inorder_traversal(root->left);
printf(" %d",root->data);
inorder_traversal(root->right);
}
}
```
### 範例
最後，將以上所有函式利用下面的範例來做總結：
```C=
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//建構Binary Search Tree的Structure
struct binary_search_tree{
int data;
struct binary_search_tree *left;
struct binary_search_tree *right;
};
typedef struct binary_search_tree BST_Node;
void inorder_traversal(BST_Node* root){
if (root != NULL){
inorder_traversal(root->left);
printf(" %d",root->data);
inorder_traversal(root->right);
}
}
BST_Node* InsertNode(BST_Node* root, int val){
/*略*/
}
BST_Node* FindParent(BST_Node* root, int value, int* pos){
/*略*/
}
BST_Node* DeleteNode(BST_Node* root, int value){
/*略*/
}
int main(){
int i;
int data[] = {10, 20, 5, 8, 30, 15, 3, 18, 2, 1};
int ndata = sizeof(data)/sizeof(int);
BST_Node *head = NULL;
for (i=0; i<ndata; i++) /*建立Binary Search Tree*/
head = InsertNode(head, data[i]);
printf("In order listing:\n"); /*輸出Inorder Traversal之排序*/
inorder_traversal(head);
printf("\n");
assert(FindNode(head, 15)); /*assert判斷是否有錯誤，如果有錯，立即中止程式*/
assert(!FindNode(head, 11));
head = DeleteNode(head,5); /*刪除節點5*/
printf("After delete the node 5:\n");
inorder_traversal(head); /*輸出Inorder Traversal之排序*/
return 0;
}
```
結果如下：
:::success
In order listing:
1 2 3 5 8 10 15 18 20 30
After delete the node 5:
1 2 3 8 10 15 18 20 30
:::