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 }
