算法: 二叉树增、删、查、找详解编程语言

  1 #include <stdio.h> 
  2 #include <string.h> 
  3  
  4 struct Node{ 
  5     Node *left; 
  6     Node *right; 
  7     int key; 
  8 }; 
  9  
 10 Node* create_node(const int key){ 
 11     Node *tmp = new Node; 
 12     tmp->left = NULL; 
 13     tmp->right = NULL; 
 14     tmp->key = key; 
 15     return tmp; 
 16 } 
 17  
 18 Node* search_node(Node *node, const int key){ 
 19     if (node == NULL){ 
 20         return NULL;     
 21     }    
 22      
 23     Node *tmp = node; 
 24     while(tmp != NULL){ 
 25         if (tmp->key == key){ 
 26             break; 
 27         }    
 28         else{ 
 29             tmp = (tmp->key < key)? tmp->right:tmp->left; 
 30         }    
 31     }    
 32  
 33     return tmp; 
 34 } 
 35  
 36 void insert_node(Node **root, const int key){ 
 37     if (*root == NULL){ 
 38         *root = create_node(key); 
 39         return; 
 40     }    
 41  
 42     Node *pre = NULL; 
 43     Node *tmp = *root; 
 44  
 45     while(tmp != NULL){ 
 46         if (tmp->key == key){ 
 47             return; 
 48         } 
 49         else{ 
 50             pre = tmp; 
 51             tmp = (tmp->key < key)? tmp->right:tmp->left; 
 52         } 
 53     } 
 54  
 55     tmp = create_node(key); 
 56     if (pre->key < key){ 
 57         pre->right = tmp; 
 58     } 
 59     else { 
 60         pre->left = tmp; 
 61     } 
 62     return; 
 63 } 
 64  
 65 void del_node(Node** root, int val){ 
 66     Node* pre = NULL; 
 67     Node* curr = *root; 
 68     while(curr && curr->key != val){ 
 69         pre = curr; 
 70         curr = (val <= curr->key) ? curr->left:curr->right; 
 71     }    
 72  
 73     if (curr == NULL){ 
 74         printf("delete node not exist/n"); 
 75         return ; 
 76     }    
 77  
 78     if (curr->left == NULL && curr->right == NULL){ //删除节点是叶子节点 
 79         if (pre == NULL){ 
 80             Node* tmp = *root; 
 81             delete *root; 
 82             *root = NULL; 
 83         }    
 84         else { 
 85             if (pre->left == curr){ 
 86                 pre->left = NULL; 
 87             }    
 88             else { 
 89                 pre->right = NULL; 
 90             }    
 91             delete curr; 
 92         }    
 93     }    
 94     else if (curr->left == NULL || curr->right == NULL){    //删除节点只有一个孩子节点 
 95         if (curr->left != NULL){    //如果只存在left节点 
 96             if(pre == NULL){ 
 97                 *root = curr->left; 
 98             }    
 99             else { 
100                 if (pre->left == curr){ 
101                     pre->left = curr->left; 
102                 }    
103                 else { 
104                     pre->right = curr->left; 
105                 } 
106             } 
107             delete curr; 
108         } 
109         else{   //如果只存在right节点 
110             if (pre == NULL) { 
111                 *root = curr->right; 
112             } 
113             else { 
114                 if (pre->right == curr){ 
115                     pre->left = curr->right; 
116                 } 
117                 else{ 
118                     pre->right = curr->right; 
119                 } 
120             } 
121             delete curr; 
122         } 
123     } 
124     else if (curr->left != NULL && curr->right != NULL){    //删除节点left, right都存在 
125         Node* pp = curr; 
126         Node* p  = curr->right; 
127         while(p->left != NULL){ 
128             pp = p; 
129             p  = p->left; 
130         } 
131  
132         curr->key = p->key; 
133         if (curr == pp){ 
134             curr->right = p->right; 
135         } 
136         else{ 
137             pp->left = p->right; 
138         } 
139         delete p; 
140     } 
141  
142     return ; 
143 } 
144  
145 void del_tree(Node *root){ 
146     if (root->left != NULL){ 
147         del_tree(root->left); 
148     } 
149  
150     if (root->right != NULL){ 
151         del_tree(root->right); 
152     } 
153  
154     if (root){ 
155         delete root; 
156     } 
157 } 
158  
159 int main(){ 
160     Node *root = NULL; 
161     int cmd_no; 
162     int key; 
163     while(true){ 
164         printf("items list:/n"); 
165         printf("1. Search/n"); 
166         printf("2. Insert/n"); 
167         printf("3. Delete/n"); 
168         printf("4. Quit/n"); 
169         printf("input cmd:"); 
170  
171         scanf("%d", &cmd_no); 
172         if (cmd_no == 4){ 
173             break; 
174         } 
175         scanf("%d", &key); 
176         switch(cmd_no){ 
177             case 1:{ 
178                 if (search_node(root, key)){ 
179                     printf("exist/n"); 
180                 } 
181                 else { 
182                     printf("not exist/n"); 
183                 } 
184                 break; 
185             } 
186             case 2:{ 
187                 insert_node(&root, key); 
188                 break; 
189             } 
190             case 3:{ 
191                 del_node(&root, key); 
192                 break; 
193             } 
194             default: { 
195                 printf("input error"); 
196             } 
197         } 
198     } 
199  
200     del_tree(root); 
201     return 0; 
202 }