本篇博客主要是讲解什么是二叉搜索树，以及模拟实现二叉搜索树的插入节点，中序遍历，查找特定节点，以及删除节点。
什么是二叉搜索树
首先二叉搜索树肯定是一棵二叉树，对于二叉树我们应该是陌生了。而我们在学习二叉树的时候知道，如果只是一棵普通的二叉树，用来储存数据是没有任何意义的，因为如果我们将数据放到一个普通的二叉树上，那么当我们需要查找这个值的时候我们只能将整棵树都遍历一遍，我们才能找到这个这个节点在二叉树中的位置。这和我们普通的使用数组没有什么区别。
二叉搜索树则不同
我们下面来看二叉搜素树的特点：
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3.它的左右子树也分别为二叉搜索树
下面是一张标准的搜索二叉树的图：这里还存在一个二叉搜索树的要求那就是在二叉搜索树的内部一般都是不存在重复值的。
如果我这里想要寻找的值是7。那么我们不必和普通的二叉树一样，将整棵二叉树都遍历一遍，然后才能找到7的位置。
而这里则不是首先7小于8所以我们去到了8的左子树，然后7大于3我们去到了3的右子树，最后6小于7我们去到6的右子树自然就找到了节点7。
二叉搜索树的插入（非递归）
在写二叉搜索树的插入之前我们先将二叉搜索树的结构和二叉搜索树节点的结构确定。
二叉搜索树节点的结构：
template<class T>
struct BSNode
{
BSNode* _left;
BSNode* _right;
T _val;
BSNode(const T& a)
:_val(a)
,_left(nullptr)
,_right(nullptr)
{}
};二叉搜索树的结构
template<class K>
class BStree
{
typedef BSNode<K> Node;
public:
private:
Node* _root;
};确定好了结构之后我们来插入节点。
首先如果我们要插入的这颗二叉搜索树一个节点都没有那么这个时候就很好插入。直接创建一个新的搜索树的节点，然后让_root 等于这个新创建出来空间的地址即可。
其次如果存在值呢？
如果存在值那么我们自然要使用一个cur指针，去寻找我们要插入的这个值在什么位置。找到了之后，将其链接到二叉树上即可。
下面是代码的实现
//首先来完成二叉搜索树的插入功能
bool Insert(const K& val)
{
if (_root == nullptr)
{
_root = new Node(val);
return true;
}//这是一棵空树，所以这里直接让根节点成为一个节点即可。
//运行到这里代表这一棵树不是空树，我们需要找到这个val应该插入在什么地方
Node* cur = _root;
Node* parent = nullptr;//确保最后能够链接
while (cur)
{
parent = cur;//这个父节点是用于下面链接的
if (cur->_val < val)
{
cur = cur->_right;
}
else if (cur->_val > val)
{
cur = cur->_left;
}
else//默认情况下二叉搜索树是不允许出现重复值的
{
return false;
}
}
if (val < parent->_val)//当运行到这里的时候，我们的cur已经移动到了val应该在的位置，
//此时parennt正是我的val需要的父节点
//现在只需要判断val是大于parent的_val还是小于parent的_val
{
parent->_left = new Node(val);
return true;
}
else
{
parent->_right = new Node(val);
return true;
}
}由此就能够完成插入节点的操作。
中序遍历
但是我们只是完成了一个插入操作，如果不使用监视窗口调试查看的话，我们是无法看到值是否真的储存正确了，所以这里我们需要完成一个中序遍历。对于二叉树的中序遍历我们只需要记住顺序是左子树，根，右子树，然后加上递归结束的判断条件。即可完成，但是和c语言的二叉树遍历不同我们这里出现了一个问题那就是我们在类外调用的时候，是无法拿到根节点的。那么这里存在两种解决方法，第一种方法，写一个Get_Root函数，将类中的_root节点返回给类外使用。
第二个方法如下：
void Inorder()
{
inorder(_root);//这里使用这种方法解决因为如果还是使用c语言的那种方法，
//会发现如果是在类外的话，我们无法
//得到根节点，所以这里我们在创建一个函数来递归调用中序查看的方法
}
//下面的函数我是放在private修饰的作用域中的所以在类外是无法使用下面的这个函数的
void inorder(Node* _root)
{
if (_root == nullptr)
{
return;
}
inorder(_root->_left);
cout << _root->_val << " ";
inorder(_root->_right);
}现在有了插入和中序遍历的函数，我们就来看一下我们的这棵二叉搜索树是否是正确的。
int main()
{
BStree<int> tree;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
tree.InsertR(e);
}
tree.Inorder();
return 0;
}
没有出现错误，中序遍历的结果也是正确的，我这里构建的正是下图中的这棵二叉搜索树：
中序遍历的结果也是正确的，这里我们也能看出来为什么，二叉搜索树还有一个名字是排序二叉树，而map能够拥有排序的功能也正是因为底层使用了二叉搜索树。
查找函数（非递归）
对于查找函数就很简单了，只需要记住二叉搜素树的特点就可了。
bool Find(const K& val)
{
Node* cur = _root;
while (cur)
{
if (cur->_val < val)
{
cur = cur->_right;
}
else if (cur->_val > val)
{
cur = cur->_left;
}
else
{
return true;//代表找到了这个节点
}
}
return false;//没有找到这个节点
}下面我们依旧是检测一下这个函数是否可用。
发现没有问题。
搜索树的删除（非递归）
那么下面我们就来实现第一个比较难的函数，删除节点的函数。
我们首先拿上图分析一下我们删除各个节点可能遇到的问题：
第1个要删除的节点具有一个左子节点
这里我们假设1要删除的节点是14，那么我们要怎么做呢？这里存在一个方法就是"托孤",这里你可以理解成这里的14号节点要出去玩，但是这个14号节点是具有左孩子的。而自己又是父节点的右孩子所以这里就可以将14号节点的左子树成为10号节点的新右子树（因为14号节点就是10号的右子节点，如果14号是10号的左子节点，这里14的左子树就要成为10号的左子树），此时没有破坏二叉搜索树的结构，这样也能完成对14号节点的删除。这里需要注意的一个点就是如果我们要删除的这个节点刚好是根节点呢？
如下图：
此时的8是没有右子树的，所以为了再将8删除后不影响整颗树，就可以选择让8的左子节点成为新的_root,这样即使8被删除了依旧能够保持整棵树是二叉搜索树。
第2个要删除的节点具有一个右子节点
如果待删除的节点只存在一个右节点，我们依旧是使用托孤的方法，在知道了待删除的节点是父节点的左/右节点后，将待删除的节点的右子树连接到父节点上。同理如果要删除的节点是根节点，也和上面做一样的处理
这里我再解释一下为什么，如果待删除节点是一个叶子节点时，也能归类到上面两种中的任意一种，因为将叶子节点的左子树还是右子树都是空。所以只用在删除了叶子节点后，让空代替叶子节点的位置即可。也可以使用“托孤”完美的解决
第3个要删除的节点具有2个子节点
但是如果我们要删除的那个节点是具有两个子节点的此时就不能使用”托孤“的方法了。依旧拿上面那张图举例子：
这里我们假设要删除的是3号节点，此时的3号节点存在两个子节点，所以使用“托孤”的方法肯定是无法解决了。那么我们换一个思路能否寻找一个能够替代3号节点的节点呢？然后我们就会发现3号节点左子树的最大值，或者是右子树的最小值都能够替代三号节点（1号节点和4号节点），而我们在写代码的时候一般选择的是找到4号节点（右子树的最左节点，这里需要注意的是右子树的最左节点虽然已经不可能存在左子节点了，但还是可能会存在右子节点）。然后我们交换3和4，交换完成后的图如下：
然后这里就变成了去删除3号节点（注意：使用待删除节点右子树的最左节点替换待删除的节点，这个待删除的节点一定会变成只有右子树或者是没有子树的情况）。
下面我们就可以来写代码了
bool Erase(const K& val)
{
//因为我们删除的这个节点可能是只有一个节点（0个节点）{这两种情况一起考虑}，具有2个子节点
Node* cur = _root;
//所以这里需要我们记录一下待删除那个节点的父节点
Node* parent = nullptr;
while (cur)
{
if (cur->_val < val)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_val > val)
{
parent = cur;
cur = cur->_left;
}
else//找到了要删除的节点
{
//下面来考虑是一个子节点还是两个子节点的情况
if (cur->_left == nullptr)//我没有左孩子，将我的右孩子托付给父节点
{
if (cur == _root)//我们要删除的这个节点刚好就是根节点
{
_root = cur->_right;
}
else//我们删除这个不是根节点,使用托孤法
{
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
}
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;
}
}
}
else//我的左孩子和有孩子都存在值
{
//我需要去我的右子树里面找到最左值来替换我，然后再删除我
Node* parent = cur;//这里parent就是为了能够找到交换后待删除节点的父节点的
Node* subleft = cur->_right;
while (subleft->_left)
{
parent = subleft;
subleft = subleft->_left;
}
swap(subleft->_val, cur->_val);
//下面就需要删除subleft节点
//subleft是最左节点，但是它可能还具有右子节点
if (subleft == parent->_left)
{
parent->_left = subleft->_right;
}
else
{
parent->_right = subleft->_right;
}
}
return true;
}
}
return false;//表明没有找到要删除的节点
}这个代码需要注意一下的是这里：
这里parent的目的已经写在注释中了，那么这里为什么要给parent赋值为cur而不是nullptr呢？如果这里的parent赋值的是nullptr，以上图的那棵树为例子，如果我们想要删除的是8号节点那么cur的右子节点刚好就是右子树的最左节点，此时就不会进入循环，如果parent为nullptr，那么后面就会出现对nullptr的解引用自然就会出现错误。所以这里我们给parent赋值cur，就是为了避免这种情况。如果给parent赋值为cur，依旧是上面的例子，此时的cur指向的就是8，然后我们交换8和10，然后使用parent将8的右子树连接到10上，完成对8的删除。
下面我们来测试一下写的函数是否正确：
以上我们就完成了，对二叉搜索树插入，查找，中序遍历，删除的模拟，但是除了中序遍历，以外都没有使用递归的方法，所以下面我们就使用递归的方法来模拟实现插入，查找和删除。
查找函数（递归）
我们需要记住要实现递归的一个大思路就是要将大问题分解化，例如这里假设我当前的这个节点没有找到你要查找的节点，那就根据你要查找值得大小将其分解成，去我的左子树/右子树里面去查找你要的节点下面是代码
bool FindR(const K& val)
{
return FindR(_root, val);
}
bool FindR(Node* cur, const K& val)
{
if (cur->_val == val)
{
return true;
}
else if (cur->_val < val)
{
return FindR(cur->_right, val);
}
else if (cur->_val > val)
{
return FindR(cur->_left, val);
}
return false;
}插入函数（递归）
至于插入函数我们的第一步依旧是需要，找到要插入的位置，然后再连接，但是在使用递归的时候我们连接就不需要和非递归一样麻烦了。代码实现：
bool InsertR(const K& val)
{
return _InsertR(_root,val);
}
bool _InsertR(Node*& cur,const K& val)//这里为什么要使用引用呢？
//这里使用引用能够完成链接
{
if (cur == nullptr)
{
//这里的cur是一个别名是哪里的别名呢？是递归上一层的那个父节点left指针/right指针的别名，
//我们修改了这个cur自然就修改了
//递归上一层的那个父节点的left/right指针完成了链接
//即使你传过来的是一个nullptr这里就等于将这个空指针重新开辟了一个空间，并且改变了这个空指针的值
cur = new Node(val);
return true;
}
else
{
if (cur->_val < val)
{
return _InsertR(cur->_right, val);
}
else if(cur->_val>val)
{
return _InsertR(cur->_left, val);
}
else//遇到了相同的值不能插入
{
return false;
}
}
}这里没有使用一个额外的变量来记录父节点，原因是我们使用了引用，而在非递归（循环）不能使用引用是因为在c++中引用是不能修改指向的。
删除函数（递归）
删除函数的递归实现思路是：如果当前节点不是待删除节点，那就递归去左子树和右子树上寻找，但是不同点依旧是使用了应用就不需要使用一个变量来记录父节点了。除此之外，还存在一个不同点在对于拥有两个子节点的待删除节点上，我们知道在将待删除节点和替换节点交换以后，整棵树不再是一个二叉搜索树（交换后引用也无法使用了）。
但是我们在交换后，还有一个节点的左子树依旧是二叉搜索树。
可以看到在将4和3交换后，4的右子树依旧是一颗二叉搜索树，所以我们就可以变成在交换节点的右子树上删除3号节点。
下面是代码的实现：
bool EraseR(const K& val)
{
return _EraseR(_root, val);
}
bool _EraseR(Node*& cur, const K& val)
{
if (cur == nullptr)
{
return false;//代表没找到要删除的数或者这棵树已经空了
}
else if (cur->_val < val)
{
return _EraseR(cur->_right, val);//转换成去我的右子树上删除这个节点
}
else if (cur->_val > val)
{
return _EraseR(cur->_left, val);//去我的左子树上去删除这个节点
}
else
{
//删除这个节点
if (cur->_right == nullptr)
{
cur = cur->_left;
}//这里还是使用了那个引用的特点此时的cur就是上一层父节点的（左子指针/右子指针）
else if (cur->_left == nullptr)
{
cur = cur->_right;
}
else//代表要删除的这个节点具有两个节点
{
Node* subleft = cur->_right;
while (subleft->_left)
{
subleft = subleft->_left;
}
swap(subleft->_val, cur->_val);//完成替换,那么下面就是一个重点此时我们的引用是无法改变的，也就意味着我们
//无法把引用从cur替换到subleft的父节点上，那么此时我们又没有subleft的父节点，那么我们要怎么做呢？
_EraseR(cur->_right, val);//我们就转换成去此时cur的右节点上删除val，虽然此时的整棵树不是一个
//二分查找树，但是我们替换了之后的cur的右子树任然是一个二分查找树
//原因如下，在交换前cur的值就小于右子树的所有值，那么我们将cur和右子树的最小值交换之后，
//cur的右子树任然是满足二分搜索树的特点的
}
}
}下面是我的所有包含在头文件中的代码（递归和非递归都有）
template<class T>
struct BSNode
{
BSNode* _left;
BSNode* _right;
T _val;
BSNode(const T& a)
:_val(a)
,_left(nullptr)
,_right(nullptr)
{}
};
template<class K>
class BStree
{
typedef BSNode<K> Node;
public:
//首先来完成二叉搜索树的插入功能
bool Insert(const K& val)
{
if (_root == nullptr)
{
_root = new Node(val);
return true;
}//这是一棵空树，所以这里直接让根节点成为一个节点即可。
//运行到这里代表这一棵树不是空树，我们需要找到这个val应该插入在什么地方
Node* cur = _root;
Node* parent = nullptr;//确保最后能够链接
while (cur)
{
parent = cur;
if (cur->_val < val)
{
cur = cur->_right;
}
else if (cur->_val > val)
{
cur = cur->_left;
}
else//默认情况下二叉搜索树是不允许出现重复值的
{
return false;
}
}
if (val < parent->_val)//当运行到这里的时候，我们的cur已经移动到了val应该在的位置，此时parennt正是我的val需要的父节点
//现在只需要判断val是大于parent的_val还是小于parent的_val
{
parent->_left = new Node(val);
return true;
}
else
{
parent->_right = new Node(val);
return true;
}
}
void Inorder()
{
inorder(_root);//这里使用这种方法解决因为如果还是使用c语言的那种方法，会发现如果是在类外的话，我们无法
//得到根节点，所以这里我们在创建一个函数来递归调用中序查看的方法
}
bool Find(const K& val)
{
Node* cur = _root;
while (cur)
{
if (cur->_val < val)
{
cur = cur->_right;
}
else if (cur->_val > val)
{
cur = cur->_left;
}
else
{
return true;//代表找到了这个节点
}
}
return false;//没有找到这个节点
}
bool Erase(const K& val)
{
//因为我们删除的这个节点可能是只有一个节点（0个节点）{这两种情况一起考虑}，具有2个子节点
Node* cur = _root;
//所以这里需要我们记录一下待删除那个节点的父节点
Node* parent = nullptr;
while (cur)
{
if (cur->_val < val)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_val > val)
{
parent = cur;
cur = cur->_left;
}
else//找到了要删除的节点
{
//下面来考虑是一个子节点还是两个子节点的情况
if (cur->_left == nullptr)//我没有左孩子，将我的右孩子托付给父节点
{
if (cur == _root)//我们要删除的这个节点刚好就是根节点
{
_root = cur->_right;
}
else//我们删除这个不是根节点,使用托孤法
{
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
}
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;
}
}
}
else//我的左孩子和有孩子都存在值
{
//我需要去我的右子树里面找到最左值来替换我，然后再删除我
Node* parent = cur;
Node* subleft = cur->_right;
while (subleft->_left)
{
parent = subleft;
subleft = subleft->_left;
}
swap(subleft->_val, cur->_val);
//下面就需要删除subleft节点
//subleft是最左节点，但是它可能还具有右子节点
if (subleft == parent->_left)
{
parent->_left = subleft->_right;
}
else
{
parent->_right = subleft->_right;
}
}
return true;
}
}
return false;//表明没有找到要删除的节点
}
//以上我们都是完成的非递归版本，下面我们来完成递归版本，除了中序遍历函数以外，都是非递归的
bool InsertR(const K& val)
{
return _InsertR(_root,val);
}
bool FindR(const K& val)
{
return FindR(_root, val);
}
bool EraseR(const K& val)
{
return _EraseR(_root, val);
}
private:
bool _EraseR(Node*& cur, const K& val)
{
if (cur == nullptr)
{
return false;//代表没找到要删除的数或者这棵树已经空了
}
else if (cur->_val < val)
{
return _EraseR(cur->_right, val);//转换成去我的右子树上删除这个节点
}
else if (cur->_val > val)
{
return _EraseR(cur->_left, val);//去我的左子树上去删除这个节点
}
else
{
//删除这个节点
if (cur->_right == nullptr)
{
cur = cur->_left;
}//这里还是使用了那个引用的特点此时的cur就是上一层父节点的（左子指针/右子指针）
else if (cur->_left == nullptr)
{
cur = cur->_right;
}
else//代表要删除的这个节点具有两个节点
{
Node* subleft = cur->_right;
while (subleft->_left)
{
subleft = subleft->_left;
}
swap(subleft->_val, cur->_val);//完成替换,那么下面就是一个重点此时我们的引用是无法改变的，也就意味着我们
//无法把引用从cur替换到subleft的父节点上，那么此时我们又没有subleft的父节点，那么我们要怎么做呢？
_EraseR(cur->_right, val);//我们就转换成去此时cur的右节点上删除val，虽然此时的整棵树不是一个
//二分查找树，但是我们替换了之后的cur的右子树任然是一个二分查找树
//原因如下，在交换前cur的值就小于右子树的所有值，那么我们将cur和右子树的最小值交换之后，
//cur的右子树任然是满足二分搜索树的特点的
}
}
}
bool FindR(Node* cur, const K& val)
{
if (cur->_val == val)
{
return true;
}
else if (cur->_val < val)
{
return FindR(cur->_right, val);
}
else if (cur->_val > val)
{
return FindR(cur->_left, val);
}
return false;
}
bool _InsertR(Node*& cur,const K& val)//这里为什么要使用引用呢？
//这里使用引用能够完成链接
{
if (cur == nullptr)
{
//这里的cur是一个别名是哪里的别名呢？是递归上一层的那个父节点left指针/right指针的别名，我们修改了这个cur自然就修改了
//递归上一层的那个父节点的left/right指针完成了链接
//即使你传过来的是一个nullptr这里就等于将这个空指针重新开辟了一个空间，并且改变了这个空指针的值
cur = new Node(val);
return true;
}
else
{
if (cur->_val < val)
{
return _InsertR(cur->_right, val);
}
else if(cur->_val>val)
{
return _InsertR(cur->_left, val);
}
else//遇到了相同的值不能插入
{
return false;
}
}
}
void inorder(Node* _root)
{
if (_root == nullptr)
{
return;
}
inorder(_root->_left);
cout << _root->_val << " ";
inorder(_root->_right);
}
Node* _root = nullptr;
};//一棵二叉树只会具有一个根节点希望这篇博客能对你有所帮助，写得不好请见谅，如果发现了错误，欢迎指正。