面试：实现二叉搜索树的查找、插入和删除操作

  1 #include <iostream>
  2 
  3 struct BSTNode {
  4     int key;
  5     BSTNode* left;
  6     BSTNode* right;
  7     BSTNode(int x) : key(x), left(nullptr), right(nullptr) {
  8     }
  9 };
 10 
 11 //recursive
 12 BSTNode* search(BSTNode* root, int key) {
 13     if (root == nullptr)
 14         return nullptr;
 15     if (root->key == key)
 16         return root;
 17     else if (key < root->key)
 18         search(root->left, key);
 19     else
 20         search(root->right, key);
 21     return root;
 22 }
 23 
 24 BSTNode* search2(BSTNode* root, int key) {
 25     if (root == nullptr)
 26         return nullptr;
 27     BSTNode* cur = root;
 28 
 29     while (cur) {
 30         if (cur->key == key)
 31             break;
 32         else if (key < cur->key)
 33             cur = cur->left;
 34         else
 35             cur = cur->right;
 36     }
 37     return cur;
 38 }
 39 
 40 //return true or false;
 41 BSTNode* insert(BSTNode* root, int key) {
 42     BSTNode* insertNode = new BSTNode(key);
 43 
 44 
 45     if (root == nullptr) {
 46         root = insertNode;
 47     }
 48 
 49     BSTNode* cur = root;
 50     BSTNode* parent = nullptr;
 51     while (cur) {
 52         //when same key,false means insert failed.
 53         if (cur->key == key) return root;
 54         parent = cur;
 55 
 56         if (key < cur->key)
 57             cur = cur->left;
 58         else
 59             cur = cur->right;
 60     }
 61 
 62     if(key < parent->key){
 63         parent->left = insertNode;
 64     }else{
 65         parent->right = insertNode;
 66     }
 67     return root;
 68 }
 69 
 70 //假设要删除的节点是p，
 71 //分为三种情况：1）p是树叶；2）p只有一棵非空子树；3）p有两颗非空子树
 72 BSTNode* erase(BSTNode* root, int key) {
 73     if (root == nullptr)
 74         return nullptr;
 75 
 76     if(key < root->key){
 77         root->left = erase(root->left,key);
 78     }else if(key > root->key){
 79         root->right = erase(root->right,key);
 80     }else{
 81         if(root->left == nullptr &&  root->right == nullptr){
 82             delete root;
 83             root = nullptr;
 84         }else if(root->left){
 85             BSTNode* p = root->left;
 86             while(p->right){
 87                 p = p->right;
 88             }
 89             root->key = p->key;
 90             root->left = erase(root->left,root->key);
 91         }else{
 92             BSTNode* p = root->right;
 93             while(p->left){
 94                 p = p->left;
 95             }
 96             root->key = p->key;
 97             root->right = erase(root->right,root->key);
 98         }
 99     }
100     return root;
101 }
102 
103 void print(BSTNode* root){
104     if(root == nullptr) return;
105     print(root->left);
106     std::cout << root->key << '	';
107     print(root->right);
108 }
109 
110 int main(){
111     BSTNode* root = new BSTNode(3);
112     insert(root,5);
113     insert(root,4);
114     insert(root,2);
115     print(root);
116     std::cout << std::endl;
117     erase(root,4);
118     print(root);
119     return 0;
120 }