1.前言
从二叉搜索树开始，后面慢慢学的AVL树，红黑树，map,set，哈希表等等都会慢慢的变得更难了，也更加难以理解了。希望大家能够坚持下去，只要坚持，就是胜利。
本章重点
着重讲解什么是二叉搜索树，二叉搜索树的定义、性质以及二叉搜索树的正删查的模拟实现。
2.二叉搜索树的概念
二叉搜索树：从中序遍历来看就是一颗有序树，即左边比我大，右边比我小。并且左子树也符合这个要求，右子树也符合这个要求。
也可以称二叉搜索树为二叉查找树，并且他也可以是一棵空树
例：如果这棵树不为空的话
由于左子树中10的右边5比10小，所以这不是一颗二叉搜索树
30的左边15比30小，15作为左子树，没有左右孩子，天然是一棵二叉搜索树，而30的右边全都比30大，且右子树以41为根的左边比其小，右边比其大。所以这棵树是一棵二叉搜索树
3.二叉搜索树的定义及性质
如何定义一棵二叉树呢？
代入如下：
//创建节点
template <class T>
struct BstreeNode
{
BstreeNode<T>* left;
BstreeNode<T>* right;
T val;
//构造函数
BstreeNode(const T& key)
:left(nullptr)
,right(nullptr)
,val(key)
{}
};解释：二叉树由一个一个的节点组成，所以只需要定义出来了节点，再把不同的节点链接起来，那么就组成了一棵二叉树
二叉树的性质：
1.二叉搜索树在用中序遍历时，得到的值就是一个已经排好序的序列了。
例：
用中序遍历可得：1 3 4 6 7 8 10 13 14
2.二叉搜索树只支持增加，删除，查找，不支持修改。
这是因为如果一旦改动了二叉搜索树里面的某一个值，那么这棵二叉搜索树就有可能不是二叉搜索树了，只是一棵普通的二叉树。
3.二叉搜索树的时间复杂度是0(N)
如果二叉树一旦出现最坏的情况，那么就是所有的值都比根小。
例：
由于这个原因，二叉搜索树是不稳定的，所以后续很少用到二叉搜索树，更多的是使用AVL树，和红黑树。
PS：二叉搜索树中是不能够出现相同的值的，如果出现了相同的值，就默认他不是一棵二叉搜索树
4.二叉树的模拟实现
先构造地基，把基本的框架搞出来
//先构造单节点
template <class T>
struct BstreeNode
{
BstreeNode<T>* left;
BstreeNode<T>* right;
T val;
//构造函数
BstreeNode(const T& key)
:left(nullptr)
,right(nullptr)
,val(key)
{}
};
//这里模拟实现二叉搜索树
template <class T>
class Bstree
{
public:
typedef BstreeNode<T> Node;
private:
Node* _root;
}4.1 二叉搜索树的查找
例：
要在这一棵二叉搜索树中查找到7，查找代码如下。
迭代版本：
bool Find(const T& key)
{
Node* cur = _root;
while (cur)
{
if (cur->val < key)
cur = cur->right;
else if (cur->val > key)
cur = cur->left;
else if (cur->val == key)
return true;
}
return false;
}递归版本：
bool FindR(const T& key)
{
if (_FindR(_root, key)) return true;
else return false;
}
bool _FindR(Node* root, const T& key)
{
if (root == nullptr) return false;
if (root->val > key) return _FindR(root->left, key);
else if (root->val < key) return _FindR(root->right, key);
else return true;
}简单来说就是总结成一句话：如果当前值比我小，我就去右子树里面找，如果当前值比我大，那我就去左子树里面找。最后的结果要么就是找到了，要么就是这棵二叉搜索树里面根本没有这个值。
4.2 二叉搜索树的插入
1.当树为空的时候，那么直接插入即可
2.如果树不为空，那么就需要先找到是具体插入在哪一个位置的后面，然后再进行插入。
例：
如果要插入一个2
代码如下：
bool Insert(const T& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
//先找到要插入的位置
Node* prev = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->val > key)
{
prev = cur;
cur = cur->left;
}
else if (cur->val < key)
{
prev = cur;
cur = cur->right;
}
else return false;
}
//到这就找到了要插入的位置
cur = new Node(key);
if (prev->val > key)
prev->left = cur;
else if (prev->val < key)
prev->right = cur;
return true;
}PS：这里在找的时候，也记录了要插入的位置的前一个节点，这是因为你需要把插入的值链接到前一个节点的左边或者右边，形成一棵二叉搜索树。
4.3 二叉搜索树的删除
先判断要删除的节点是否在二叉搜索树里面，如果不在，那就返回。如果在的话，那么就有以下四种情况
1.要删除的节点左为空
2.要删除的节点右为空
3.要删除的节点左右都为空(这种情况包含在1.2两种情况里面)
4.要删除的节点左右都不为空。（这种情况就需要进行特殊处理了，找出左子树的最右值，即最大值，然后与删除的节点值进行交换，那么就转换成了删除这个左子树的最右值所在的节点的位置了。或者找出右子树的最左值，即最小值。）
代码如下：
bool Erase(const T& key)
{
//1.在删除之前要先找到
Node* prev = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->val > key)
{
prev = cur;
cur = cur->left;
}
else if (cur->val < key)
{
prev = cur;
cur = cur->right;
}
else
{
//找到了--三种情况--左为空，右为空，左右均不为空
//1.左为空
if (cur->left == nullptr)
{
//1.先判断是不是根节点
if (_root == cur)
_root = cur->right;
else
{
//不是根节点--那么就是链接的问题了
if (cur == prev->left)
prev->left = cur->right;
else if (cur == prev->right)
prev->right = cur->right;
}
delete cur;
cur = nullptr;
return true;
}
//2.右为空
else if (cur->right == nullptr)
{
//1.先判断是不是根节点
if (_root == cur)
_root = cur->left;
else
{
//不是根节点--那么就是链接的问题了
if (cur == prev->left)
prev->left = cur->left;
else if (cur == prev->right)
prev->right = cur->left;
}
delete cur;
cur = nullptr;
return true;
}
else
{
//左右均不为空--那么找左子树的最右，或者右子树的最左来进行替换
Node* prev = cur;
Node* minleft = cur->right;
while (1)
{
if (minleft->left != nullptr)
{
prev = minleft;
minleft = minleft->left;
}
else
break;
}
//找到了右子树的最左为minleft
cur->val = minleft->val;
//还是分两种情况--左为空或者右为空
if (minleft->left == nullptr)
{
if (prev == cur)
prev->right = minleft->right;
else
prev->left = minleft->right;
}
else if (minleft->right == nullptr)
{
//右为空，那么左右一定是空的，因为minleft就是最左了
if (prev == cur)
prev->right = nullptr;
else
prev->left = nullptr;
}
delete minleft;
minleft = nullptr;
return true;
}
}
}
return false;
}5.总结
二叉树的模拟实现肯定不只是单单的这么简单，而模拟实现他的目的只是为了更好的理解他的相关操作，以及理解增删查代码的相关写法。我们不是为了造轮子，而是为了更好的理解这个轮子是如何造出来的。
此外：本次只给出来查找函数的迭代写法和递归写法，插入函数和删除函数的递归写法还没有给出，有兴趣的小伙伴参考以下链接。
二叉搜索树的增删改模拟实现 · e87b2ae · 青酒余成/初识数据结构 - Gitee.com
