# <center><font size=10>binary_search_tree.a</font> <br> <font size=5>二元搜尋樹使用說明書</font> <br> <font size=4>by 李奕承</font></center>
# <center>摘要</center>
本library提供的結構如下
```c
typedef struct node {
struct node* left;
struct node* right;
}btreeNode_t;
```
本 library 提供以下幾種函數
- 初始化
- 插入節點
- 列印二元搜尋樹
- 中序走訪
- 複製樹
- 判斷兩個樹是否相等
- 尋找節點
- 尋找最小節點
- 尋找最大節點
- 層序走訪佇列
- 刪除節點
- 計算level
# <center>使用方法</center>
### 1.帶入標頭檔
```c
#include"bstSpec.h"
```
### 2.在要使用二元搜尋樹的結構中加入 btreeNode_t 作為成員
例如
```c
typedef struct test_tree_node{
int data;
char *name;
btreeNode_t node; // 作為成員
}test_tree_node;
```
### 3.建立樹根
需要先選擇一筆資料建立根節點，之後用來做其他操作，例如：
```c
test_tree_node root;
Bst_init(&root.node);
root.data = 7;
root.name = "David";
```
### 4.編寫並提供回調函數指標
以下幾個需要使用者編寫並提供回調函數指標
```c
insertNode
deleteNode
inOrder
findNode
treeCopy
treeEqual
```
### 5.搭配巨集使用
如果 btreeNode_t 不是在結構中的第一個成員，要使用 btreeNode_t 指標存取其它成員時，可以使用本libary提供的下面這個巨集
```c
#define return_to_user_struct_pointer(USER_STRUCT_TYPE, MEMBER_NAME, MEMBER_POINT)
```
USER_STRUCT_TYPE : 你設計的結構名稱
MEMBER_NAME : btreeNode_t 在你的結構中的成員名稱
MEMBER_POINT : btreeNode_t 在你結構中的指標
### 6.編譯
- bstSpec.h 要記得放在引用標頭檔的路徑下
- 編譯時記得加入 binary_search_tree.a
```
gcc -I include -Wall -o ./bin/test test.c binary_search_tree.a
```
# <center>函數介紹與範例</center>
## 範例使用的結構
下面是範例用到的結構，btreeNode_t 是它的第三個成員
```c
typedef struct test_tree_node{
int data;
char *name;
btreeNode_t node;
}test_tree_node;
```
## 初始化
```c
void Bst_init(btreeNode_t* node);
```
這個函數可以將 btreeNode_t 中的 left 和 right 成員初始化為指向NULL。
可以在你新增一個結構時使用，例如下面的示範，宣告一個測試用的結構，並初始化裡面的 btreeNode_t 成員。
```c
test_tree_node a;
Bst_init(&a.node);
```
## 插入節點
```c
void insertNode(btreeNode_t* insert_element, btreeNode_t** root,
int(*compare)(btreeNode_t* insert_element, btreeNode_t* in_tree_element));
```
這個函數可以將一個節點插入到二元樹中，範例中先宣告一個空的樹 tree_one
```c
btreeNode_t* tree_one = NULL;
```
<font color= #0000FF>本函數的參數中有函數指針，需要使用者傳入用來比較大小的函數。</font>
以下是範例使用的比較函數
```c
int compare_int(btreeNode_t* insert_element, btreeNode_t* in_tree_element)
{
if(return_to_user_struct_pointer(test_tree_node, node, insert_element)->data <
return_to_user_struct_pointer(test_tree_node, node, in_tree_element)->data)
{
return -1;
}
if(return_to_user_struct_pointer(test_tree_node, node, insert_element)->data >
return_to_user_struct_pointer(test_tree_node, node, in_tree_element)->data)
{
return 1;
}
if(return_to_user_struct_pointer(test_tree_node, node, insert_element)->data ==
return_to_user_struct_pointer(test_tree_node, node, in_tree_element)->data)
{
return 2;
}
return 0;
}
```
接著建立幾個用來測試的節點
```c
test_tree_node root;
Bst_init(&root.node);
root.data = 7;
root.name = "David";
test_tree_node a;
Bst_init(&a.node);
a.data = 3;
a.name = "Kent";
test_tree_node b;
Bst_init(&b.node);
b.data = 2;
b.name = "John";
test_tree_node c;
Bst_init(&c.node);
c.data = 8;
c.name = "Alice";
test_tree_node d;
Bst_init(&d.node);
d.data = 4;
d.name = "Alisa";
```
將他們插入到 tree_one 中
```c
insertNode(&root.node, &tree_one, compare_int);
insertNode(&a.node, &tree_one, compare_int);
insertNode(&b.node, &tree_one, compare_int);
insertNode(&c.node, &tree_one, compare_int);
insertNode(&d.node, &tree_one, compare_int);
```
## 列印二元搜尋樹
```c
void printf_tree(btreeNode_t* root, int(*get_data)(btreeNode_t* queue_member));
```
這個函數可以將二元搜尋樹以圖形的形式列印出來。
<font color= #0000FF>本函數的參數中有函數指標，需要使用者傳入用來取得印出資料的函數。</font>
以下是範例使用的函數
```c
int get_data(btreeNode_t* root)
{
return return_to_user_struct_pointer(test_tree_node, node, root)->data;
}
```
將 tree_one 印出來
```c
printf_tree(tree_one, get_data);
```
終端機顯示的圖形
```
7
/ \
/ \
3 8
/ \
2 4
```
## 中序走訪
```c
void inOrder(btreeNode_t* root, void(*print)(btreeNode_t* root));
```
本函數顯示一個樹的中序走訪結果。
<font color= #0000FF>本函數的參數中有函數指標，需要使用者傳入用來印出資料的函數。</font>
以下是範例使用的函數
```c
void print_data(btreeNode_t* root)
{
printf("%d ", return_to_user_struct_pointer(test_tree_node, node, root)->data);
}
```
中序走訪 tree_one
```c
printf("print tree_one : \n");
inOrder(tree_one, print_data);
```
終端機的輸出
```
print tree_one inorder : 2 3 4 7 8
```
## 複製樹
```c
btreeNode_t* treeCopy(btreeNode_t* root, btreeNode_t*(*copy)(btreeNode_t* root));
```
本函數可以複製一個二元搜尋樹。
<font color= #0000FF>本函數的參數中有函數指標，需要使用者傳入用來複製節點的函數。</font>
以下是範例使用的函數
```c
btreeNode_t* copy_test_node(btreeNode_t* root)
{
test_tree_node * new_node = (test_tree_node *)malloc(sizeof(test_tree_node));
*new_node = *return_to_user_struct_pointer(test_tree_node, node, root);
Bst_init(&new_node->node);
return &new_node->node;
}
```
宣告一個空樹指標 tree_two ，將 tree_one 的樹複製給 tree_two 並印出
```c
btreeNode_t* tree_two = treeCopy(tree_one, copy_test_node);
printf_tree(tree_two, get_data);
```
終端機的輸出
```
7
/ \
/ \
3 8
/ \
2 4
```
## 判斷兩個樹是否相等
```c
int treeEqual(btreeNode_t* root_A, btreeNode_t* root_B,
int(*compare)(btreeNode_t* root_A, btreeNode_t* root_B));
```
本函數用來判斷兩個二元搜尋樹是否相等。
<font color= #0000FF>本函數的參數中有函數指標，需要使用者傳入用來比較兩個節點是否相等的函數。</font>
以下是範例使用的函數
```c
int compare_Equal(btreeNode_t* node_a, btreeNode_t* node_b)
{
if(return_to_user_struct_pointer(test_tree_node, node, node_a)->data ==
return_to_user_struct_pointer(test_tree_node, node, node_b)->data)
{
if(strcmp(return_to_user_struct_pointer(test_tree_node, node, node_a)->name,
return_to_user_struct_pointer(test_tree_node, node, node_b)->name) == 0)
{
return 1;
}
}
return 0;
}
```
比較 tree_one 和 tree_two
```c
printf("is tree_one and tree_two Equal? (1:ture 0:false): ");
printf("%d\n", treeEqual(tree_one, tree_two, compare_Equal));
```
終端機的輸出
```
is tree_one and tree_two Equal? (1:ture 0:false): 1
```
## 尋找節點
```c
btreeNode_t* findNode(int key, btreeNode_t* root,
int(*compare)(int key, btreeNode_t* in_tree_element));
```
本函數根據使用者要求的值來尋找符合的節點。
<font color= #0000FF>本函數的參數中有函數指標，需要使用者傳入用來比較節點的函數。</font>
以下是範例使用的函數
```c
int compare_key(int key, btreeNode_t* in_tree_element)
{
if(key <
return_to_user_struct_pointer(test_tree_node, node, in_tree_element)->data)
{
return -1;
}
if(key >
return_to_user_struct_pointer(test_tree_node, node, in_tree_element)->data)
{
return 1;
}
if(key ==
return_to_user_struct_pointer(test_tree_node, node, in_tree_element)->data)
{
return 2;
}
return 0;
}
```
比對 data 尋找並印出該節點的 name 成員
```c
test = findNode(2, tree_one, compare_key);
printf("find who's ID is 2 : ");
if(test != NULL)
{
printf("%s\n", return_to_user_struct_pointer(test_tree_node, node, test)->name);
}
test = findNode(7, tree_one, compare_key);
printf("find who's ID is 7 : ");
if(test != NULL)
{
printf("%s\n", return_to_user_struct_pointer(test_tree_node, node, test)->name);
}
test = findNode(3, tree_one, compare_key);
printf("find who's ID is 3 : ");
if(test != NULL)
{
printf("%s\n", return_to_user_struct_pointer(test_tree_node, node, test)->name);
}
test = findNode(8, tree_one, compare_key);
printf("find who's ID is 8 : ");
if(test != NULL)
{
printf("%s\n", return_to_user_struct_pointer(test_tree_node, node, test)->name);
}
```
終端機的輸出
```
find who's ID is 2 : John
find who's ID is 7 : David
find who's ID is 3 : Kent
find who's ID is 8 : Alice
```
## 尋找最小節點
```c
btreeNode_t* findMinNode(btreeNode_t* root);
```
本函數可以尋找一個二元搜尋樹的最小節點。
以下範例以 tree_one 為例
```c
printf("find minimum node in tree_one : ");
printf("%d\n",
return_to_user_struct_pointer(test_tree_node, node, findMinNode(tree_one))->data);
```
終端機的輸出
```
find minimum node in tree_one : 2
```
## 尋找最大節點
```c
btreeNode_t* findMaxNode(btreeNode_t* root);
```
本函數可以尋找一個二元搜尋樹的最大節點。
以下範例以 tree_one 為例
```c
printf("find maximum node in tree_one : ");
printf("%d\n",
return_to_user_struct_pointer(test_tree_node, node, findMaxNode(tree_one))->data);
```
終端機的輸出
```
find maximum node in tree_one : 8
```
## 層序走訪佇列
```c
void tree_level_to_queue(btreeNode_t* root, btreeNode_t* queue[]);
```
本函數以層序走訪一個二元搜尋樹，並按順序將每個節點的指標存進佇列。
以下範例以 tree_one 為例並印出佇列
```c
printf("print level order of tree_one : ");
btreeNode_t* level_temp[10];
for(int i = 0 ; i < 10 ; i++)
{
level_temp[i] = NULL;
}
tree_level_to_queue(tree_two, level_temp);
for(int i = 0 ; i < 10 ; i++ )
{
if(level_temp[i] != NULL)
{
printf("%d ",
return_to_user_struct_pointer(test_tree_node, node, level_temp[i])->data);
}
}
```
終端機的輸出
```
print level order of tree_one : 7 3 8 2 4
```
## 刪除節點
```c
void deleteNode(btreeNode_t* delete_node, btreeNode_t** root,
int(*compare)(btreeNode_t* delete_node, btreeNode_t* in_tree_element));
```
這個函數可以將一個節點從樹中刪除，當刪除的節點左右都有子樹時，本library會拿右子樹的最小節點來放在被刪除的節點位置。
<font color= #0000FF>本函數的參數中有函數指標，需要使用者傳入用來比較節點的函數。</font>
以下是範例使用的函數
```c
int compare_int(btreeNode_t* insert_element, btreeNode_t* in_tree_element)
{
if(return_to_user_struct_pointer(test_tree_node, node, insert_element)->data <
return_to_user_struct_pointer(test_tree_node, node, in_tree_element)->data)
{
return -1;
}
if(return_to_user_struct_pointer(test_tree_node, node, insert_element)->data >
return_to_user_struct_pointer(test_tree_node, node, in_tree_element)->data)
{
return 1;
}
if(return_to_user_struct_pointer(test_tree_node, node, insert_element)->data ==
return_to_user_struct_pointer(test_tree_node, node, in_tree_element)->data)
{
return 2;
}
return 0;
}
```
刪除 tree_one 中 data 為 3 的 a 節點，並印出刪除後的樹
```c
deleteNode(&a.node, &tree_one, compare_int);
printf_tree(tree_one, get_data);
```
終端機的輸出
```
7
/ \
/ \
4 8
/
2
```
## 計算level
```c
int count_tree_level(btreeNode_t* root);
```
這個函數可以計算一個二元搜尋樹的level數，本 library 假設樹根 level 為 0
以下範例計算 tree_one 的 level 數並印出
```c
printf("print tree_one level : ");
printf("%d\n", count_tree_level(tree_one));
```
終端機的輸出
```
print tree_one level : 2
```
Sign in with Wallet
Connect another wallet