使用C++实现二叉搜索树的数据结构

需要注意的地方：
①二叉搜索树删除一个指定结点R，若R为叶子结点，则将R的父结点中指向R的指针改为指向nullptr；若R的左右子结点一个为空，一个非空，则将R的父结点中指向R的指针改为指向R的非空子结点；若R有两个非空子结点，则找出R的右子树中的最小值结点，将其删除并将R的值置为该最小值结点的值。
②对二叉搜索树进行中序遍历，将得到按升序排序的输出结果。
③使用了多态，二叉搜索树结点类BSTNode继承自抽象类BinNode（二叉树结点类）。
④二叉搜索树不是自平衡的，二叉搜索树的平衡性取决于结点的插入顺序，在极端情况二叉搜索树会退化成链表，查找元素的时间复杂度会退化为O(N)。
代码如下，写在头文件中：
  1 #ifndef BST_H
  2 #define BST_H
  3 
  4 #include <iostream>
  5 #include <queue>
  6 
  7 
  8 /************************************************************************/
  9 /* 抽象二叉树结点类                                                     */
 10 /************************************************************************/
 11 template <typename Val>
 12 class BinNode
 13 {
 14 public:
 15     virtual ~BinNode() {}
 16     virtual bool IsLeaf() const = 0;
 17     virtual Val GetValue() const = 0;
 18     virtual void SetValue(const Val &val_) = 0;
 19     virtual BinNode* GetLeftChild() const = 0;
 20     virtual void SetLeftChild(BinNode *lc) = 0;
 21     virtual BinNode* GetRightChild() const = 0;
 22     virtual void SetRightChild(BinNode *rc) = 0;
 23     virtual void InOrderTraverse() const = 0;
 24 };
 25 
 26 
 27 /************************************************************************/
 28 /* 二叉搜索树结点类                                                     */
 29 /************************************************************************/
 30 template <typename Key, typename Val>
 31 class BSTNode : public BinNode<Val>
 32 {
 33 public:
 34     BSTNode()
 35         : key(), val(), left_(nullptr), right_(nullptr) {}
 36     BSTNode(const Key &key_, const Val &val_, BSTNode *lc = nullptr, BSTNode *rc = nullptr)
 37         : key(key_), val(val_), left_(lc), right_(rc) {}
 38     ~BSTNode() {}
 39     bool IsLeaf() const { return (left_ == nullptr) && (right_ == nullptr); } //判断是否为叶结点
 40     Key GetKey() const { return key; }
 41     void SetKey(const Key &key_) { key = key_; } //删除结点时用到,其他情况下不可对key值做修改
 42     Val GetValue() const { return val; }
 43     void SetValue(const Val &val_) { val = val_; }
 44     BSTNode* GetLeftChild() const { return left_; }
 45     void SetLeftChild(BinNode<Val> *lc) { left_ = dynamic_cast<BSTNode*>(lc); }
 46     BSTNode* GetRightChild() const { return right_; }
 47     void SetRightChild(BinNode<Val> *rc) { right_ = dynamic_cast<BSTNode*>(rc); }
 48     void InOrderTraverse() const; //中序遍历
 49 private:
 50     Key key;
 51     Val val;
 52     BSTNode *left_;
 53     BSTNode *right_;
 54 };
 55 
 56 template <typename Key, typename Val>
 57 void BSTNode<Key, Val>::InOrderTraverse() const
 58 {
 59     if (left_ != nullptr)
 60     {
 61         left_->InOrderTraverse();
 62     }
 63     std::cout << "Key: " << key << ", Value: " << val << "
";
 64     if (right_ != nullptr)
 65     {
 66         right_->InOrderTraverse();
 67     }
 68 }
 69 
 70 
 71 /************************************************************************/
 72 /* 二叉搜索树类                                                         */
 73 /************************************************************************/
 74 template <typename Key, typename Val>
 75 class BSTree
 76 {
 77 public:
 78     BSTree()
 79         : root(nullptr), node_num(0) {}
 80     ~BSTree() { Deconstructor(root); }
 81     BSTree(const BSTree &bst) = delete; //禁止编译器生成拷贝构造函数
 82     BSTree& operator=(const BSTree &bst) = delete; //禁止编译器重载拷贝赋值运算符
 83     void InOrderTraverse() const; //中序遍历
 84     void Insert(const Key &key, const Val &val); //插入新结点
 85     Val Delete(const Key &key); //删除指定结点,返回结点的值
 86     Val Find(const Key &key) const; //获取指定key值结点对应的val值
 87     void SetEmpty(); //清空树中所有结点
 88     void BFS() const; //广度优先搜索遍历
 89     unsigned int Size() const { return node_num; }
 90 private:
 91     BSTNode<Key, Val> *root;
 92     unsigned int node_num;
 93     /************************************************************************/
 94     /* 私有函数                                                             */
 95     /************************************************************************/
 96     BSTNode<Key, Val>* Inserter(BSTNode<Key, Val> *root, const Key &key, const Val &val); //插入结点的辅助函数
 97     void Deconstructor(BSTNode<Key, Val> *root); //析构函数的辅助函数,delete所有结点
 98     BSTNode<Key, Val>* GetMinValueNode(BSTNode<Key, Val> *root) const; //找到Key值最小的结点
 99     BSTNode<Key, Val>* DeleteMinValueNode(BSTNode<Key, Val> *root); //删除Key值最小的结点
100     BSTNode<Key, Val>* Deleter(BSTNode<Key, Val> *root, const Key &key); //删除结点的辅助函数
101     Val Finder(BSTNode<Key, Val> *root, const Key &key) const; //找出指定Key值的结点,并返回val的值
102 };
103 
104 template <typename Key, typename Val>
105 void BSTree<Key, Val>::InOrderTraverse() const
106 {
107     if (root == nullptr)
108     {
109         return;
110     }
111     std::cout << "Inorder Traverse:
";
112     root->InOrderTraverse();
113 }
114 
115 template <typename Key, typename Val>
116 void BSTree<Key, Val>::Insert(const Key &key, const Val &val)
117 {
118     root = Inserter(root, key, val);
119     ++node_num;
120 }
121 
122 template <typename Key, typename Val>
123 BSTNode<Key, Val>* BSTree<Key, Val>::Inserter(BSTNode<Key, Val> *root, const Key &key, const Val &val)
124 {
125     if (root == nullptr)
126     {
127         return new BSTNode<Key, Val>(key, val, nullptr, nullptr);
128     }
129     if (key < root->GetKey())
130     {
131         root->SetLeftChild(Inserter(root->GetLeftChild(), key, val));
132     }
133     else
134     {
135         root->SetRightChild(Inserter(root->GetRightChild(), key, val));
136     }
137     return root;
138 }
139 
140 template <typename Key, typename Val>
141 void BSTree<Key, Val>::Deconstructor(BSTNode<Key, Val> *root)
142 {
143     if (root == nullptr)
144     {
145         return;
146     }
147     Deconstructor(root->GetLeftChild());
148     Deconstructor(root->GetRightChild());
149     delete root;
150 }
151 
152 template <typename Key, typename Val>
153 BSTNode<Key, Val>* BSTree<Key, Val>::GetMinValueNode(BSTNode<Key, Val> *root) const
154 {
155     if (root->GetLeftChild() == nullptr)
156     {
157         return root;
158     }
159     else
160     {
161         return GetMinValueNode(root->GetLeftChild());
162     }
163 }
164 
165 template <typename Key, typename Val>
166 BSTNode<Key, Val>* BSTree<Key, Val>::DeleteMinValueNode(BSTNode<Key, Val> *root)
167 {
168     if (root->GetLeftChild() == nullptr)
169     {
170         return root->GetRightChild();
171     }
172     else
173     {
174         root->SetLeftChild(DeleteMinValueNode(root->GetLeftChild()));
175         return root;
176     }
177 }
178 
179 template <typename Key, typename Val>
180 Val BSTree<Key, Val>::Delete(const Key &key)
181 {
182     Val temp_val = Finder(root, key);
183     if (temp_val != Val())
184     {
185         root = Deleter(root, key);
186         --node_num;
187     }
188     return temp_val;
189 }
190 
191 template <typename Key, typename Val>
192 BSTNode<Key, Val>* BSTree<Key, Val>::Deleter(BSTNode<Key, Val> *root, const Key &key)
193 {
194     if (root == nullptr)
195         return nullptr;
196     if (key < root->GetKey())
197     {
198         root->SetLeftChild(Deleter(root->GetLeftChild(), key));
199     }
200     else if (key > root->GetKey())
201     {
202         root->SetRightChild(Deleter(root->GetRightChild(), key));
203     }
204     else
205     {
206         if (root->GetLeftChild() == nullptr)
207         {
208             BSTNode<Key, Val> *temp_node = root;
209             root = root->GetRightChild();
210             delete temp_node;
211         }
212         else if (root->GetRightChild() == nullptr)
213         {
214             BSTNode<Key, Val> *temp_node = root;
215             root = root->GetLeftChild();
216             delete temp_node;
217         }
218         else
219         {
220             BSTNode<Key, Val> *temp_node = GetMinValueNode(root->GetRightChild());
221             root->SetValue(temp_node->GetValue());
222             root->SetKey(temp_node->GetKey());
223             root->SetRightChild(DeleteMinValueNode(root->GetRightChild()));
224             delete temp_node;
225         }
226     }
227     return root;
228 }
229 
230 template <typename Key, typename Val>
231 Val BSTree<Key, Val>::Find(const Key &key) const
232 {
233     return Finder(root, key);
234 }
235 
236 template <typename Key, typename Val>
237 Val BSTree<Key, Val>::Finder(BSTNode<Key, Val> *root, const Key &key) const
238 {
239     if (root == nullptr)
240     {
241         return Val(); //对应的结点不存在,返回Val类型的默认值
242     }
243     if (key < root->GetKey())
244     {
245         return Finder(root->GetLeftChild(), key);
246     }
247     else if (key > root->GetKey())
248     {
249         return Finder(root->GetRightChild(), key);
250     }
251     else
252     {
253         return root->GetValue();
254     }
255 }
256 
257 template <typename Key, typename Val>
258 void BSTree<Key, Val>::SetEmpty()
259 {
260     Deconstructor(root);
261     root = nullptr;
262     node_num = 0;
263 }
264 
265 template <typename Key, typename Val>
266 void BSTree<Key, Val>::BFS() const
267 {
268     std::queue<BSTNode<Key, Val>*> node_queue;
269     node_queue.push(root);
270     BSTNode<Key, Val> *temp_node = nullptr;
271     std::cout << "Breadth First Search Traverse:
";
272     while (!node_queue.empty())
273     {
274         temp_node = node_queue.front();
275         node_queue.pop();
276         std::cout << "Key: " << temp_node->GetKey() << ", Value: " << temp_node->GetValue() << "
";
277         if (temp_node->GetLeftChild() != nullptr)
278         {
279             node_queue.push(temp_node->GetLeftChild());
280         }
281         if (temp_node->GetRightChild() != nullptr)
282         {
283             node_queue.push(temp_node->GetRightChild());
284         }
285     }
286 }
287 
288 #endif