第六章 二元搜尋樹 現在我們的注意焦點要轉到搜尋樹（search tree）了，要深度討論兩種標準的樹結構（tree structure），就是本章所要說明的二元搜尋樹（binary search tree）以及下一章所要討論的 AVL 平衡樹（AVL tree）。這兩種樹其資料都依序排列的，它們之間的差別只在於.

Presentation on theme: "第六章 二元搜尋樹 現在我們的注意焦點要轉到搜尋樹（search tree）了，要深度討論兩種標準的樹結構（tree structure），就是本章所要說明的二元搜尋樹（binary search tree）以及下一章所要討論的 AVL 平衡樹（AVL tree）。這兩種樹其資料都依序排列的，它們之間的差別只在於."— Presentation transcript:

1 第六章 二元搜尋樹 現在我們的注意焦點要轉到搜尋樹（search tree）了，要深度討論兩種標準的樹結構（tree structure），就是本章所要說明的二元搜尋樹（binary search tree）以及下一章所要討論的 AVL 平衡樹（AVL tree）。這兩種樹其資料都依序排列的，它們之間的差別只在於 AVL 是一種平衡樹，而二元搜尋樹卻不是。 前面章節在設計堆疊或佇列時，其資料結構都可選用陣列或連結串列，選用陣列對於搜尋作業其效率很高，但對於插入及移除卻沒有效率，選用連結串列對於搜尋作業其效率很差，但對於插入及移除卻有很高的效率，理想的結構是搜尋、插入、移除等作業其效率都要很好，答案就是使用二元搜尋樹或 AVL 平衡樹結構。

2 6.1 基本觀念 一棵二元搜尋樹是一棵二元樹，俱有下列的特性： 1. 所有左子樹其資料項均小於根節點。
2. 所有右子樹其資料項均大於或等於根節點。 3. 每一子樹本身也是一棵二元搜尋樹。

3 二元搜尋樹 一般而言，每一個節點所表示的資訊非僅是一個單純的資料，而是一組資料的結合，稱為一個記錄（record），在 C 語言裡屬於一種結構型態（struct）。當二元搜尋樹其節點的對象是一個記錄時，其順序為該記錄的鍵（key）值。如下圖所示。

4 五種二元搜尋樹舉例 下圖是五種二元搜尋樹舉例，（a）與（b）是一棵完整且平衡的二元搜尋樹，（d）是一棵接近完整且平衡的二元搜尋樹，（c）與（e）是既不完整也不平衡的二元搜尋樹。

5 6.2 二元搜尋樹資料結構 二元搜尋樹實作需要兩種不同的結構，一個頭結構以及一個資料結構。頭結構包含不屬資料的一些相關的資訊，例如資料節點計數、第一個資料節點指標、或是資料的比較方法，等等的資訊。 資料結構包含資料欄以及鏈欄，鏈欄的內含為下一個資料節點的指標。資料欄可以是資料本身，也可以是指到真正資料位置的指標，left 鏈欄指到下一個左子樹根節點，right 鏈欄指到下一個右子樹根節點，鏈欄其值若為 NULL 則表示不指到任何資料節點。

6 資料結構 資料結構宣告如下： struct bstNodeTag { void *dataptr;
struct bstNodeTag *left; struct bstNodeTag *right; }; 本案例資料結構裡的資料欄宣告為不定型態的指標「void *dataptr」，不定型態的指標與任何型態的指標相匹配，使用時只須強迫轉型為指定的型態就可使用了。鏈欄 left 及 right 都是指標，它指到下一個子樹根節點。

7 頭結構 頭結構宣告如下： struct bstTag { int count;
int (*compare) (void* arg1, void* arg2); struct bstNodeTag *root; }; 頭結構裡有三個成員，count 成員為節點計數。root 表二元搜尋樹根節點的指標。compare 是兩項資料比較的函式，資料項可以是整數、浮點數、字元、字串等等 C 語言所允許的資料型態，這個函式使用時必須由使用者提供。

8 6.3 建立頭結構初值 struct bstTag *bstCreate(int (*compare)
(void *arg1, void *arg2)) { struct bstTag *tree; tree = malloc(sizeof(struct bstTag)); if (tree) tree->root = NULL; tree->count = 0; tree->compare = compare; } return tree;

9 6.4 加入 int bstInsert(struct bstTag *tree, void *dataptr) {
struct bstNodeTag* newptr; newptr = malloc(sizeof(struct bstNodeTag)); if (!newptr) return 0; newptr->right = NULL; newptr->left = NULL; newptr->dataptr = dataptr; if (tree->count == 0) tree->root = newptr; else InsertBST(tree, tree->root, newptr); (tree->count)++; return 1; } 6.4 加入

10 6.5 取得 void *bstGet(struct bstTag *tree, void *keyptr) {
if (tree->root) return GetBST(tree, keyptr, tree->root); else return NULL; }

11 6.6 移除 int bstRemove(struct bstTag *tree, void *delkey) { int success;
struct bstNodeTag *newroot; newroot=RemoveBST(tree,tree->root,delkey,&success); if (success) tree->root = newroot; (tree->count)--; if (tree->count == 0) tree->root=NULL; } return success;

12 6.7 測試空白 int bstEmpty(struct bstTag *tree) {
return (tree->count==0); }

13 6.8 測試滿載 int bstFull(struct bstTag *tree) {
struct bstNodeTag * newptr; newptr = malloc(sizeof(*(tree->root))); if (newptr) free(newptr); return 0; } else return 1;

14 6.9 傳回資料項數 int bstCount(struct bstTag *tree) {
return (tree->count); }

15 6.10 釋放記憶體 struct bstTag *bstRelease(struct bstTag *tree) { if (tree)
ReleaseBST (tree->root); free (tree); return NULL; }

16 6.11 二元搜尋樹應用 將前面有關二元搜尋樹的資料結構以及函式存入 bst.h 表頭檔備用。表頭檔名 b 表 binary，s 表 search，t 表 tree，即二元搜尋樹的意思。

17 6.11.1 整數二元搜尋樹 執行下列 numbst.c 程式時，依序從 data[] 輸入下列的整數：
每輸入一個整數時就透過 bstInsert() 函式插入二元搜尋樹的適當位置，最後建立一個如下圖所示的 tree 二元搜尋樹。

18 建立一棵二元搜尋樹tree 要建立一棵二元搜尋樹必須提供一個比較函式，因為本題的資料為整數，因此將不定型態的指標「void *」num1 及 num2 強迫轉型為「int *」整數型態的指標 key1 及 key2，然後進行比較，將結果傳回。 int compare(void *num1, void *num2) { return *(int*)num1 - *(int*)num2; } 比較函式名為 compare，可當建立建立二元搜尋樹函式的引數，其程式碼如下： struct bstTag *tree; tree = bstCreate(compare);

19 依次從 data[] 輸入一個整數 data[i]
for (i=0; i<sizeof(data)/sizeof(int); i++) { dataptr = (int *)malloc(sizeof(int)); *dataptr = data[i]; bstInsert(tree, dataptr); } 這一段程式依次從 data[] 輸入一個整數 data[i]，取得整數大小的記憶體 dataptr 後將 data[i] 拷貝至此記憶體，然後透過 bstInsert() 函式將 dataptr 位址插入 tree 二元搜尋樹適當的位置。一直輸入到 data[] 沒有資料才結束輸入的作業，二元搜尋樹也才建立完成，如上圖 6.3 所示。

20 二元搜尋樹的遍訪 bstTraverse(tree, printNum);
這是對於 tree 二元搜尋樹的中序遍訪（inorder），printNum 是列印資料節點的函式，本例題只是將不定型態 void 指標轉成整數指標後列印其整數內容而已。 printf("\nPreorder :\n"); preorder(tree->root); 這是對於 tree 二元搜尋樹的前序遍訪（preorder）。 printf("\nPostorder :\n"); postorder(tree->root); 這是對於 tree 二元搜尋樹的後序遍訪（postorder）。

21 Inorder : Preorder : Postorder :

22 班上同學成績 上一個例題資料節點裡資料指標 dataptr 所指的是很單純的一個整數而已，本例題「班上同學成績」其 dataptr 所指的卻是一個學生資料結構，宣告如下： struct studentNodeTag { int id; char name[21]; float score; }; 該結構包含三個成員，id 為學生證號碼，宣告為整數，name 為姓名，宣告為 21 個字元的字串，字串以 '\0' 結束，score 欄為該生平均成績，宣告為浮點數。本結構包含三種不同資料型態的變數，整數、字串、浮點數。

23 同學資料從檔案student.txt輸入 每一個同學的資料均從檔案輸入，然後插入二元搜尋樹的適當位置。執行 student.c 程式時從本文檔 student.txt 輸入下列的資料： 105 Maya 86 103 Kay 109 Jay 107 Lina 115 Fay

24 學生成績二元搜尋樹

25 Void buildClass(struct bstTag *tree)
{ char buf[512]; struct studentNodeTag *sp; FILE *f = fopen("student.txt", "r"); while (fgets(buf,512,f)!=NULL) sp = malloc(sizeof(struct studentNodeTag)); sscanf(buf,"%d %s %f", &(sp->id), sp->name, &(sp->score)); bstInsert(tree, sp); } fclose(f); return; 執行本程式時，首先從檔案student.txt 輸入學生資料，建立一棵二元搜尋樹 tree，它是透過「buildClass(tree);」敘述完成的，其程式碼如左：

26 這是主程式的功能表，首先執行 getOption() 函式顯示一個功能選項表，並輸入一個字元 option，若該字元不是 'Q'，就一直執行選項的工作，選 'A' 功能插入學生成績，'F' 功能找尋學生成績，'P' 功能印出二元搜尋樹 tree 所有節點資料，'R' 功能移除指定學生節點，這些功能的函式程式碼都很簡單，請直接參閱 student.c 程式，就不再逐一說明了。 while ( (option = getOption()) != 'Q') { switch (option) case 'A': insertStudent(tree); break; case 'F': findStudent(tree); break; case 'P': printTree(tree); break; case 'R': removeStudent(tree); break; }

27 檔案student.txt 105 Maya 86 103 Kay 82 109 Jay 79 107 Lina 75 115 Fay 80

28 【編譯執行】 ch05> gcc student.c -o student.exe <Enter> ch05> student.exe <Enter> ====== MENU ====== I Insert Student F Find Student P Print Class List R Remove Student Q Quit Enter option : p <Enter> List students in the class: id name score 103 Kay 105 Maya 107 Lina 109 Jay 115 Fay

29 Find Student ====== MENU ====== I Insert Student F Find Student
P Print Class List R Remove Student Q Quit Enter option : f <Enter> Enter student id : 109 <Enter> Student id: 109 name: Jay score: 79.0

30 Remove Student ====== MENU ====== I Insert Student F Find Student
P Print Class List R Remove Student Q Quit Enter option : r <Enter> Enter student id : 109 <Enter>

31 Insert Student ====== MENU ====== I Insert Student F Find Student
P Print Class List R Remove Student Q Quit Enter option : i <Enter> Enter id,name,score (EOF end) : 109 Peter 88.8 <Enter> Enter id,name,score (EOF end) : 108 Tom 77.7 <Enter> Enter id,name,score (EOF end) : ^Z <Enter>

32 Print Class List ====== MENU ====== I Insert Student F Find Student
P Print Class List R Remove Student Q Quit Enter option : p <Enter> List students in the class: id name score 103 Kay 105 Maya 107 Lina 108 Tom 109 Peter 115 Fay Print Class List

33 Quit ====== MENU ====== I Insert Student F Find Student
P Print Class List R Remove Student Q Quit Enter option : q <Enter>

34 6.12 字串二元搜尋樹 我們前面所建立的二元搜尋樹其資料節點裡的資料是一個不定型態的指標，其宣告如下： void *dataptr;
資料指標所指的可以是任何 C 語言所提供的資料型態，可以說以不變應萬變，不過對初學者來講完全透過指標的操作顯然有點複雜，不易了解，筆者另設計一套以字串資料為主的函式，操作較容易，說明如下。

35 6.12.1 資料結構 資料節點的結構宣告如下： #define STRLEN 80 struct strbstNodeTag {
char data[STRLEN]; struct strbstNodeTag *right, *left; }; 宣告一個常數識別字 STRLEN 其值為 80，資料字串最長 80 個字元，此常數值可依需要隨時更改。結構名稱為 strbstNodeTag，包含三個成員，data 資料是 STRLEN 長度的字串，left 及 right 為指向此種節點的指標。

36 6.12.2 建立根節點指標 struct strbstNodeTag *strbstCreate() {
struct strbstNodeTag *root; root = malloc(sizeof(struct strbstNodeTag)); root = NULL; return root; } 取得一塊記憶體 root，將其值設為 NULL 值，表示目前不指到任何節點，將 root 傳回。請注意它並不需指定比較函式 。

37 6.12.3 插入 void strbstInsert(struct strbstNodeTag **root,
struct strbstNodeTag *itemptr) { if ((*root)==NULL) *root = itemptr; return; } if (strcmp(itemptr->data,(*root)->data)<0) strbstInsert(&(*root)->left, itemptr); else if (strcmp(itemptr->data,(*root)->data)>0) strbstInsert(&(*root)->right, itemptr);

38 6.12.4 取得 void *strbstGet(struct strbstNodeTag *root, void *keyptr) {
if (root) if (strcmp(keyptr, root->data) < 0) return strbstGet(root->left, keyptr); else if (strcmp(keyptr, root->data) > 0) return strbstGet(root->right, keyptr); else return root->data; } return NULL; 取得

39 6.12.5 移除 int strbstRemove(struct strbstNodeTag *root, void *delkey) {
int success; struct strbstNodeTag *newroot; newroot = RemoveStrbst(root, delkey, &success); if (success) root = newroot; else root = NULL; return success; }

40 6.12.6 測試空白 int strbstEmpty(struct strbstNodeTag *root) {
return (root==NULL); }

41 6.12.7 測試滿載 int strbstFull(struct strbstNodeTag *root) {
struct strbstNodeTag *newptr; newptr = malloc(sizeof(*(root))); if (newptr) free(newptr); return 0; } else return 1;

42 6.12.8 傳回資料項數 int strbstCount(struct strbstNodeTag *root) {
int count=0; if (root==NULL) return 0; CountStrbst(root, &count); return count; }

43 6.12.9 釋放記憶體 void *strbstRelease(struct strbstNodeTag *root) {
if (root) strbstRelease(root->left); free(root); strbstRelease(root->right); } return NULL;

44 測試程式 以上所說明有關字串二元搜尋樹的資料結構宣告，以及相關的函式存入表頭檔 strbst.h 備用。str 表字串 string，b 表二元 binary，s 表搜尋 search，t 表樹結構 tree。 在測試程式 strbst.c 裡頭所準備的輸入資料 data[] 如下： "JMP" "COMP" "MUL" "DIV" "ADD" "SUB" "LOOP" "LEA" "MOV" 一共九個字串，依次透過 strbstInsert() 函式建立一個 root 字串二元搜尋樹，如下圖所示。

45 建立字串二 元搜尋樹

46 遍訪及移除 然後分別測試前序遍訪、後序遍訪、中序遍訪等函式是否正確。然後測試移除 "MUL" 字串的作業，移除節點的作業較複雜，說明如下：
1. 在二元搜尋樹裡找到移除鍵 "MUL" 節點 p。 2. 找到 p 節點之左子樹中最大者 "MOV" 之節點 x。 3. 將 p 節點資料（"MUL"）與 x 節點資料（"MOV"）互換。 4. 移除 x 節點（"MUL"）。

47 移除"MUL"節點之前

48 移除"MUL"節點之後

49 重新插入"MUL"節點之後