算法: 二叉树增、删、查、找

最近写个任务与二叉树相关。
这里记录一下二叉树相关代码。后续可以使用。
  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
");
 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:
");
165         printf("1. Search
");
166         printf("2. Insert
");
167         printf("3. Delete
");
168         printf("4. Quit
");
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
");
180                 }
181                 else {
182                     printf("not exist
");
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 }