一、概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
1、若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
2、若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
3、它的左右子树也分别为二叉搜索树。
如下图，就是一颗二叉搜索树。
二叉搜索树的基本框架如下：
1、结点的实现：
template<class K> struct BSTreeNode { BSTreeNode(const K& key = K()) :_left(nullptr) , _right(nullptr) , _key(key) {} BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; };
2、搜索二叉树的框架
template<class K> class BSTree { typedef BSTreeNode<K> Node; public: BSTree() {} private: Node* _root = nullptr; };
二、二叉搜索树的操作及实现
下面我们来讲一讲二叉搜索树的一些基本操作。
1、查找
查找在这里就比较简单了，我们可以比较结点值的大小来判断我们应该往左子树去查找还是往右子树去查找，直到找到空结点。即：要查找的值小于当前根节点的值，就去左子树找，要查找的值大于当前根节点的值，就去右子树找。代码如下：
bool Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key > key) cur = cur->_left; else if (cur->_key < key) cur = cur->_right; else return true; } return false; }
上面的代码是通过循环来控制寻找的，而我们也可以通过递归来帮助我们进行查找。代码如下：
bool _FindR(Node* root, const K& key) { if (root == nullptr) return false; if (root->_key < key) return _FindR(root->_right, key); else if (root->_key > key) return _FindR(root->_left, key); else return true; } bool FindR(const K& key) { return _FindR(_root, key); }
为什么我们要实现一个子函数来帮助我们完成递归的操作呢？因为我们在定义了一个 BSTree<int> t 之后，我们对于成员函数的调用是通过 t.FindR(3) 去查找。但是如果是原来的方式的话我们必须要自己传根节点过去。但是事实是成员函数的参数里有一个 this 指针，就相当于传了 _root 过去，因此我们只需要传要查找的值了。所以应该 private 封装一个子函数来帮助我们完成递归。
2、插入
插入的寻找思路和查找一样：要插入的值小于当前根节点的值，就去左子树插入，要查找的值大于当前根节点的值，就去右子树插入，直到空位置位置。然后就在空位置插入。
bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key > key) { parent = cur; cur = cur->_left; } else if (cur->_key < key) { parent = cur; cur = cur->_right; } else return false; } cur = new Node(key); if (parent->_key < key) parent->_right = cur; else parent->_left = cur; return true; }
插入的递归写法，代码如下：
bool _InsertR(Node*& root, const K& key) { if (root == nullptr) { root = new Node(key); return true; } if (root->_key < key) return _InsertR(root->_right, key); else if (root->_key > key) return _InsertR(root->_left, key); else return false; } bool InsertR(const K& key) { return _InsertR(_root, key); }
3、删除
删除与上面两种操作相比，就比较复杂了，所涉及的情况也较多，细节也多。下面我来看看删除是怎么实现的吧。
最开始还是和上面的一样，我们需要先找到要删除的结点，然后进行下面的操作。
删除最简单的情况就是删除叶子结点，我们不需要做任何的调整，直接将它删除即可。然后就是左子树为空，或者右子树为空的情况，我们只需要在寻找删除结点时记录一下它的父亲结点，然后将删除结点的子节点连接给父亲结点即可。
注：删除叶子结点，其实相当于左为空或者右为空的情况，所以我们只需要考虑左为空或者右为空的情况，左右为空的情况必然会去走前面的任意一种情况。
1、左为空
2、右为空
3、左右都不为空
如果我们要删除的结点的左右孩子都不为空，那么我们应该怎么去调整，才能保证仍然是搜索树呢？从上面我们知道如果删除的结点是叶子结点的话，我们只需要直接删除它即可，那么我们有没有什么办法可以将要删除的结点调整到叶子节点的位置呢？
那么这里我们就需要一个非常好用的方法，那就是替换法删除。
具体思路：可以在其子树中找一个替代结点， 比如：
1、 找其左子树中的最大节点，即左子树中最右侧的节点，或者在其右子树中最小的节
点，即右子树中最左侧的节点。
2、 替代节点找到后，将替代节点中的值交给待删除节点，转换成删除替代节点。
如下图，我们要删除3（这里我们找右子树的最左结点）。
删除的三种情况都分析完了，下面我们用代码来实现：
bool Erase(const K& key) { Node* cur = _root; Node* parent = nullptr; while (cur) { if (cur->_key > key) { parent = cur; cur = cur->_left; } else if (cur->_key < key) { parent = cur; cur = cur->_right; } // cur->_key == key，开始删除 else { //1、左为空 //2、右为空 //3、左右都不为空 if (cur->_left == nullptr) { if (cur == _root) { _root == cur->_right; } else { if (cur == parent->_left) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; cur == nullptr; } else if (cur->_right == nullptr) { if (cur == _root) { _root == cur->_left; } else { if (cur == parent->_left) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; cur == nullptr; } else { //替换法删除 Node* minparent = cur; Node* min = cur->_right; while (min->_left) { minparent = min; min = min->_left; } swap(cur->_key, min->_key); if (min == minparent->_left) minparent->_left = min->_right; else minparent->_right = min->_right; delete min; } } } return false; }
删除同样也有递归实现的代码。代码如下：
bool _EraseR(Node*& root, const K& key) { if (root == nullptr) return false; if (root->_key < key) return _EraseR(root->_right, key); else if (root->_key > key) return _EraseR(root->_left, key); else { Node* del = root; if (root->_left == nullptr) root = root->_right; else if (root->_right == nullptr) root = root->_left; else { Node* min = root->_right; while (min->_left) { min = min->_left; } swap(root->_key, min->_key); return _EraseR(root->_right, key); } delete del; return true; } } bool EraseR(const K& key) { return _EraseR(_root, key); }
三、其他操作
1、析构函数
void _Destory(Node*& root) { if (root == nullptr) return; _Destory(root->_left); _Destory(root->_right); delete root; root = nullptr; } ~BSTree() { _Destory(_root); }
2、拷贝构造函数
Node* _Copy(Node* root) { if (root == nullptr) return nullptr; Node* copyroot = new Node(root->_key); copyroot->_left = _Copy(root->_left); copyroot->_right = _Copy(root->_right); return copyroot; } BSTree(const BSTree<K>& t) { _root = _Copy(t._root); }
3、赋值
BSTree<K>& operator=(BSTree<K> t) { swap(_root, t._root); return *this; }
四、完整代码
1、BinarySearchTree.h
#pragma once #include<iostream> #include<cstdbool> using namespace std; template<class K> struct BSTreeNode { BSTreeNode(const K& key = K()) :_left(nullptr) , _right(nullptr) , _key(key) {} BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; }; template<class K> class BSTree { typedef BSTreeNode<K> Node; public: BSTree() {} //拷贝构造函数 BSTree(const BSTree<K>& t) { _root = _Copy(t._root); } BSTree<K>& operator=(BSTree<K> t) { swap(_root, t._root); return *this; } bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key > key) { parent = cur; cur = cur->_left; } else if (cur->_key < key) { parent = cur; cur = cur->_right; } else return false; } cur = new Node(key); if (parent->_key < key) parent->_right = cur; else parent->_left = cur; return true; } //重难点 bool Erase(const K& key) { Node* cur = _root; Node* parent = nullptr; while (cur) { if (cur->_key > key) { parent = cur; cur = cur->_left; } else if (cur->_key < key) { parent = cur; cur = cur->_right; } // cur->_key == key，开始删除 else { //1、左为空 //2、右为空 //3、左右都不为空 if (cur->_left == nullptr) { if (cur == _root) { _root == cur->_right; } else { if (cur == parent->_left) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; cur == nullptr; } else if (cur->_right == nullptr) { if (cur == _root) { _root == cur->_left; } else { if (cur == parent->_left) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; cur == nullptr; } else { //替换法删除 Node* minparent = cur; Node* min = cur->_right; while (min->_left) { minparent = min; min = min->_left; } swap(cur->_key, min->_key); if (min == minparent->_left) minparent->_left = min->_right; else minparent->_right = min->_right; delete min; } } } return false; } bool Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key > key) cur = cur->_left; else if (cur->_key < key) cur = cur->_right; else return true; } return false; } void InOrder() { _InOrder(_root); } //查找的递归 bool FindR(const K& key) { return _FindR(_root, key); } //插入的递归 bool InsertR(const K& key) { return _InsertR(_root, key); } //删除的递归 bool EraseR(const K& key) { return _EraseR(_root, key); } ~BSTree() { _Destory(_root); } private: Node* _Copy(Node* root) { if (root == nullptr) return nullptr; Node* copyroot = new Node(root->_key); copyroot->_left = _Copy(root->_left); copyroot->_right = _Copy(root->_right); return copyroot; } void _Destory(Node*& root) { if (root == nullptr) return; _Destory(root->_left); _Destory(root->_right); delete root; root = nullptr; } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } //查找的递归 bool _FindR(Node* root, const K& key) { if (root == nullptr) return false; if (root->_key < key) return _FindR(root->_right, key); else if (root->_key > key) return _FindR(root->_left, key); else return true; } //插入的递归 bool _InsertR(Node*& root, const K& key) { if (root == nullptr) { root = new Node(key); return true; } if (root->_key < key) return _InsertR(root->_right, key); else if (root->_key > key) return _InsertR(root->_left, key); else return false; } // 删除的递归 bool _EraseR(Node*& root, const K& key) { if (root == nullptr) return false; if (root->_key < key) return _EraseR(root->_right, key); else if (root->_key > key) return _EraseR(root->_left, key); else { Node* del = root; if (root->_left == nullptr) root = root->_right; else if (root->_right == nullptr) root = root->_left; else { Node* min = root->_right; while (min->_left) { min = min->_left; } swap(root->_key, min->_key); return _EraseR(root->_right, key); } delete del; return true; } } private: Node* _root = nullptr; }; void TestBSTree1() { BSTree<int> t; int a[] = { 8,3,1,10,6,4,7,14,13 }; for (auto e : a) { t.Insert(e); } t.InOrder(); cout << endl; cout << t.Find(3) << endl;; } void TestBSTree2() { BSTree<int> t; int a[] = { 8,3,1,10,6,4,7,14,13 }; for (auto e : a) { t.Insert(e); } cout << t.Find(3); cout << endl; cout << t.Find(50); cout << endl; } void TestBSTree3() { BSTree<int> t; int a[] = { 8,3,1,10,6,4,7,14,13 }; for (auto e : a) { t.Insert(e); } BSTree<int> t1; t1 = t; cout << "t1: "; t1.InOrder(); cout << endl; }
2、test.cpp
#include"BinarySearchTree.h" int main() { TestBSTree1(); cout << "————————————" << endl; TestBSTree2(); cout << "————————————" << endl; TestBSTree3(); return 0; }
运行结果如下：
