二叉查找树

代码实现了二叉树的创建、查找、插入、删除、遍历。

以下着重说删除，分3种情况：
case 1：要删除的节点t即有左子树又有右子树，如图c的node 5
case 2：要删除的节点即没左子树又没右子树，如图a的node 13
case 3：要删除的节点有单支子树，或左或右，如图b的node 16或node 10，另外也要注册被删除节点是父亲的左还是右子树

点击(此处)折叠或打开

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct BiTree {
   
5.     int data;
   
6.     struct BiTree* lchild;
   
7.     struct BiTree* rchild;
   
8. }BST;
   
9. 
   
10. void visit_node(BST* t)
    
11. {
    
12.     if(t != NULL)
    
13.         printf("%d\n", t->data);
    
14. }
    
15. 
    
16. /* 遍历整个树，中序遍历 */
    
17. void traverse_tree(BST* t)
    
18. {
    
19.     if(t == NULL)
    
20.         return;
    
21.     traverse_tree(t->lchild);
    
22.     visit_node(t);
    
23.     traverse_tree(t->rchild);
    
24. }
    
25. #if 0
    
26. /* 插入节点，递归方法 */
    
27. BST* insert_node_recursion(BST** t, int v)
    
28. {
    
29.     if(*t == NULL) {
    
30.         *t = (BST*)malloc(sizeof(BST));
    
31.         (*t)->data = v;
    
32.         (*t)->lchild = (*t)->rchild = NULL;
    
33.         return *t;
    
34.     }
    
35.     
    
36.     if (v < (*t)->data)
    
37.         (*t)->lchild = insert_node_recursion(&((*t)->lchild), v);
    
38.     else
    
39.         (*t)->rchild = insert_node_recursion(&((*t)->rchild), v);
    
40.     
    
41.     return *t;
    
42. }
    
43. #else
    
44. /* 插入节点，递归方法 */
    
45. BST* insert_node_recursion(BST* t, int v)
    
46. {
    
47.     if(t == NULL) {
    
48.         BST* n;
    
49.         n = (BST*)malloc(sizeof(BST));
    
50.         n->data = v;
    
51.         n->lchild = n->rchild = NULL;
    
52.         return n;
    
53.     }
    
54.     
    
55.     if (v < t->data)
    
56.         t->lchild = insert_node_recursion(t->lchild, v);
    
57.     else if(v > t->data)
    
58.         t->rchild = insert_node_recursion(t->rchild, v);
    
59. 
    
60.     return t;
    
61. }
    
62. #endif
    
63. 
    
64. /* 插入节点，普通方法 */
    
65. BST* insert_node_normal(BST* t, int v)
    
66. {
    
67.     BST* pre = NULL;
    
68.     BST* new = NULL;
    
69.     BST* head = t;
    
70.     int l, r;
    
71.     
    
72.     while(t && t->data != v) {
    
73.         pre = t;
    
74.         l = r = 0;
    
75.         if(v < t->data) {
    
76.             l = 1;
    
77.             t = t->lchild;
    
78.         } else {
    
79.             r = 1;
    
80.             t = t->rchild;
    
81.         }
    
82.     }
    
83.     
    
84.     new = (BST*)malloc(sizeof(BST));
    
85.     new->data = v;
    
86.     new->lchild = new->rchild = NULL;
    
87.     
    
88.     if (pre != NULL)
    
89.         l ? (pre->lchild = new) : (pre->rchild = new);
    
90.     
    
91.     if(head == NULL)
    
92.         return new;
    
93.     else
    
94.         return head;
    
95. }
    
96. 
    
97. /* 查找节点 */
    
98. BST* search_node(BST* t, int v)
    
99. {
    
100.     int level = 0;
     
101.     
     
102.     while (t) {
     
103.         level++;        
     
104.         if(v == t->data) {
     
105.             printf("found it, deep level is %d\n", level);
     
106.             break;
     
107.         } else if(v < t->data)
     
108.             t = t->lchild;
     
109.         else
     
110.             t = t->rchild;
     
111.     }
     
112.     
     
113.     if(!t) {
     
114.         printf("node %d is not exist.\n", v);
     
115.         return NULL;
     
116.     } else
     
117.         return t;
     
118. }
     
119. 
     
120. /* 删除节点 */
     
121. void delete_node(BST* t, int v)
     
122. {
     
123.     BST* pre = NULL;
     
124.     BST* find = NULL;
     
125.     BST* parent = NULL;
     
126.     BST* most_left = NULL;
     
127.     int l, r;
     
128.     
     
129.     while (t) {
     
130.         if(v == t->data) {    //找到要删除的这个节点了
     
131.             find = t;
     
132.             if(t->lchild && t->rchild) {    //case 1：要删除的节点t即有左子树又有右子树，删除过程总3步
     
133. 
     
134.                 //找到t的右子树里的最左节点 @1步
     
135.                 t = t->rchild;
     
136.                 while (t->lchild) {            
     
137.                     parent = t;                //记录最左结点的父亲
     
138.                     t = t->lchild;
     
139.                 }
     
140.                 most_left = t;
     
141.                 
     
142.                 //最左节点代替被删除节点t的位置 @2步
     
143.                 find->data = most_left->data;
     
144.                 
     
145.                 //上面有人被删除带走，最左节点升职上去了，所以要重新调整下最左节点的上下关系，并删除其占用的空间 @3步
     
146.                 if (most_left->rchild)
     
147.                     parent->lchild = most_left->rchild;
     
148.                 else
     
149.                     parent->lchild = NULL;
     
150.                 free(most_left);
     
151.                 most_left = NULL;
     
152.                 
     
153.                 break;
     
154.             }
     
155.             else if(!t->lchild && !t->rchild)    //case 2：要删除的节点即没左子树又没右子树
     
156.                 //l为真表示要删除的节点是父亲的左孩子，所以把左子树指针置空，否则置空右子树指针
     
157.                 l ? (pre->lchild = NULL) : (pre->rchild = NULL);
     
158.                 
     
159.             else if(t->lchild)                    //case 3：要删除的节点有左子树
     
160.                 //要删除的结点为t，t的父亲是pre，t有个左儿子是t->lchild
     
161.                 //t被带走了，所以把t的孩子过继给t的父亲pre，也就是爷爷来带孙子
     
162.                 //那么爷爷是左胳膊牵着孙子走还是右胳膊呢，那得看t是pre的左孩子还是右孩子
     
163.                 //l为真表示要删除的节点t是父亲pre的左孩子，所以把t的孩子过继给父亲pre的左子树，否则就过继给右子树
     
164.                 l ? (pre->lchild = t->lchild) : (pre->rchild = t->lchild);
     
165.                 
     
166.             else if(t->rchild)                    //case 4：要删除的节点有右子树
     
167.                 //同case 3一样，都是过继孙子给爷爷的故事，只不过这个是右孩子，case 3是左孩子
     
168.                 r ? (pre->rchild = t->rchild) : (pre->lchild = t->rchild);
     
169.             
     
170.             free(find);
     
171.             find = NULL;
     
172.             break;
     
173.         } else if(v < t->data) {
     
174.             pre = t;    //pre代表当前节点的父亲
     
175.             l = 1;        //l变量为真表示当前节点是父亲节点的左子树
     
176.             r = 0;
     
177.             t = t->lchild;
     
178.         } else {
     
179.             pre = t;
     
180.             r = 1;        //r变量为真表示当前节点是父亲节点的右子树
     
181.             l = 0;
     
182.             t = t->rchild;
     
183.         }
     
184.     }
     
185. }
     
186. 
     
187. /* 创建二叉查找树 */
     
188. void create_bitree(BST** t, int *d, int len)
     
189. {
     
190.     int i;
     
191.     
     
192.     for(i = 0; i < len; i++)
     
193. //        *t = insert_node_recursion(*t, d[i]);
     
194.         *t = insert_node_normal(*t, d[i]);
     
195. }
     
196. 
     
197. void main(void)
     
198. {
     
199.     //T是整个树的根
     
200.     BST* T = NULL;
     
201.     int n = 0;
     
202. //    int d[] = {4, 13, 3, 9, 28, 6};
     
203.     int d[] = {4, 13, 3, 9};
     
204.     
     
205.     while(d[n++] != 0);
     
206. 
     
207.     create_bitree(&T, d, n - 1);
     
208. //    insert_node_recursion(T, 15);
     
209.     insert_node_normal(T, 15);
     
210.     traverse_tree(T);
     
211.     printf("\n\n");
     
212. //    search_node(T, 9);
     
213.     delete_node(T, 4);
     
214.     traverse_tree(T);
     
215. }