概念：
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
搜索二叉树的操作：
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
- 二叉搜索树需要满足左子树比根小，右子树比根大，每一棵树，每一颗子树都需要满足这个条件
- 二叉搜索树使用中序遍历后，得出的遍历结果一定是一个升序序列
- 二叉搜索树的的查询操作雷素与二分查找，但是却比二分查找要来的简单，因为搜索二叉树的删除和插入操作比二分查找更为的简单，且并不需要二分查找一样，当插入和删除后必须要在经历一次排序操作。
- 最后二叉搜索树是不允许进行节点内部的value 也就是节点数值的修改，这是因为二叉搜索树的排序操作和树的结构是因为节点的value进行链接和形成的
节点结构：
template<class K>
//struct BinarySearchTreeNode
struct BSTreeNode
{
BSTreeNode<K>* _left;//指向左子树指针
BSTreeNode<K>* _right;//指向右子树指针
K _key;//用来进行排序的value数值
BSTreeNode(const K& key)//节点的初始化列表
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};插入操作：
二叉搜索树的插入 插入的具体过程如下：
a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点
因为插入时需要保证插入之后还是二叉搜索树，所以插入操作需要进行一次的对比， 例如插入数字5，如果需要插入数字5，那么就需要进行依次的对比！
也就是和每一个节点进行对比，从根节点开始，比对比的节点小往左边移动，比对比的节点大往右移动，直到走到最后一个节点，走向空，需要记住每次插入的节点（非重复）最后都是会插入一个空的位置。
同时还需要注意，当插入的数据已经在树中存在了，而就需要注意搜索树中不会冗余，也就是插入一个相同的元素是不允许在同一个树中出现两次，这是不允许的！除非需要一些扩展。
bool Insert(const K& key)
{
if (_root == nullptr)
{
//当根节点是空的时候，直接进行创造新节点进行插入操作
_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;
}查找函数：
二叉搜索树的查找：
a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
b、最多查找高度次，走到到空，还没找到，这个值不存在。
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
{//找到了就返回
return true;
}
}
//直到指向了空就表示二叉搜索树中没有这个节点存在
return false;
}
删除函数：
删除操作分为三种情况/两种操作：
a、删除的节点他的左子树是空的，则他的父节点要指向他的右子树，同理删除的节点他的右子树是空的，他的父节点要指向他的左子树
b、叶子节点，不过叶子节点可以和第一种情况相结合，让父节点指向删除的叶子节点的右子树
c、左右子树都不为空的：需要使用替换法，找该节点的右子树最小节点或者左子树最大节点
这里找右子树的最小节点。
操作一：情况a、情况b
删除的节点他的左子树是空的，则他的父节点要指向他的右子树，同理删除的节点他的右子树是空的，他的父节点要指向他的左子树。
同时这里还会诞生一个问题，被删除节点的左子树是空的，那父节点指向这个节点的右子树，但是是父节点的那一个指针指向呢？是右指针还是左指针？
需要进行额外的判断，判断删除的节点是父节点的左子树还是右子树，左子树就左指针，右子树就右指针。
且还有一个细节：例如左边为空时，被删除节点的父亲点的要进行判断，判断删除的节点是父亲节点的左节点还是右节点，但是如果我们删除的是根节点，就如上图所示.
这种就需要提前进行判断，如果当前的节点是一个根节点，且左边为空时，那么根节点就需要进行替换，替换成这个根节点的右子树的头一个节点，如果是右边为空，那么这个根节点就需要替换成根节点的左子树的头一个节点。
else
{
// 删除
// 左为空，父亲指向我的右
if (cur->_left == nullptr)//判断被删除的节点是否是他的左子树为空
{
//if(parent == nullptr)是否为根节点的判断
if (cur == _root)
{//为根节点，那么根节点替换成根节点的右子树
_root = cur->_right;
}
else
{//不算根节点则进行父亲节点的指向判断
if (cur == parent->_left)
{
//如果当前节点是父亲节点的左子树，那么就使用父亲节点的左指针指向这个节点的右子树
parent->_left = cur->_right;
}
else
{
//如果当前节点是父亲节点的右子树，那么就使用父亲节点的右指针指向这个节点的右子树
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
//if(parent == nullptr)//是否是根节点的判断
if (cur == _root)
{
_root = cur->_left;
}
else
{
// 右为空，父亲指向我的左
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
操作二：
左右子树都不为空的：需要使用替换法，找该节点的右子树最小节点或者左子树最大节点，这里找右子树的最小节点。
找到这个被删除节点的右子树，然后进入右子树后一直往左边走，找到被删除节点的右子树的 最小的数，而删除操作则需要吧要删除的节点和最小数替换（交换操作）
但是有产生一个问题，之后要删除的话，可能找不到要删除的节点，所以我们还需要一个最小节点的父亲节点，进行指向操作，所以在找右子树最小节点的时候，还得跟更新他的父节点。
同时删除后让父亲节点的左指针指向空（这里删除的节点是叶子节点没有字节的，所以删除节点的指向是null）
但是这种只能因对常规删除，如果删除的的节点中他的右子树是一个叶子节点呢，又或者，它是根节点呢：
就如上图这种情况，这种情况下删除根节点，那么右子树的最小节点就是根的右孩子节点
同时在我们的代码中，交换删除后，我们让父亲节点的左指针，指向被删除节点的右子树（常规操作是最小右节点的父亲节点指向空，这里的最小右节点刚好是根节点的有孩子），那么放在上图情况会直接崩掉，所以还需要进行一个判断
最后这个判断的前者是判断是否是正常情况，在正常情况中，最小右子树节点的父节点只是一个普通的节点，且最小右子树节点的父节点的左边一定是最小右子树节点，所以可以让父节点指向最小右字数节点的 右子树
而非常情况就是如上图这种情况，根节点的右孩子节点就是根节点的最小右子树节点，这种非常情况下，根节点的最小右子树节点在右边，所以需要让根节点的右指针指向最小右子树节点的 右子树。
else
{
// 左右都不为空，替换法删除
//
// 查找右子树的最左节点替代删除
Node* rightMinParent = cur;
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
swap(cur->_key, rightMin->_key);
if (rightMinParent->_left == rightMin)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
}
完成的删除函数代码：
bool Erase(const K& key)
{
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->_left == nullptr)
{
//if(parent == nullptr)
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
//if(parent == nullptr)
if (cur == _root)
{
_root = cur->_left;
}
else
{
// 右为空，父亲指向我的左
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
{
// 左右都不为空，替换法删除
//
// 查找右子树的最左节点替代删除
Node* rightMinParent = cur;
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
swap(cur->_key, rightMin->_key);
if (rightMinParent->_left == rightMin)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
}
return true;
}
}
return false;
}中序遍历：
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}需要注意，这里中序遍历这样写的原因是因为root根节点是私有的原因，所以在外是调不动中序遍历函数的，所以需要把中序遍历函数进行套用，放在私有成员内部，在外部套用一层调用即可使用。
