博客主页：【夜泉_ly】
本文专栏：【C++】
欢迎点赞👍收藏⭐关注❤️
文章目录
- 💡二叉搜索树
- 1. 简介
- 2. 模拟实现
- 2.1 节点
- 2.2 成员
- 2.3 默认构造
- 2.4 插入
- 2.4 中序遍历
- 2.5 查找
- 2.6 删除⭐
- 分析
- 代码实现
💡二叉搜索树
1. 简介
BinarySearchTree，即二叉搜索树。
本文作为二叉树的进阶，AVL和红黑树的铺垫，主要目的是讲讲什么是二叉搜索树，以及简单的模拟实现。
首先，二叉搜索树是一颗二叉树，即每个节点的度最多为二。
其次，对于一颗二叉搜索树，规定：
-
对任意一个节点，其左子树没有节点的值大于它的值，右子树没有节点的值小于它的值。
-
对任意一个节点，其左右子树也是二叉搜索树。
-
特别的，一个空树当然也是二叉搜索树。
这里画了三个我认为比较典型的二叉搜索树，仅供参考：
当看到二叉搜索树的结构后，它的功能就显而易见了。
以上图中间那颗树为例，如果想要查找值为5的节点：
- 从根节点开始找，此时节点的值为4，小于要查找的值，因此只能在右子树找。
- 从值为6的节点开始找，此时节点的值大于要查找的值，因此只能在左子树找。
- 找到值为5的节点，返回结果。
可以发现，如果是一般情况，那么二叉搜索树平均查找的效率是O(logN)；但如果是上图最右边的那种情况，最多查找高度次，查找的效率就会变为O(N)。
如何避免O(N)的情况，就是AVL和红黑树的事了，今天只讲最简单的二叉搜索树。
二叉树基础知识我之前有写过，这里就丢几个链接：
数据结构-二叉树-基础知识
数据结构-堆-详解
数据结构-链式二叉树-四种遍历
现在开始上手二叉搜索树的模拟实现：
2. 模拟实现
2.1 节点
首先得先把节点给弄出来，由于是简单模拟实现，就弄个简单点的节点：
template<class K>
struct BSTreeNode
{
因为这个节点的内容可以全部公开，这里定义为struct。（class加public当然也是可以的）
K _key;BSTreeNode<K>* _left;BSTreeNode<K>* _right;
其成员需要存储数据，以及指向左右子节点的指针。
与C语言不同，这里还需要写个构造函数：
BSTreeNode(const K& key): _key(key): _left(nullptr): _right(nullptr){}
};
注意是const K& key ，不要写成K key !!!，我刚从C转到C++，这种地方经常会忘记加引用😂。
2.2 成员
有了节点，就可以开始写二叉搜索树了：
template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
先typedef一下，加了模板后，类名不是类型，重命名可以让使用变得方便，且减少了写错类型的可能性。
private:Node* _root;
成员是节点的指针。
2.3 默认构造
然后是默认构造，直接传空就行：
BSTree(): _root(nullptr){}
2.4 插入
接下来是插入，在普通二叉树中，插入删除都没有意义，因为插入的位置并没有规定，但在二叉搜索树中，插入是由明确规定的。
bool Insert(const K& key){
当树为空：
if (_root == nullptr){_root = new Node(key);return true;}
不为空，就循环往下走：
Node* parent = nullptr;Node* cur = _root;while (cur != nullptr){
为避免丢位置，加了一个parent。
if (cur->_key == key){return false;}
数据重复直接返回。
不重复，就根据规则往左或往右走：
parent = cur;if (cur->_key < key){cur = cur->_right;}else{cur = cur->_left;}}if (parent->_key > key){parent->_left = new Node(key);}else{parent->_right = new Node(key);}return true;}
为了快速验证上面代码的正确性，可以进行调试，也可以写个中序遍历，因为按二叉搜索树的定义，其中序遍历一定是升序的。
2.4 中序遍历
void InOrder(){_InOrder(_root);}
这里必须再写个函数，因为在调用中序遍历时无法使用私有成员_root。
_InOrder(Node* root){if(root == nullptr) {return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}
2.5 查找
二叉搜索树，当然也得有搜索功能：
Node* Find(const K& key){Node* cur = _root;while (cur != nullptr){if (cur->_key == key){return cur;}if (cur->_key < key){cur = cur->_right;}else{cur = cur->_left;}}return nullptr;}
最后写删除：
2.6 删除⭐
分析
这里比较复杂，先分析好了再写，假定被删除节点为A
-
A为子节点：
这种比较简单，记住父节点就行。
-
A只有一个子节点：
这种只需让A的父节点指向A的子节点。 -
A有两个子节点：
这种情况比较麻烦，一种有效的方式是：用A节点左子树的最大节点顶替A节点。因为左子树小于右子树，因此替换后能保证满足二叉搜索树的定义。
拿上面的树举例，就是拿B换掉A：
这里还存在下图这种最麻烦的情况：
代码实现
下面是代码实现：
bool Erase(const K& key){Node* cur = _root;Node* parent = cur;while (cur != nullptr);{parent = cur;
首先需注意的是，parent在循环一开始就要保存cur，因为在之前的分析中发现了父节点不存在的情况。（这里parent是用cur初始化的，因此也可以在每次移动cur前赋值；但用nullptr初始化parent就只能将赋值写在循环开始）
接下来，让cur走到待删除位置：
if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{
找到位置后，按之前分析的三种情况进行删除操作。
情况一，为子节点：
if (cur->_left == nullptr && cur->_right == nullptr){if (parent == cur){_root = nullptr;}else{
先处理了只有一个节点的情况。
if (parent->_left == cur){parent->_left = nullptr;}else{parent->_right = nullptr;}}}
情况二，有一个子节点：
else if (cur->_left == nullptr || cur->_right == nullptr){if (parent == cur){if (cur->_left != nullptr){_root = cur->_left;}else{_root = cur->_right;}}else{
还是先处理了删除根的情况。
if (parent->_left == cur){if (cur->_left != nullptr){parent->_left = cur->_left;}else{parent->_left = cur->_right;}}else{if (cur->_left != nullptr){parent->_right = cur->_left;}else{parent->_right = cur->_right;}}}}else{
此时可以看见，情况二的代码包含了情况一，因此可以把之前情况一的代码删了。😂
接下来是情况三，有两个子节点：
Node* LMax = cur->_left;Node* LMaxParent = cur;while (LMax->_right != nullptr){LMaxParent = LMax;LMax = LMax->_right;}
先找到了左子树最大的节点。
然后进行替换，需注意保留LMax的左子树：
std::swap(LMax->_key, _root->_key);if (LMaxParent->_left == _root){LMaxParent->_left = LMax->_left;}else{LMaxParent->_right = LMax->_left;}
这里把LMax赋给cur，方便等会统一释放节点：
cur = LMax;}
最后释放节点：
delete cur;return true;}}return false;
}
希望本篇文章对你有所帮助！并激发你进一步探索编程的兴趣！
本人仅是个C语言初学者，如果你有任何疑问或建议，欢迎随时留言讨论！让我们一起学习，共同进步！
