@Author: 张海拔
@Update: 2014-01-24
@Link: http://www.cnblogs.com/zhanghaiba/p/3532885.html
1 /* 2 *Author: ZhangHaiba 3 *Date: 2014-1-24 4 *File: binary_search_tree_iter.c 5 * 6 *this demo shows how to build a BST data structure 7 *and support some command line to operate this BST 8 *such like i(insert), d(delete), s(search), q(quit) etc 9 *interestingly, this demo use tree module which written by Greg Lee 10 *making BST data structure and it‘s opreation visualization 11 * 12 *hint: implementation iterative 13 */ 14 15 #include <stdio.h> 16 #include <stdlib.h> 17 #include <stdbool.h> 18 #define MOD 256 19 #define CMD_LEN 128 20 21 typedef struct node* link; 22 23 typedef struct node { 24 int item; 25 link left; 26 link right; 27 }node; 28 29 //public 30 link NODE(int item, link left, link right); //as constructor 31 link bst_insert(link root, int item); 32 link bst_delete(link root, int item); 33 link bst_search(link root, int item); 34 void bst_inorder(link root); 35 void bst_show_by_tree(link root); 36 //private 37 link* pre(link root); 38 link* next(link root); 39 void inorder(link root); //included in bst_inorder() 40 void tree_print(link root, FILE* fd); //included in bst_show_by_tree() 41 42 int main(void) 43 { 44 45 link r = NULL; //BST root 46 47 //operating this the BST r 48 49 /*** Command Line Manual ***/ 50 /* 51 * "i 100" means insert item which value 100 52 * "d 200" means delete item which value 200 53 * "s 300" means search item which value 300 54 * "p" means call the tree module to print the BST tree 55 * "l" means list the inorder list of BST 56 * "q" means quit 57 */ 58 59 while (true) { 60 char cmd[CMD_LEN]; 61 62 scanf("%s", cmd); 63 if (cmd[0] == ‘q‘) 64 break; 65 else if (cmd[0] == ‘i‘ || cmd[0] == ‘d‘ || cmd[0] == ‘s‘) { 66 int item; 67 scanf("%d", &item); 68 if (cmd[0] == ‘i‘) 69 r = bst_insert(r, item); 70 else if (cmd[0] == ‘d‘) 71 r = bst_delete(r, item); 72 else { 73 link aim_link = bst_search(r, item); 74 if (aim_link == NULL) 75 printf("Not Found!\n"); 76 else 77 printf("Found: %d\n", aim_link->item); 78 } 79 } 80 else if (cmd[0] == ‘p‘) 81 bst_show_by_tree(r); 82 else if (cmd[0] == ‘l‘) 83 bst_inorder(r); 84 else 85 ; //ingnore illegal command line 86 } 87 return 0; 88 } 89 90 link NODE(int item, link left, link right) 91 { 92 link born = malloc(sizeof (node)); 93 born->item = item; 94 born->left = left; 95 born->right = right; 96 return born; 97 } 98 99 link bst_insert(link root, int item) 100 { 101 if (root == NULL) 102 return NODE(item, NULL, NULL); 103 link p = root; 104 while (true) { 105 if (item < p->item) { 106 if (p->left != NULL) 107 p = p->left; 108 else { 109 p->left = NODE(item, NULL, NULL); 110 return root; 111 } 112 } else if (item > p->item) { 113 if (p->right != NULL) 114 p = p->right; 115 else { 116 p->right = NODE(item, NULL, NULL); 117 return root; 118 } 119 } else 120 return root; 121 } 122 } 123 124 link bst_delete(link root, int item) 125 { 126 if (root == NULL) 127 return NULL; 128 link save = root; 129 link *p = &root; 130 while (true) { 131 if (item < (*p)->item) { 132 if ((*p)->left != NULL) 133 p = &((*p)->left); 134 else 135 return save; //if search failed then delete nothing 136 } else if (item > (*p)->item) { 137 if ((*p)->right != NULL) 138 p = &((*p)->right); 139 else 140 return save; 141 } else { 142 if ((*p)->left != NULL) { 143 link *q = pre(*p); 144 (*p)->item = (*q)->item; 145 link del = (*q); 146 (*q) = (*q)->left; 147 free(del); 148 } else if ((*p)->right != NULL) { 149 link *q = next(*p); 150 (*p)->item = (*q)->item; 151 link del = (*q); 152 (*q) = (*q)->right; 153 free(del); 154 } else { 155 free(*p); 156 if (*p == save) //guarantee delete BST those have only one node 157 save = NULL; 158 *p = NULL; 159 } 160 return save; 161 } 162 } 163 } 164 165 link bst_search(link root, int item) 166 { 167 if (root == NULL) 168 return NULL; 169 link p = root; 170 while (true) { 171 if (item < p->item) { 172 if (p->left != NULL) 173 p = p->left; 174 else 175 return NULL; 176 } else if (item > p->item) { 177 if (p->right != NULL) 178 p = p->right; 179 else 180 return NULL; 181 } else 182 return p; 183 } 184 } 185 186 //has grantee root != NULL 187 link* pre(link root) 188 { 189 link *p = &(root->left); 190 191 while ((*p)->right != NULL) 192 p = &((*p)->right); 193 return p; 194 } 195 196 //has grantee root != NULL 197 link* next(link root) 198 { 199 link *p = &(root->right); 200 201 while ((*p)->left != NULL) 202 p = &((*p)->left); 203 return p; 204 } 205 206 void bst_inorder(link root) 207 { 208 inorder(root); 209 printf("\n"); 210 } 211 212 void inorder(link root) 213 { 214 if (root == NULL) 215 return; 216 inorder(root->left); 217 printf("%d ", root->item); 218 inorder(root->right); 219 } 220 221 void bst_show_by_tree(link root) 222 { 223 char cmd[CMD_LEN]; 224 225 sprintf(cmd, "rm -f ./tree_src.txt"); 226 system(cmd); 227 228 FILE *fd = fopen("./tree_src.txt", "a+"); 229 fprintf(fd, "\n\t\\tree"); 230 tree_print(root, fd); 231 fprintf(fd, "\n\n"); 232 fclose(fd); 233 234 sprintf(cmd, "cat ./tree_src.txt | ~/tree/tree"); 235 system(cmd); 236 } 237 238 void tree_print(link root, FILE *fd) 239 { 240 fprintf(fd, "("); 241 if (root != NULL) { 242 fprintf(fd, "%d", root->item); 243 tree_print(root->left, fd); 244 tree_print(root->right, fd); 245 } 246 fprintf(fd, ")"); 247 }
测试示范：
ZhangHaiba-MacBook-Pro:code apple$ ./a.out p i 50 p 50 _|__ | | i 45 i 55 p 50 ___|___ | | 45 55 _|__ _|__ | | | | i 35 i 36 i 39 i 38 l 35 36 38 39 45 50 55 i 70 i 68 i 61 i 65 i 62 i 67 p 50 ____|____ | | 45 55 _|__ __|___ | | | | 35 70 _|__ _|__ | | | | 36 68 _|__ _|__ | | | | 39 61 _|__ _|__ | | | | 38 65 _|__ ___|___ | | | | 62 67 _|__ _|__ | | | | l 35 36 38 39 45 50 55 61 62 65 67 68 70 s 66 Not Found! s 62 Found: 62 s 39 Found: 39 s 37 Not Found! d 62 p 50 ____|____ | | 45 55 _|__ __|___ | | | | 35 70 _|__ _|__ | | | | 36 68 _|__ _|__ | | | | 39 61 _|__ _|__ | | | | 38 65 _|__ _|__ | | | | 67 _|__ | | d 45 p 50 ____|____ | | 39 55 _|__ __|___ | | | | 35 70 _|__ _|__ | | | | 36 68 _|__ _|__ | | | | 38 61 _|__ _|__ | | | | 65 _|__ | | 67 _|__ | | d 55 p 50 ____|____ | | 39 61 _|__ __|___ | | | | 35 70 _|__ _|__ | | | | 36 68 _|__ _|__ | | | | 38 65 _|__ _|__ | | | | 67 _|__ | | d 39 p 50 ___|___ | | 38 61 _|__ _|__ | | | | 35 70 _|__ _|__ | | | | 36 68 _|__ _|__ | | | | 65 _|__ | | 67 _|__ | | d 61 p 50 ___|___ | | 38 65 _|__ _|__ | | | | 35 70 _|__ _|__ | | | | 36 68 _|__ _|__ | | | | 67 _|__ | | d 50 p 38 ___|___ | | 35 65 _|__ _|__ | | | | 36 70 _|__ _|__ | | | | 68 _|__ | | 67 _|__ | | d 38 d 68 d 70 d 35 d 36 d 67 p 65 _|__ | | d 65 p i 99 p 99 _|__ | | q