1 //二叉查找树   递归实现  插入，删除和查找
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 
  5 typedef struct Node {
  6     int val;
  7     struct Node* left;
  8     struct Node* right;
  9 }Node;
 10 typedef int bool;
 11 
 12 Node * Find(Node* root,int a);   //如果找到了返回指针 如果找不到则返回空指针
 13 Node *Insert(Node* root, int a);  //将a插入到root中并且返回根节点指针
 14 Node *Delete(Node* root,int a);   //将a从root中删除并且返回根节点指针    
 15 Node* FindMin(Node* root);//找到最小节点并且返回该节点的指针
 16 Node* FindMax(Node* root);//找到最大节点并且返回该节点的指针
 17 void PreorderTraversal(Node* root); //先序遍历
 18 int main(){
 19     Node* root = (Node*)malloc(sizeof(Node));//根节点
 20     Node * BST, *MinP, *MaxP, *Tmp;   //分别是树根节点   最小节点 最大节点 和一个临时用的节点指针变量
 21     int X;
 22     int N, i;
 23     BST = NULL;
 24     scanf("%d", &N);//插入节点
 25     for (i = 0; i < N; i++) {
 26         scanf("%d", &X);
 27         BST = Insert(BST, X);
 28     }
 29     printf("Preorder:"); PreorderTraversal(BST); printf("\n");//先序遍历
 30     MinP = FindMin(BST);
 31     MaxP = FindMax(BST);
 32     scanf("%d", &N);//查找节点
 33     for (i = 0; i < N; i++) {
 34         scanf("%d", &X);
 35         Tmp = Find(BST, X);
 36         if (Tmp == NULL) printf("%d is not found\n", X);
 37         else {
 38             printf("%d is found\n", Tmp->val);
 39             if (Tmp == MinP) printf("%d is the smallest key\n", Tmp->val);
 40             if (Tmp == MaxP) printf("%d is the largest key\n", Tmp->val);
 41         }
 42     }
 43     scanf("%d", &N);//删除节点
 44     for (i = 0; i < N; i++) {
 45         scanf("%d", &X);
 46         BST = Delete(BST, X);
 47     }
 48     printf("Preorder:"); PreorderTraversal(BST); printf("\n");//先序遍历
 49     return 0;
 50 }
 51 
 52 Node *Find(Node* root,int a) { //查找
 53     if (!root) return NULL;
 54     if (a == root->val) {
 55         return root;
 56     }
 57     else if (a > root->val) {
 58         return Find(root->right, a);
 59     }
 60     else {//a< root->val
 61         return Find(root->left, a);
 62     }
 63     return NULL;//实际上这一行是没有必要的
 64 }
 65 Node *Insert(Node* root, int a) {
 66     if (!root) {
 67         Node* newNode = (Node*)malloc(sizeof(Node));
 68         newNode->val = a;
 69         newNode->left = newNode->right = NULL;
 70         return newNode;
 71     }
 72     else if (a > root->val) {
 73         root->right = Insert(root->right, a);
 74     }
 75     else if (a < root->val) {
 76         root->left = Insert(root->left, a);
 77     }
 78     else {
 79         //这时候root的节点值等于a则不处理
 80     }
 81     return root;
 82 }
 83 Node* Delete(Node* root, int a) {
 84     if (!root) return root;
 85     if (a < root->val)       root->left = Delete(root->left, a);
 86     else if(a > root->val)   root->right = Delete(root->right, a);
 87     else{  //找到这个节点  那么进行删除操作  此刻要考虑四种情况：左右空 左右非空 左空右非空 左非空右空
 88         if (!root->left) { Node* temp = root; root = root->right; free(temp); }
 89         else if (!root->right) { Node* temp = root; root = root->left;free(temp); }
 90         else {
 91             Node* temp = root->right;
 92             while (temp->left) {
 93                 temp = temp->left;
 94             }
 95             temp->left = root->left;
 96             root = root->right;
 97         }
 98     }
 99     return root;//这一句实际上没有必要
100 }
101 Node* FindMin(Node* root) {
102     if (!root) {
103         return NULL;
104     }
105     if (!root->left) {
106         return root;
107     }
108     return FindMin(root->left);
109 }
110 Node* FindMax(Node* root) {
111     if (!root) {
112         return NULL;
113     }
114     if (!root->right) {
115         return root;
116     }
117     return FindMax(root->right);
118 }
119 void PreorderTraversal(Node* root) {
120     if (!root) return;
121     printf("%d  ", root->val);
122     PreorderTraversal(root->left);
123     PreorderTraversal(root->right);
124 }

  1 #define _CRT_SECURE_NO_WARNINGS
  2 //二叉查找树   非递归实现  插入，删除和查找
  3 #include<stdio.h>
  4 #include<stdlib.h>
  5 
  6 typedef struct Node {
  7     int val;
  8     struct Node* left;
  9     struct Node* right;
 10 }Node;
 11 typedef int bool;
 12 
 13 Node * Find(Node* root,int a);   //如果找到了返回指针 如果找不到则返回空指针
 14 Node *Insert(Node* root, int a);  //将a插入到root中并且返回根节点指针
 15 Node *Delete(Node* root,int a);   //将a从root中删除并且返回根节点指针    
 16 Node* FindMin(Node* root);//找到最小节点并且返回该节点的指针
 17 Node* FindMax(Node* root);//找到最大节点并且返回该节点的指针
 18 void PreorderTraversal(Node* root); //先序遍历
 19 int main(){
 20     Node* root = (Node*)malloc(sizeof(Node));//根节点
 21     Node * BST, *MinP, *MaxP, *Tmp;   //分别是树根节点   最小节点 最大节点 和一个临时用的节点指针变量
 22     int X;
 23     int N, i;
 24     BST = NULL;
 25     scanf("%d", &N);//插入节点
 26     for (i = 0; i < N; i++) {
 27         scanf("%d", &X);
 28         BST = Insert(BST, X);
 29     }
 30     printf("Preorder:"); PreorderTraversal(BST); printf("\n");//先序遍历
 31     MinP = FindMin(BST);
 32     MaxP = FindMax(BST);
 33     scanf("%d", &N);//查找节点
 34     for (i = 0; i < N; i++) {
 35         scanf("%d", &X);
 36         Tmp = Find(BST, X);
 37         if (Tmp == NULL) printf("%d is not found\n", X);
 38         else {
 39             printf("%d is found\n", Tmp->val);
 40             if (Tmp == MinP) printf("%d is the smallest key\n", Tmp->val);
 41             if (Tmp == MaxP) printf("%d is the largest key\n", Tmp->val);
 42         }
 43     }
 44     scanf("%d", &N);//删除节点
 45     for (i = 0; i < N; i++) {
 46         scanf("%d", &X);
 47         BST = Delete(BST, X);
 48     }
 49     printf("Preorder:"); PreorderTraversal(BST); printf("\n");//先序遍历
 50     return 0;
 51 }
 52 Node *Find(Node* root,int a) { //查找
 53     if (!root) return NULL;
 54     while (root) {
 55         if (a == root->val) {
 56             break;
 57         }
 58         else if (a > root->val) {
 59             root = root->right;
 60         }
 61         else {//a< root->val
 62             root = root->left;
 63         }
 64     }
 65     return root;
 66 }
 67 Node *Insert(Node* root, int a) {
 68     if (!root) {
 69         root = (Node*)malloc(sizeof(Node));
 70         root->val = a;
 71         root->left = root->right = NULL;
 72     }
 73     else {
 74         Node* cur = root;
 75         Node* pre = NULL;
 76         while (cur) {
 77             if (a > cur->val) {
 78                 pre = cur;
 79                 cur = cur->right;
 80             }
 81             else if (a < cur->val) {
 82                 pre = cur;
 83                 cur = cur->left;
 84             }
 85             else {  
 86                 break;//找到了值为a的节点
 87             }
 88         }
 89         if (!cur) {  //如果没有找到 则插入
 90             if (a < pre->val) {
 91                 pre->left = (Node*)malloc(sizeof(Node));
 92                 pre->left->left = pre->left->right = NULL;
 93                 pre->left->val = a;
 94             }   
 95             else {
 96                 pre->right = (Node*)malloc(sizeof(Node));
 97                 pre->right->left = pre->right->right = NULL;
 98                 pre->right->val = a;
 99             }
100         }
101     }
102     return root;
103 }
104 Node* Delete(Node* root, int a) {//为什么代码这么长？因为没用到递归也没用到引用 就需要一个pre 
105     if (!root) return root;//根节点为空
106     Node* pre = NULL;
107     Node* cur = root;
108     while (cur) {
109         if (a < cur->val) {
110             pre = cur;
111             cur = cur->left;
112         }
113         else if (a > cur->val) {
114             pre = cur;
115             cur = cur->right;
116         }
117         else {
118             if ((!cur->left) && (!cur->right)) {
119                 if (!pre) {//cur为根节点
120                     free(cur);
121                     return pre;
122                 }
123                 if (a < pre->val) {
124                     pre->left = NULL;
125                 }
126                 else {
127                     pre->right = NULL;
128                 }
129                 return root;
130             }
131             else if (!cur->right) {
132                 if (!pre) {
133                     cur = cur->left;
134                     free(root);
135                     return cur;
136                 }
137                 if (a < pre->val) {
138                     pre->left = cur->left;
139                     free(cur);
140                 }
141                 else {
142                     pre->right = cur->left;
143                     free(cur);
144                 }
145                 return root;
146             }
147             else if (!cur->left) {
148                 if (!pre) {
149                     cur = cur->right;
150                     free(root);
151                     return cur;
152                 }
153                 if (a < pre->val) {
154                     pre->left = cur->right;
155                     free(cur);
156                 }
157                 else {
158                     pre->right = cur->right;
159                     free(cur);
160                 }
161                 return root;
162             }
163             else {  
164                 Node* temp = cur->left;
165                 while (temp->right) {
166                     temp = temp->right;
167                 }
168                 temp->right = cur->right;
169                 if (!pre) return cur->left;
170                 pre = cur->left;
171                 return root;
172             }
173         }
174     }
175     return root;
176 }
177 Node* FindMin(Node* root) {
178     if (!root) {
179         return NULL;
180     }
181     while (root->left) {
182         root = root->left;
183     }
184     return root;
185 }
186 Node* FindMax(Node* root) {
187     if (!root) {
188         return NULL;
189     }
190     while (root->right) {
191         root = root->right;
192     }
193     return root;
194 }
195 void PreorderTraversal(Node* root) {
196     if (!root) return;
197     printf("%d  ", root->val);
198     PreorderTraversal(root->left);
199     PreorderTraversal(root->right);
200 }