目录
0. 引言
1. 二叉搜索树
1.1 定义
1.2 特点
2. 二叉搜索树的实现
2.1 基本框架
2.2 查找
2.3 插入
2.4 删除
2.4.1 右子树为空
2.4.2 左子树为空
2.4.3 左右都不为空
2.4.4 代码
0. 引言
在C语言数据结构中，我们已经基本了解过二叉树，这篇博客分享的二叉搜索树，主要是为了方便学习后面的 map 以及 set 的学习。那么，现在让我们开始吧！
1. 二叉搜索树
1.1 定义
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值；
它的左右子树也分别为二叉搜索树。
这里我们可以看到，将数据存入二叉搜索树中进行查找时，理想情况下只需要 logN 的时间复杂度。这就是 二叉搜索树 名字的由来，搜索（查找）速度很快。
1.2 特点
搜索二叉树的基本特点：左比根小，右比根大。
- 若某个节点的左节点不为空，则左节点的值一定比当前节点的值小，且其左子树的所有节点都比它小；
- 若某个节点的右节点不为空，则右节点的值一定比当前节点的值大，且其右子树的所有节点都比它大；
- 二叉搜索树的每一个节点的根，左，右 都满足基本特点。
除此之外，二叉搜索树还有一个特点： 中序遍历的结果为升序
例如，对下面这个搜索二叉树进行中序遍历：
上述结果为：1 3 4 5 6 7 10 13 14
由此可见搜素二叉树也具有排序价值，故也称为二叉排序树。
2. 二叉搜索树的实现
2.1 基本框架
我们主要利用C++的类和对象，泛型编程等特点来建立节点的框架，并在此框架的基础上完善各种功能。具体代码如下：
#pragma once
#include <iostream>
//部分展开，避免冲突
using std::cout; //遍历时需要用到
using std::endl;
//命名空间
namespace LHY
{
//利用模板，泛型编程
template<class K>
struct BSTreeNode
{
BSTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
//二叉树包含左节点指针、右节点指针、节点值信息
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
private:
Node* _root = nullptr; //二叉搜索树的根
};
}
这里需要注意的是，二叉搜索树的节点类需要写出构造函数，因为后面创建新节点时会用到；二叉搜索树的根可以给个缺省值 nullptr ，确保后续不会出错。
2.2 查找
查找思路较为简单，当查找值比当前值大，往右子树走，当查找值比当前值小时，则往左走，若相等，即为找到。代码如下：
bool Empty() const
{
return _root == nullptr;
}
bool Find(const K& key) const
{
//如果为空，则查找失败
if (Empty())
return false;
Node* cur = _root;
while (cur)
{
//如果查找值比当前值大，则往右走
if (cur->_key < key)
cur = cur->_right;
//如果查找值比当前值小，则往左走
else if (cur->_key > key)
cur = cur->_left;
else
return true; //找到了
}
return false; //没找到
}
例如，当我们查找 7 时，只需查找 4 次，即可得到结果。
返回 bool 值是为了表示操作成功或者失败。
2.3 插入
实现插入操作实际上与查找差不多，插入操作需要先查找合适的位置再进行插入操作。因此我们的思路如下：
- 先找到合适的位置（满足基本特点）
- 如果当前位置不为空（冗余），则插入失败
- 为空则结束循环，进行插入：创建新节点、判断需要插在左边还是右边、链接新节点完成插入
具体代码如下：
bool Insert(const K& key)
{
//如果为空，则就是第一次插入
if (Empty())
{
_root = new Node(key);
return true;
}
//需要记录父节点
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
//出现冗余，插入失败
return false;
}
}
cur = new Node(key);
//判断需要链接至左边还是右边
if (parent->_key < key)
parent->_right = cur;
else
parent->_left = cur;
return true;
}
二叉搜索树的根为多少，取决于谁第一个插入，后序插入的节点都是基于根节点进行插入的
当找到合适位置时，需要根据当前 key 值与父节点的值进行判断，插入至合适的位置（满足基本特点）。
我们以插入 15 为例子，第一步我们先查找合适的位置：
第二步，插入节点：
若查找不到合适的位置，则插入失败。 且代码当前实现的二叉搜索树不允许冗余，如果想要实现冗余的二叉搜索树，可以规定重复的值插在左边或右边，都是可行的。
在确认 新节点的链接位置时，可以通过 parent 与 cur 的 key 值判断，也可以通过原有链接关系判断 如果是通过原有链接判断：parent->_right == cur 需要先创建新节点 new_node（不能覆盖 cur 的值），利用 cur 进行链接判断后，再进行新节点链接 推荐直接使用 key 值判断，省时省力
总结：
- 在执行循环查找合适位置前，需要创建变量记录父节点的位置，方便后续进行新节点链接
- 找到合适位置后，需要将新节点与父节点进行比较判断，确认链接在左边还是右边
- 插入失败返回 false，插入成功返回 true。
2.4 删除
删除的思路如下：先利用查找来判断目标值是否存在，如果存在，则进行删除，此时，待删除的节点可能会存在多种情况，需要具体问题具体分析，如果不存在，则删除失败。下面我们依次来看删除的各种可能性。
2.4.1 右子树为空
当右子树为空时，只 需要将其左子树与父节点进行判断链接即可，无论其左子树是否为空，都可以链接，链接完成后，删除目标节点。
2.4.2 左子树为空
同理，左子树为空时，将其右子树与父节点进行判断链接，链接完成后删除目标节点。
2.4.3 左右都不为空
当左右都不为空时，就有点麻烦了，需要找到一个合适的值（即 > 左子树所有节点的值，又 < 右子树所有节点的值），确保符合二叉搜索树的基本特点。符合条件的值有：左子树的最右节点（左子树中最大的）、右子树的最左节点（右子树中最小的），将这两个值中的任意一个覆盖待删除节点的值，都能确保符合要求。
解释： 为什么找 左子树的最右节点或右子树的最左节点的值覆盖 可以符合要求？因为左子树的最右节点是左子树中最大的值，> 左子树所有节点（除了自己），< 右子树所有节点，右子树的最左节点也是如此，都能符合要求。
2.4.4 代码
bool Erase(const K& key)
{
if (Empty())
return false;
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
if (cur->_right == nullptr)
{
//右为空，考虑将左子树链接
if (cur == _root)
_root = cur->_left;
else
{
if (parent->_right == cur)
parent->_right = cur->_left;
else
parent->_left = cur->_left;
}
delete cur;
}
else if (cur->_left == nullptr)
{
//左为空，考虑将右子树链接
if (cur == _root)
_root = cur->_right;
else
{
if (parent->_right == cur)
parent->_right = cur->_right;
else
parent->_left = cur->_right;
}
delete cur;
}
else
{
//左右子树都不为空，找左子树的最右节点
//可以更改为找右子树的最左节点
parent = cur;
Node* maxLeft = cur->_left;
while (maxLeft->_right)
{
parent = maxLeft;
maxLeft = maxLeft->_right;
}
//替换，伪删除
cur->_key = maxLeft->_key;
if (parent->_right == maxLeft)
parent->_right = maxLeft->_left;
else
parent->_left = maxLeft->_left;
delete maxLeft;
}
return true;
}
}
return false;
}
总结：
左右子树都为空时：直接删除；左子树、右子树其中一个为空时：托孤，将另一个子树（孩子）寄托给父节点，然后删除自己；左子树、右子树都不空：找一个能挑起担子的保姆，照顾左右两个子树（孩子），然后删除多余的保姆。
注意：涉及更改链接关系的操作，都需要保存父节点的信息；右子树为空、左子树为空时，包含了删除 根节点 的情况，此时 parent 为空，不必更改父节点链接关系，更新根节点信息后，删除目标节点即可，因此需要对这种情况特殊处理；右子树、左子树都为空的节点，包含于 右子树为空 的情况中，自然会处理到；左右子树都不为空的场景中，parent 要初始化为 cur，避免后面的野指针问题。
