首页 / C++ / 二叉搜索树C++实现

二叉搜索树C++实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了二叉搜索树C++实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2718字，纯文字阅读大概需要4分钟。

内容图文

              1 template<typename Element>
  2class BinarySearchTree
  3{
  4public:
  5        BinarySearchTree():root(NULL){}
  6         BinarySearchTree(const BinarySearchTree& bst):root(NULL)
  7        {
  8operator=(bst);
  9        }
 10virtual ~BinarySearchTree()
 11        { clear(root); }
 12 13void insert(const Element& e)
 14        { insert(root, e); }
 15void remove(const Element& e)
 16        { remove(root, e); }
 17bool contains(const Element& e) const 18         { return contains(root, e); }
 19const Element& findMin() const 20         { return findMin(root); }
 21const Element& findMax() const 22         { return findMax(root); }
 23bool isEmpty() const 24         { return root==NULL; }
 25void clear()
 26        { clear(root); }
 27 28const BinarySearchTree& operator=(const BinarySearchTree& bst)
 29        {
 30if(this!=&bst)
 31            {
 32                clear();
 33                 root = clone(bst.root);
 34            }
 35return *this;
 36        }
 37 38private:
 39struct BSTNode
 40        {
 41            Element element;
 42             BSTNode *left;
 43             BSTNode *right;
 44             BSTNode(const Element& e, BSTNode *lt, BSTNode *rt):
 45                element(e), left(lt), right(rt){}
 46        };
 47         BSTNode *root;
 48 49         BSTNode* clone(BSTNode * t)
 50        {
 51if(t!=NULL)
 52            {
 53returnnew BSTNode(t->element, clone(t->left), clone(t->right));
 54            }
 55return NULL;
 56        }
 57void clear(BSTNode * &t)
 58        {
 59if(t!=NULL)
 60            {
 61                 clear(t->left);
 62                 clear(t->right);
 63delete t;
 64            }
 65             t = NULL;
 66        }
 67void insert(BSTNode * &t, const Element& e)
 68        {
 69if(t!=NULL)
 70            {
 71if(e<t->element)
 72                {
 73                     insert(t->left, e);
 74                }
 75elseif(e>t->element)
 76                {
 77                     insert(t->right, e);
 78                }
 79else 80                {
 81                }
 82            }
 83else 84            {
 85                 t = new BSTNode(e, NULL, NULL);
 86            }
 87        }
 88void remove(BSTNode * &t, const Element& e)
 89        {
 90if(t!=NULL)
 91            {
 92if(e<t->element)
 93                {
 94                     remove(t->left, e);
 95                }
 96elseif(e>t->element)
 97                {
 98                     remove(t->right, e);
 99                }
100elseif(t->left!=NULL&&t->right!=NULL)
101                {
102                     t->element = findMin(t->right);
103                     remove(t->right, t->element);
104                }
105else106                {
107                     BSTNode *tmp = t;
108                     t = t->left!=NULL?t->left:t->right;
109delete tmp;
110                }
111            }
112        }
113bool contains(BSTNode * t, const Element& e) const114        {
115if(t!=NULL)
116            {
117if(e<t->element)
118                {
119return contains(t->left, e);
120                }
121elseif(e>t->element)
122                {
123return contains(t->right, e);
124                }
125else126                {
127returntrue;
128                }
129            }
130else131            {
132returnfalse;
133            }
134        }
135const Element& findMin(BSTNode* t) const136        {
137return t->left!=NULL?findMin(t->left):t->element;
138        }
139const Element& findMax(BSTNode* t) const140        {
141return t->right!=NULL?findMax(t->right):t->element;
142        }
143 };

 

原文：http://www.cnblogs.com/pczhou/p/4641415.html

内容总结

以上是互联网集市为您收集整理的二叉搜索树C++实现全部内容，希望文章能够帮你解决二叉搜索树C++实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1276999.html

来源：【匿名】