二叉搜索树

  1 #include<iostream>
  2 using namespace std;
  3 template<class K,class V>
  4 struct BSTNode
  5 {
  6     K _key;
  7     V _value;
  8     BSTNode<K, V> *_left;
  9     BSTNode<K, V> *_right;
 10     BSTNode(const K&key,const V&value)
 11         :_key(key), _value(value), _left(NULL), _right(NULL)
 12     {}
 13 };
 14 
 15 template<class K, class V>
 16 class BSTree
 17 {
 18     typedef BSTNode<K, V>  Node;
 19 protected:
 20     Node* _root;
 21 public:
 22     BSTree() :_root(NULL)
 23     {}
 24     ~BSTree()
 25     {}
 26     void Inorder()
 27     {
 28         return _Inorder(_root);
 29         cout << endl;
 30     }
 31     bool Insert(const K&key, const V&value)
 32     {
 33         if (_root == NULL)
 34         {
 35             _root = new Node(key, value);
 36             return true;
 37         }
 38         Node *parent = NULL;
 39         Node *cur = _root;
 40         while (cur)
 41         {
 42             if (cur->_key < key)
 43             {
 44                 parent = cur;
 45                 cur = cur->_right;
 46             }
 47             else if (cur->_key > key)
 48             {
 49                 parent = cur;
 50                 cur = cur->_left;
 51             }
 52             else
 53             {
 54                 return false;
 55             }
 56 
 57             if (parent->_key < key)
 58             {
 59                 parent->_right = new Node(key, value);
 60             }
 61             else
 62             {
 63                 parent->_left = new Node(key, value);
 64             }
 65             return true;
 66         }
 67     }
 68 
 69 
 70     Node* Find(const K&key)
 71     {
 72         Node*cur = _root;
 73         while (cur)
 74         {
 75             if (cur->_key > key)
 76             {
 77                 cur = cur->_left;
 78             }
 79             else if (cur->_key < key)
 80             {
 81                 cur = cur->_right;
 82             }
 83             else
 84             {
 85                 return cur;
 86             }
 87         }
 88         return NULL;
 89     }
 90     bool Insert_R(const K&key, const V&value)
 91     {
 92         return _Insert_R(_root, key, value);
 93     }
 94 
 95     Node* Find_R(const K&key)
 96     {
 97         return _Find_R(_root, key);
 98     }
 99 
100     bool Remove_R(const K&key)
101     {
102         return _Remove_R(_root, key);
103     }
104 
105     bool Remove(const K&key)//非递归删除
106     {
107         return _Remove(_root, key);
108     }
109 
110 protected:
111     bool _Insert_R(Node*&root, const K&key, const V&value)
112     {
113         if (root == NULL)
114         {
115             root = new Node(key, value);
116             return true;
117         }
118         if (root->_key < key)
119         {
120             return _Insert_R(root->_right, key, value);
121         }
122         if (root->_key > key)
123         {
124             return _Insert_R(root->_left, key, value);
125         }
126         else
127         {
128             return false;
129         }
130     }
131 
132     Node* _Find_R(Node*&root, const K&key)
133     {
134         if (root == NULL)
135         {
136             return NULL;
137         }
138         if (root->_key < key)
139         {
140             return _Find_R(root->_right, key);
141         }
142         else if (root->_key>key)
143         {
144             return _Find_R(root->_left, key);
145         }
146         else
147         {
148             return root;
149         }
150     }
151 
152     bool _Remove_R(Node*& root, const K&key)
153     {
154         if (root == NULL)
155         {
156             return false;
157         }
158         else if (root->_key < key)
159         {
160             return _Remove_R(root->_right, key);
161         }
162         else if (root->_key > key)
163         {
164             return _Remove_R(root->_left, key);
165         }
166         else
167         {
168             Node* del = root;
169             if (root->_left == NULL)
170             {
171                 root = root->_right;
172             }
173             else if (root->_right == NULL)
174             {
175                 root = root->_left;
176             }
177             else
178             {
179                 Node* firstInorder = root->_right;
180                 while (firstInorder->_left)
181                 {
182                     firstInorder = firstInorder->_left;
183                 }
184                 swap(del->_key, firstInorder->_key);
185                 swap(del->_value, firstInorder->_value);
186                 return _Remove_R(root->_right, key);
187             }
188             delete del;
189         }
190     }
191 
192     bool _Remove(Node*& root, const K&key) //非递归删除
193     {
194         if (root == NULL)
195         {
196             return false;
197         }
198         if (root->_left == NULL&&root->_right == NULL)
199         {
200             delete root;
201             root = NULL;
202             return true;
203         }
204         Node* parent = NULL;
205         Node* del = root;
206         while (del)
207         {
208             if (del->_key < key)
209             {
210                 parent = del;
211                 del = del->_right;
212             }
213             else if (del->_key > key)
214             {
215                 parent = del;
216                 del = del->_left;
217             }
218             else
219             {
220                 break;
221             }
222         }
223         if (del)
224         {
225             if (del->_left == NULL)
226             {
227                 if (del == root)
228                 {
229                     root = del->_right;
230                 }
231                 else
232                 {
233                     if (del == parent->_left)
234                     {
235                         parent->_left = del->_right;
236                     }
237                     else
238                     {
239                         parent->_right = del->_right;
240                     }
241                 }
242             }
243             else if (del->_right == NULL)
244             {
245                 if (del == root)
246                 {
247                     root = del->_left;
248                 }
249                 else
250                 {
251                     if (del == parent->_left)
252                     {
253                         parent->_left = del->_left;
254                     }
255                     else
256                     {
257                         parent->_right = del->_left;
258                     }
259                 }
260             }
261             else
262             {
263                 Node* parent = del;
264                 Node* firstInorder = del->_right;
265                 while (firstInorder->_left)
266                 {
267                     parent = firstInorder;
268                     firstInorder = firstInorder->_left;
269                 }
270                 swap(del->_key, firstInorder->_key);
271                 swap(del->_value, firstInorder->_value);
272                 if (firstInorder == parent->_left)
273                 {
274                     parent->_left = firstInorder->_right;
275                 }
276                 else
277                 {
278                     parent->_right = firstInorder->_right;
279                 }
280                 delete del;
281                 del = NULL;
282                 return true;
283             }
284         }
285     }
286 
287     void _Inorder(Node* root)
288     {
289         if (root == NULL)
290         {
291             return;
292         }
293         else
294         {
295             _Inorder(root->_left);
296             cout << root->_key << " ";
297             _Inorder(root->_right);
298         }
299     }
300 };
301 void Test()
302 {
303     int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
304     BSTree<int, double> t;
305     for (size_t i = 0; i < sizeof(a) / sizeof(int);++i)
306     {
307         t.Insert_R(a[i], a[i]);
308     }
309     t.Inorder();
310     cout << endl;
311     cout<<t.Find(4);
312     cout << endl;
313     //t.Remove(4);
314     t.Remove(2);
315     /*t.Remove_R(1);
316     t.Remove_R(5);*/
317 
318     t.Inorder();
319     cout << endl;
320 }