引言：在本篇博客当中，我们会将关于二叉树的进阶结构——二叉搜索树，强大的搜索效率让它在数据结构当中变得十分重要，让我们一起来进行学习吧！

更多有关C++的知识详解可前往个人主页：计信猫

一，二叉搜索树的概念

        二叉搜索树的概念其实很简单，首先它一定满足成为一颗二叉树的基本条件，其次值比根节点小的储存在左子树，值比根节点大的储存在右子树，同时它的左右子树也为二叉搜索树。如图就是一颗简单的二叉搜索树：

二，二叉搜索树的创建

        既然我们想创建一颗二叉搜索树，那么首先我们就应该创建一个二叉搜索树的节点结构体（我们称为Node），如下代码所示：

template<class k>
class Node
{
public:Node(const k& key):_left(nullptr), _right(nullptr), _key(key){}Node* _left;Node* _right;k _key;//key为所储存的值
};

        此后我们还应该创建一个结构体专门用于二叉搜索树的遍历，数据操作，代码如下：

template<class k>
class BSTree
{
public:using Node = Node<k>;Node* _root = nullptr;
};

三，二叉搜索树的数据操作函数

1，插入数据

        在二叉搜索树中，我们想插入一个值其实就非常简单了，我们分为两种情况：

        情况一：当二叉搜索树为一个空树时，那么我们就直接创建一个节点并且将这个节点赋值给_root即可。

        情况二：即不为空树时，那么我们只需要根据二叉搜索树的规则遍历到二叉树的根节点，再把数据插入即可。

        所以我们的代码如下：

//插入数据
bool insert(const k& key)
{//情况一：根节点为空if (_root == nullptr){_root = new Node(key);return true;}//情况二：根节点不为空else{//比根节点大的放左边，比根节点小的放右边Node* cur = _root;Node* parent = nullptr;//cur遍历到根节点while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key);//比父节点小就插入左边，反之则插入右边if (parent->_key > key){parent->_left = cur;}else{parent->_right = cur;}return true;}

 2，查找数据

        该函数的作用是查找二叉搜索树中是否存在值key，如果在遍历的过程中找到了值key，那么就返回true，若未找到值key，就返回false。那么代码如下：

//查找数据
bool find(const k& key)
{Node* cur = _root;while (cur){if (cur->_key > key)//比父节点大就往右走{cur = cur->_right;}else if (cur->_key < key)//比父节点小就往左走{cur = cur->_left;}else//相等就返回true{return true;}}return false;
}

 3，删除数据

        删除数据函数在本篇博客中就相对复杂，但没事，我将分情况来进行一一地讲解。

（1）删除的节点左右子树都为空

        这种情况就非常简单，删除这种叶子节点（cur）我们只需要将其父节点的左右指针指向空，然后delete掉这个叶子节点即可，如下图所示：

        而该种情况可以被我们直接归类为情况（2）或情况（3） 。

（2）删除的节点左子树不为空，右子树为空

        当我们遇到这种情况的时候，我们就可以将其父节点（parent）与这个节点（cur）的左孩子相连，但连接的时候我们同时需要判断这个节点与父节点的左右关系，如果被删除节点在父节点的左边，那么我们就应该将该节点的左子树插入到父节点的左边，反之我们则插入父节点的右边。如下图所示：

        可一旦当我们遇到如下图的情况就要进行特殊处理：

        其实处理办法也很简单，我们只需要将根节点的左孩子赋值给_root，然后再删除cur节点即可。所以该情况下处理的代码如下：

else if (cur->_right == nullptr)//cur的右边为空
{if (cur == _root)//特殊情况{_root = cur->_left;}else{if (parent->_left == cur)//左孩子被删除{parent->_left = cur->_left;}else//右孩子被删除{parent->_right = cur->_left;}}delete cur;return true;
}

（3）删除的节点左子树为空，右子树不为空

        那么这种情况其实就可以直接类比到情况（2）了，此时我们就可以直接展示代码：

if (cur->_left == nullptr)//cur的左边为空
{if (cur == _root)//特殊情况{_root = cur->_right;}else{if (parent->_left == cur)//左孩子被删除{parent->_left = cur->_right;}else//右孩子被删除{parent->_right = cur->_right;}}delete cur;return true;
}

（4）删除的节点左子树和右子树都不为空

        这种情况是最麻烦的一种，但是不用担心，静下心来慢慢理解，你会发现易如反掌。那让我们以下图为例子：

        那么解决这种问题，我们就会用到一种方法，叫做替换法。替换法的含义是找到左子树的最右节点或者右子树的最左节点，来替换掉要删除的节点，再删除需要被删除的节点。语言听着很晦涩，那么我们以图来说明!

        这样，一个节点就成功被我们删除了！但是要注意，连接节点的时候还是要进行判断，若被删除的节点是在其父节点的左边，那么替换的节点也必须被连接在父节点的左边，同理，右边也是一样的。所以我们的代码如下：

//删除数据
bool erase(const k& key)
{Node* cur = _root;Node* parent = nullptr;//使用cur先遍历到要删除的节点的位置while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{//相等，进行删除操作if (cur->_left == nullptr)//cur的左边为空{if (cur == _root){_root = cur->_right;}else{if (parent->_left == cur)//左孩子被删除{parent->_left = cur->_right;}else//右孩子被删除{parent->_right = cur->_right;}}delete cur;return true;}else if (cur->_right == nullptr)//cur的右边为空{if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur)//左孩子被删除{parent->_left = cur->_left;}else//右孩子被删除{parent->_right = cur->_left;}}delete cur;return true;}else//左右均不为空，使用替换法删除：左子树的最大值或者右子树的最小值{Node* replace = cur->left;Node* replaceparent = cur;while (replace->_right){replaceparent = replace;replace = replace->_right;}cur->_key = replace->_key;if (replaceparent->_left == replace){replaceparent->_left = replace->_left;}else{replaceparent->_right = replace->_left;}delete replace;return true;}}}return false;
}