## 2012年4月6日 星期五

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

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

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)
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 {
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 <離開建立搜尋二元樹>