面试题23：二叉搜索树的查找、插入、删除

BST的查找非常简单，插入是基于查找进行的，有一点需要注意的是插入一定是称为叶子节点的孩子节点。删除稍微麻烦一点，要分情况讨论，当要删除的节点有两个孩子节点时，首先寻找要删除节点p的左子树的最大的节点s，然后交换p和s的数值，调整s父节点的指向，删除s节点。

 1 /search x on a BST,return the node's pointer
 2 TreeNode* searchBST(TreeNode* root,int x){
 3     if(root == nullptr) return nullptr;
 4     if(root->val == x) return root;
 5     if(x > root->val) return searchBST(root->right,x);
 6     if(x < root->val) return searchBST(root->left,x);
 7     return nullptr;
 8 }
 9 
10 TreeNode* searchBST2(TreeNode* root,int x){
11     TreeNode* p = root;
12     while(p){
13         if(x == p->val) return p;
14         else if(x > p->val) {
15             p = p->right;
16         }else{
17             p = p->left;
18         }
19     }
20     return nullptr;
21 }
22 
23 //if bst has x return false,else insert and return true;
24 bool insertBST(TreeNode* root,int x){
25     TreeNode* p = root;
26     TreeNode* pre = nullptr;
27     while(p){
28         if(x == p->val){
29             return false;
30         }else if(x > p->val){
31             pre = p;
32             p = p->right;
33         }else{
34             pre = p;
35             p = p->left;
36         }
37     }
38     TreeNode* px = new TreeNode(x);
39     if(pre == nullptr){
40         root = px;
41     }else if(x < pre->val){
42         pre->left = px;
43     }else{
44         pre->right = px;
45     }
46     return true;
47 }
48 
49 
50 void removerBST(TreeNode* root,int x){
51     if(root == nullptr) return;
52     TreeNode* p = root;
53     TreeNode* pp = nullptr;
54     while(p){
55         if(p->val == x){{
56             break;
57         }
58         }else if(x > p->val){
59             pp = p;
60             p = p->right;
61         }else{
62             pp = p;
63             p = p->left;
64         }
65     }
66 
67     if(p == nullptr) return;  //not found!
68 
69     //when p has two child
70     if(p->left && p->right){
71         TreeNode* s = p->left;
72         TreeNode* ps = p;
73         while(s->right){
74             ps = s;
75             s = s->right;
76         }
77         std::swap(p->val,s->val);
78         if(s == ps->right) ps->right = s->left;
79         else if(s == ps->left) ps->left = s->left;
80         delete s;
81         return;
82     }
83 
84     //when p has one or zero child
85     TreeNode* c = nullptr;
86     if(p->left) c = p->left;
87     if(p->right) c = p->right;
88     if(p==root){
89         root = c;
90     }else{
91         if(p == pp->left){
92             pp->left = c;
93         }else{
94             pp->right = c;
95         }
96         delete p;
97     }
98 
99 }