二叉树之二叉搜索树（BSTree）

二叉搜索树（Binary Search Tree）

　　引用：https://www.cnblogs.com/skywang12345/

　　详解以后再补充。。。

　　代码含注释，下面是输出效果(msys2)

代码

开发环境：Qt Creator 4.8.2　　Mingw64 7.3　　windows 8.1

完整代码：https://github.com/Duacai/Data-Structure-and-Algorithms/tree/master/Data-Structure/Tree/BSTree

BSTree.h

  1 #ifndef BSTREE_H
  2 #define BSTREE_H
  3 
  4 #include <iostream>
  5 #include <queue>
  6 
  7 using namespace std;
  8 
  9 namespace Viclib
 10 {
 11 
 12 template < typename T >
 13 class BSTNode
 14 {
 15 public:
 16     T mKey;
 17     BSTNode<T>    *mLeft;
 18     BSTNode<T>    *mRight;
 19     BSTNode<T>    *mParent;
 20 
 21     BSTNode() = delete;
 22     BSTNode(const T& key, BSTNode<T> *left, BSTNode<T> *right, BSTNode<T> *parent);
 23     BSTNode(const BSTNode<T>& tree) = delete;
 24     BSTNode(BSTNode<T> && tree);
 25     BSTNode<T>& operator = (const BSTNode<T>& tree) = delete;
 26     BSTNode<T>& operator = (BSTNode<T> && tree);
 27     virtual ~BSTNode();
 28 };
 29 
 30 template < typename T >
 31 BSTNode<T>::BSTNode(const T& key, BSTNode<T> *left, BSTNode<T> *right, BSTNode<T> *parent) :
 32     mKey(key), mLeft(left), mRight(right), mParent(parent)
 33 {
 34 }
 35 
 36 template < typename T >
 37 BSTNode<T>::BSTNode(BSTNode<T> && tree)
 38 {
 39     mLeft = tree.mLeft;
 40     mRight = tree.mRight;
 41     mParent = tree.mParent;
 42 
 43     tree->mLeft = nullptr;
 44     tree->mRight = nullptr;
 45     tree->mParent = nullptr;
 46 }
 47 
 48 template < typename T >
 49 BSTNode<T>& BSTNode<T>::operator = (BSTNode<T> && tree)
 50 {
 51     if ( this == &tree )
 52         return *this;
 53     
 54     delete mLeft;
 55     delete mRight;
 56     delete mParent;
 57     
 58     mLeft = tree->mLeft;
 59     mRight = tree->mRight;
 60     mParent = tree->mParent;
 61 
 62     return *this;
 63 }
 64 
 65 template < typename T >
 66 BSTNode<T>::~BSTNode()
 67 {
 68 }
 69 
 70 template < typename T >
 71 class BSTree
 72 {
 73 protected:
 74     BSTNode<T>* mRoot;
 75     size_t mCount;
 76 
 77     virtual void preOrder(BSTNode<T> *tree) const;                                // 深度优先的前、中、后序遍历
 78     virtual void inOrder(BSTNode<T> *tree) const;
 79     virtual void postOrder(BSTNode<T> *tree) const;
 80 
 81     virtual void levelOrder(BSTNode<T> *tree) const;                            // 广度优先
 82 
 83     virtual BSTNode<T>* search(BSTNode<T> *tree, const T& key) const;            // 递归版搜索
 84     virtual BSTNode<T>* iterativeSearch(BSTNode<T> *tree, const T& key) const;    // 非递归版搜索
 85 
 86     virtual BSTNode<T>* minimum(BSTNode<T> *tree) const;                        // 获取最小最大值
 87     virtual BSTNode<T>* maximum(BSTNode<T> *tree) const;
 88 
 89     virtual BSTNode<T>* successor(BSTNode<T> *node) const;                        // 查找后继，即大于又最接近node的节点
 90     virtual BSTNode<T>* predecessor(BSTNode<T> *node) const;                    // 查找前继
 91 
 92     virtual void insert(BSTNode<T> *node);
 93     virtual BSTNode<T>* remove(BSTNode<T> *node);                                // 返回值用于删除，返回值实际是替换结点
 94     virtual void destroy(BSTNode<T> *tree);
 95 
 96     void printTree(BSTNode<T> *tree, bool firstNode) const;                        // 打印树，类似linux的tree命令
 97 
 98     virtual int height(BSTNode<T> *tree) const;                                    // 树的高度
 99     virtual int degree(BSTNode<T> *tree) const;                                    // 结点的度数
100 
101 public:
102     BSTree();
103     BSTree(const BSTree<T>&) = default;
104     BSTree(BSTree<T> &&) = default;
105     BSTree<T>& operator = (const BSTree<T>&) = default;
106     BSTree<T>& operator = (BSTree<T> &&) = default;
107     virtual ~BSTree();
108 
109     virtual void preOrder() const;
110     virtual void inOrder() const;
111     virtual void postOrder() const;
112 
113     virtual void levelOrder() const;
114 
115     virtual BSTNode<T>* search(const T& key) const;
116     virtual BSTNode<T>* iterativeSearch(const T& key) const;
117 
118     virtual const T& minimum() const;
119     virtual const T& maximum() const;
120 
121     virtual void insert(const T& key);
122     virtual void remove(const T& key);
123     virtual void destroy();
124 
125     virtual int height() const;
126     virtual int degree() const;
127 
128     virtual size_t getCount() const;
129 
130     virtual const T& getRootKey() const;
131     virtual void printTree() const;
132 };
133 
134 template < typename T >
135 BSTree<T>::BSTree() : mRoot(nullptr), mCount(0)
136 {
137 }
138 
139 template < typename T >
140 void BSTree<T>::preOrder(BSTNode<T> *tree) const
141 {
142     if ( tree != nullptr )
143     {
144         cout << tree->mKey << " " << flush;
145         preOrder(tree->mLeft);
146         preOrder(tree->mRight);
147     }
148 }
149 
150 template < typename T >
151 void BSTree<T>::preOrder() const
152 {
153     preOrder(dynamic_cast<BSTNode<T>*>(this->mRoot));
154 }
155 
156 template < typename T >
157 void BSTree<T>::inOrder(BSTNode<T> *tree) const
158 {
159     if ( tree != nullptr )
160     {
161         inOrder(tree->mLeft);
162         cout << tree->mKey << " " << flush;
163         inOrder(tree->mRight);
164     }
165 }
166 
167 template < typename T >
168 void BSTree<T>::inOrder() const
169 {
170     inOrder(dynamic_cast<BSTNode<T>*>(this->mRoot));
171 }
172 
173 template < typename T >
174 void BSTree<T>::postOrder(BSTNode<T> *tree) const
175 {
176     if ( tree != nullptr )
177     {
178         postOrder(tree->mLeft);
179         postOrder(tree->mRight);
180         cout << tree->mKey << " " << flush;
181     }
182 }
183 
184 template < typename T >
185 void BSTree<T>::postOrder() const
186 {
187     postOrder(dynamic_cast<BSTNode<T>*>(this->mRoot));
188 }
189 
190 template < typename T >
191 void BSTree<T>::levelOrder(BSTNode<T> *tree) const
192 {
193     if ( tree != nullptr )
194     {
195         queue<BSTNode<T>*> tmp;
196         tmp.push(tree);
197 
198         while( tmp.size() > 0 )
199         {
200             BSTNode<T>* t = tmp.front();
201             tmp.pop();
202 
203             if ( t->mLeft != nullptr )
204                 tmp.push(t->mLeft);
205 
206             if ( t->mRight != nullptr )
207                 tmp.push(t->mRight);
208 
209             cout << t->mKey << " " << flush;
210         }
211     }
212 }
213 
214 template < typename T >
215 void BSTree<T>::levelOrder() const
216 {
217     levelOrder(dynamic_cast<BSTNode<T>*>(this->mRoot));
218 }
219 
220 template < typename T >
221 BSTNode<T>* BSTree<T>::search(BSTNode<T> *node, const T& key) const
222 {
223     if ( node == nullptr || node->mKey == key )
224     {
225         return node;
226     }
227     else if ( key < node->mKey )
228         return search(dynamic_cast<BSTNode<T>*>(node)->mLeft, key);
229     else
230         return search(dynamic_cast<BSTNode<T>*>(node)->mRight, key);
231 }
232 
233 template < typename T >
234 BSTNode<T>* BSTree<T>::search(const T& key) const
235 {
236     return search(dynamic_cast<BSTNode<T>*>(this->mRoot), key);
237 }
238 
239 template < typename T >
240 BSTNode<T>* BSTree<T>::iterativeSearch(BSTNode<T>* node, const T& key) const
241 {
242     while ( (node != nullptr) && (node->mKey != key) )
243     {
244         if ( key < node->mKey )
245             node = node->mLeft;
246         else
247             node = node->mRight;
248     }
249 
250     return node;
251 }
252 
253 template < typename T >
254 BSTNode<T>* BSTree<T>::iterativeSearch(const T& value) const
255 {
256     return iterativeSearch(dynamic_cast<BSTNode<T>*>(this->mRoot), value);
257 }
258 
259 template < typename T >
260 BSTNode<T>* BSTree<T>::minimum(BSTNode<T>* tree) const
261 {
262     if ( tree == nullptr )
263         return nullptr;
264 
265     while ( tree->mLeft != nullptr )
266         tree = tree->mLeft;
267 
268     return tree;
269 }
270 
271 template < typename T >
272 const T& BSTree<T>::minimum() const
273 {
274     BSTNode<T> *p = minimum(dynamic_cast<BSTNode<T>*>(this->mRoot));
275 //    if ( p == nullptr )
276 //        THROW_EXCEPTION(EmptyTreeException, "The tree is empty ...");
277 
278     return p->mKey;
279 }
280 
281 template < typename T >
282 BSTNode<T>* BSTree<T>::maximum(BSTNode<T>* tree) const
283 {
284     if ( tree == nullptr )
285         return nullptr;
286 
287     while ( tree->mRight != nullptr )
288         tree = tree->mRight;
289 
290     return tree;
291 }
292 
293 template < typename T >
294 const T& BSTree<T>::maximum() const
295 {
296     BSTNode<T> *p = maximum(dynamic_cast<BSTNode<T>*>(this->mRoot));
297 //    if ( p == nullptr )
298 //        THROW_EXCEPTION(EmptyTreeException, "The tree is empty ...");
299 
300     return p->mKey;
301 }
302 
303 template < typename T >
304 BSTNode<T>* BSTree<T>::successor(BSTNode<T> *node) const    // 查找后继
305 {
306     if ( node->mRight != nullptr )                            // 如果node有右孩子，则在它的右孩子里面最小的是后继
307     {
308         return minimum(node->mRight);
309     }
310 
311     BSTNode<T>* ret = node->mParent;                        // 如果node没有右孩子，且它自身是左孩子，则它的父亲是后继
312     while ( (ret != nullptr) && (node == ret->mRight) )        // 如果node没有右孩子，且它自身是右孩子，它的最近祖先是左孩子的，则这个祖先的父亲就是后继
313     {
314         node = ret;
315         ret = ret->mParent;
316     }
317 
318     return ret;
319 }
320 
321 template < typename T >
322 BSTNode<T>* BSTree<T>::predecessor(BSTNode<T>* node) const    // 查找前继
323 {
324     if ( node->mLeft != nullptr )                            // 如果node有左孩子，则在它的左孩子里面最大的是前继
325         return maximum(node->mLeft);
326 
327     BSTNode<T>* ret = node->mParent;                        // 如果node没有左孩子，且它自身是右孩子，则它的父亲是后继
328     while ( (ret != nullptr) && (node == ret->mLeft) )        // 如果node没有左孩子，且它自身是左孩子，它的最近祖先是右孩子的，则这个祖先的父亲就是后继
329     {
330         node = ret;
331         ret = ret->mLeft;
332     }
333 
334     return ret;
335 }
336 
337 template < typename T >
338 void BSTree<T>::insert(BSTNode<T>* node)
339 {
340     BSTNode<T>* in = nullptr;                // 插入点
341     BSTNode<T>* parent = dynamic_cast<BSTNode<T>*>(this->mRoot);        // 插入点的父节点
342 
343     while ( parent != nullptr )                // 查找node的插入点
344     {
345         in = parent;
346         if ( node->mKey < in->mKey )        // 如果node结点小于插入点，则插入到左孩子分支
347             parent = parent->mLeft;
348         else if ( node->mKey > in->mKey )    // 如果node结点大于插入点，则插入到右孩子分支
349             parent = parent->mRight;
350         else                                // 如果数据等同则跳出
351             break;
352     }
353 
354     node->mParent = in;                    // 设置node结点的父亲为插入点
355     if ( in == nullptr )                // 如果插入点为空，设node结点为根节点
356         this->mRoot = node;
357     else if ( node->mKey < in->mKey )    // 如果node结点小于插入点，插入左边
358         in->mLeft = node;
359     else if ( node->mKey > in->mKey )    // 如果node结点大于插入点，插入右边
360         in->mRight = node;
361     else                                // 如果数据等同则直接替换并释放插入的结点
362     {
363         in->mKey = node->mKey;
364         delete node;
365         return;
366     }
367 
368     ++this->mCount;                        // 结点统计，注意重复结点插入时不能增加
369 }
370 
371 template < typename T >
372 void BSTree<T>::insert(const T& key)
373 {
374     insert(new BSTNode<T>(key, nullptr, nullptr, nullptr));
375 }
376 
377 template < typename T >
378 BSTNode<T>* BSTree<T>::remove(BSTNode<T> *node)
379 {
380     BSTNode<T>* replace = nullptr;            // 代替结点
381     BSTNode<T>* del = nullptr;                // 删除点
382 
383     if ( (node->mLeft == nullptr) || (node->mRight == nullptr) )    // 如果孩子不全，node就是删除点，可以直接用仅有的孩子代替
384         del = node;
385     else                                                            // 否则有两个孩子，后继就是删除点(右子树中最小的成员)
386     {
387         del = successor(node);                                        // 查找后继
388         node->mKey = del->mKey;                                        // 直接用后继key替换node的key
389     }
390 
391     if ( del->mLeft != nullptr )            // 如果有左孩子，则更新左孩子为代替结点（如果if成立就只有左孩子）
392         replace = del->mLeft;
393     else                                    // 否则设右孩子为代替结点
394         replace = del->mRight;
395 
396     if ( replace != nullptr )                // 如果代替结点不是空树，更新代替结点的父亲
397         replace->mParent = del->mParent;
398 
399     if ( del->mParent == nullptr )            // 如果结点是根节点且孩子不全，那就直接替换
400         this->mRoot = replace;
401     else if ( del == del->mParent->mLeft )    // 如果删除点为左孩子，则更新父节点的左孩子
402         del->mParent->mLeft = replace;
403     else                                    // 否则更新父节点的右孩子
404         del->mParent->mRight = replace;
405 
406     --this->mCount;
407 
408     return del;
409 }
410 
411 template < typename T >
412 void BSTree<T>::remove(const T& key)
413 {
414     BSTNode<T> *del = nullptr, *node;
415     del = search(dynamic_cast<BSTNode<T>*>(this->mRoot), key);
416 
417     if ( del != nullptr )                        // 找到的删除点不为空
418         if ( (node = remove(del)) != nullptr )    // 删除node并返回代替结点
419             delete node;                        // 删除代替结点
420 }
421 
422 template < typename T >
423 void BSTree<T>::destroy(BSTNode<T> *tree)
424 {
425     if ( tree == nullptr )
426         return;
427 
428     if ( tree->mLeft != nullptr )
429         destroy(tree->mLeft);
430 
431     if ( tree->mRight != nullptr )
432         destroy(tree->mRight);
433 
434     delete tree;
435     tree = nullptr;
436 }
437 
438 template < typename T >
439 void BSTree<T>::destroy()
440 {
441     destroy(dynamic_cast<BSTNode<T>*>(this->mRoot));
442     this->mRoot = nullptr;
443     this->mCount = 0;
444 }
445 
446 template < typename T >
447 int BSTree<T>::height(BSTNode<T>* node) const
448 {
449     int ret = 0;
450 
451     if( node != nullptr )
452     {
453         int lh = height(node->mLeft);
454         int rh = height(node->mRight);
455 
456         ret = ((lh > rh) ? lh : rh) + 1;
457     }
458 
459     return ret;
460 }
461 
462 template < typename T >
463 int BSTree<T>::height() const
464 {
465     int ret = 0;
466 
467     if( this->mRoot != nullptr )
468     {
469         ret = height(dynamic_cast<BSTNode<T>*>(this->mRoot));
470     }
471 
472     return ret;
473 }
474 
475 template < typename T >
476 int BSTree<T>::degree(BSTNode<T>* node) const
477 {
478     int ret = 0;
479 
480     if( node != nullptr )
481     {
482         BSTNode<T>* child[] = { node->mLeft, node->mRight };
483 
484         ret = (!!node->mLeft + !!node->mRight);        // 统计有效结点数，!!用于转换成bool类型，如果是有效结点则为1，否则为0
485 
486         for(int i=0; (i<2) && (ret<2); i++)            // 如果儿子不足2个需要检查
487         {
488             int d = degree(child[i]);
489 
490             if( ret < d )
491             {
492                 ret = d;
493             }
494         }
495     }
496 
497     return ret;
498 }
499 
500 template < typename T >
501 int BSTree<T>::degree() const
502 {
503     return degree(dynamic_cast<BSTNode<T>*>(this->mRoot));
504 }
505 
506 template < typename T >
507 size_t BSTree<T>::getCount() const
508 {
509     return this->mCount;
510 }
511 
512 template <typename T>
513 void BSTree<T>::printTree(BSTNode<T> *tree, bool firstNode) const
514 {
515     if ( tree == nullptr )
516         return;
517 
518     size_t height = this->height();                // 树的高度
519     static bool *outTag = new bool[height]();    // 左边是否还有结点的标记，初始化为false
520     uint8_t static layer = 0;                    // 当前层数，根结点为第一层
521     uint8_t i;
522     ++layer;
523 
524     if ( layer > 1 )                    // 如果不是根节点需要输出特殊符号
525     {
526         for (i=1; i<layer-1; ++i )        // 根节点和最后一个结点不需要，所以从1至(layer-1)
527             if ( outTag[i] )            // 如果左边还有结点
528                 cout << "|       ";
529             else
530                 cout << "        ";
531 
532         if ( firstNode == true )        // 判断左右结点，非二叉树需要另外处理
533             cout << "L-------" << flush;
534         else
535             cout << "R-------" << flush;
536     }
537     cout << tree->mKey << endl;
538 
539     if ( (tree->mRight) != nullptr )    // 先输出右节点
540     {
541         if ( tree->mLeft != nullptr )    // 如果左边还有结点需要做标记
542             outTag[layer] = true;
543         printTree(tree->mRight, false);    // false表示当前是右节点
544     }
545 
546     if ( tree->mLeft != nullptr )
547     {
548         outTag[layer] = false;            // 左结点左边不再有结点，恢复默认标记
549         printTree(tree->mLeft, true);
550     }
551 
552     --layer;                            // 结点回溯时高度需要减1
553 }
554 
555 template <typename T>
556 void BSTree<T>::printTree() const
557 {
558     printTree(dynamic_cast<BSTNode<T>*>(this->mRoot), false);    // 作为根节点时，右参数无意义
559 }
560 
561 template < typename T >
562 const T& BSTree<T>::getRootKey() const
563 {
564     return this->mRoot->mKey;
565 }
566 
567 template < typename T >
568 BSTree<T>::~BSTree()
569 {
570     destroy();
571 }
572 
573 }
574 
575 #endif // BSTREE_H

main.cpp

  1 #include <iostream>
  2 #include <iomanip>
  3 #include <cmath>
  4 
  5 #include "BSTree.h"
  6 
  7 #include "Times.h"
  8 
  9 using namespace std;
 10 using namespace Viclib;
 11 
 12 int main(int argc, char* argv[])
 13 {
 14     uint16_t layer = 8;    // 结点最小层数
 15 
 16     if ( argc == 2 && atoi(argv[1])>0 )
 17         layer = static_cast<uint8_t>(atoi(argv[1]));
 18     else {
 19         cout << "请输入结点最小层数，注意内存大小" << log(RAND_MAX*RAND_MAX+1+RAND_MAX*2)/log(2) << endl;
 20         cin >> layer;
 21     }
 22 
 23     timingStart();                            // 启动计时
 24 
 25     cout << endl;
 26 
 27     uint64_t const count = (1ull<<layer)-1;    // 结点数
 28     uint16_t speed;                            // 记录插入和删除的进度百分比（0～100）
 29 
 30     BSTree<uint64_t> *tree = new BSTree<uint64_t>();
 31 
 32     speed = 0;
 33     srand(static_cast<unsigned int>(time(nullptr)));
 34     while ( tree->getCount() < count )
 35     {
 36         tree->insert(static_cast<size_t>(rand()*rand()+1+RAND_MAX*2));    // 使用随机值插入；如果是顺序值，会退化成链表模式，且插入变慢
 37 
 38         if ( (tree->getCount()*100/count > speed) || (tree->getCount() == count) )    // 进度值出现变化或完成操作时才能输出
 39         {
 40             speed = static_cast<uint16_t>(tree->getCount()*100/count);
 41             cout << "
已添加：" << setw(3) << speed << '%' << flush;
 42         }
 43     }
 44     cout << endl;
 45 
 46     cout << "
前序遍历: ";
 47     tree->preOrder();
 48     cout << endl;
 49 
 50     cout << "
中序遍历: ";
 51     tree->inOrder();
 52     cout << endl;
 53 
 54     cout << "
后续遍历: ";
 55     tree->postOrder();
 56     cout << endl;
 57 
 58     cout << "
广度遍历：";
 59     tree->levelOrder();
 60     cout << endl;
 61 
 62     cout << "
最小值: " << tree->minimum();
 63     cout << "
最大值: " << tree->maximum();
 64     cout << "
树高度 = " << tree->height();
 65     cout << "
结点数= " << tree->getCount();
 66     cout << endl;
 67 
 68     cout << "
输出树形信息：" << endl;
 69     tree->printTree();
 70     cout << endl;
 71 
 72     speed = 0;
 73     srand(static_cast<unsigned int>(time(nullptr)));
 74     while ( tree->getCount() )
 75     {
 76         uint64_t node;
 77 //        if ( tree->getCount()*100/count < 20 )            // 剩余量太少时，随机值命中有效结点的概率太低，从而导致删除缓慢
 78             node = tree->getRootKey();
 79 //        else
 80 //            node = static_cast<size_t>(rand()*rand()+1+RAND_MAX*2);
 81 
 82         tree->remove(node);
 83 
 84         if ( ((count-tree->getCount())*100/count > speed) || (tree->getCount() == count) )
 85         {
 86             speed = static_cast<uint16_t>((count-tree->getCount())*100/count);
 87             cout << "
已删除：" << setw(3) << speed << '%' << flush;
 88         }
 89     }
 90     cout << endl;
 91 
 92     tree->destroy();
 93     delete tree;
 94     tree = nullptr;
 95 
 96     cout << endl;
 97     timingEnd();
 98 
 99     return 0;
100 }