[C 範例代碼] 數據結構 : 二元樹 - 二元排序樹

前言 : 
編成實現功能: 創建一棵二元排序樹, 創建完成後輸入要查找的數據並進行對二元排序樹搜尋, 並將搜尋次數與結果顯示出來. 

技術要點 : 
二元排序樹是一棵具有如下特徵的非空二元樹 : 

1. 若它的左子樹非空, 則左子樹上所有節點的值都小於根節點的值.
2. 若他的右子樹非空, 則右子樹上所有節點的值都大於根節點的值.
3. 左右子樹本身各是一棵二元排序樹.

範例代碼 : 

view plaincopy to clipboardprint?

1. #include   
2. #include   
3.   
4. struct bnode{  
5.     struct bnode *lchild;  
6.     char data;  
7.     struct bnode *rchild;  
8. };  
9. typedef bnode *bitree;  
10.   
11. int searchBTree(bitree root, int key) {  
12.     int n=0;  
13.     if(root == NULL)  
14.         return -1;  
15.     bitree tmp = root;  
16.     while(tmp != NULL) {  
17.         n++;  
18.         if(tmp->data > key) {  
19.             tmp = tmp->lchild;  
20.         } else if(tmp->data == key) {  
21.             return n;  
22.         } else {  
23.             tmp = tmp->rchild;  
24.         }  
25.     }  
26.     return -1;  
27. }  
28.   
29. void addNode(bitree *root, int val) {  
30.     if(*root == NULL) {  
31.         *root = (bitree) malloc(sizeof(bnode));  
32.         (*root)->data = val;  
33.         (*root)->lchild = NULL;  
34.         (*root)->rchild = NULL;  
35.     } else {  
36.         bitree newtr = (bitree) malloc(sizeof(bnode));  
37.         newtr->data = val;  
38.         newtr->lchild = NULL;  
39.         newtr->rchild = NULL;  
40.         bitree tmp = *root;  
41.         while(tmp != NULL) {  
42.             if(tmp->data > val) { // 往左子樹               
43.                 if(tmp->lchild != NULL) {  
44.                     tmp = tmp->lchild;  
45.                 } else {  
46.                     tmp->lchild = newtr;  
47.                     break;  
48.                 }  
49.             } else {  // 往右子樹  
50.                 if(tmp->rchild != NULL) {  
51.                     tmp = tmp->rchild;  
52.                 } else {  
53.                     tmp->rchild = newtr;  
54.                     break;  
55.                 }  
56.             }             
57.         }  
58.     }  
59. }  
60.   
61. void SC_113() {  
62.     bitree root = NULL;  
63.     int val = 0;  
64.     while(val>=0) {  
65.         printf("Please give val (-1 to leave): ");  
66.         scanf("%d", &val);  
67.         if(val>=0)  
68.             addNode(&root, val);  
69.     }  
70.     printf("Please give search key: ");  
71.     scanf("%d", &val);  
72.     int n = searchBTree(root, val);  
73.     if(n>0) {  
74.         printf("Found in %d times!\n", n);  
75.     } else {  
76.         printf("Not found!");  
77.     }  
78.     free(root);  
79. }  

執行結果 : 

Please give val (-1 to leave): 5
Please give val (-1 to leave): 9
Please give val (-1 to leave): 2
Please give val (-1 to leave): 6
Please give val (-1 to leave): 4
Please give val (-1 to leave): 3
Please give val (-1 to leave): 7
Please give val (-1 to leave): 10
Please give val (-1 to leave): -1 <離開建立搜尋二元樹>
Please give search key: 6
Found in 3 times!

補充說明 : 
* [ 資料結構 小學堂 ] 樹狀結構導論 : 二元運算樹進階研究 - 二元排序樹