一.二叉搜索树介绍
二叉搜索树又叫做二叉排序树，它拥有一些特殊的性质。
1.若它的左子树不为空，那么左子树上面的节点全部小于根节点。
2.若它的右子树不为空，那么右子树上面的节点全部大于根节点。
3.它的左右子树也全部都是二叉搜素树，也就是同样遵循1，2点特征
二.二叉搜索树的使用
由于二叉搜索树的特点，使得二叉搜索树在进行中序遍历的时候，恰好就是按照顺序排好的格式。
在走中序遍历的时候，先左节点再根节点再右节点，例如本树：
左0，根1，右2
上面为左，根3，右4
上面为左，根5，右子树
左6，根7，右子树
左0，根8，右子树
左0，根9，右0
所以整体的顺序就是0，1，2，3，4，5，6，7，8，9
1.搜索二叉树的查找
从根节点开始，通过与根节点比较比根节点大，则走到右子树，比根节点小则走到左子树，如此循环，极大降低了查找的时间复杂度。
2.搜索二叉树的插入
同搜索二叉树的查找一样，一直循环查找，找到可以插入的目标位置为nullptr后，通过在开始循环时记录父节点，在找到后，利用父节点和要插入的key大小比较选择插入到左节点还是右节点。
在没有节点的时候，直接在根节点的位置插入即可。
3.搜索二叉树的删除
搜索二叉树的删除分为四种情况。
1.要删除节点的左子树为空，右子树也为空
2.要删除节点的左子树为空，右子树不为空
3.要删除的节点左子树不为空，右子树为空
4.要删除的节点左子树不为空，右子树为空
首先分析第一种情况：
如果左右子树全为空，那么直接将该节点删除即可，并将父节点指向该节点的指针置空。
第二种情况：
如果左子树为空，那么只需要将父节点指向该节点的指针，指向该节点的右子树即可，随后删除该节点。
不难看出，其实第一种情况可以合并到第二三种情况里面，只不过不是手动置空，而是让指针去指向一个空
第三种情况：
与第二种情况一致，只是指向问题不一样。
第四种情况：
这种情况比较复杂一点，如果左右子树都不为空的时候，我们最好不要去动这个节点，而是除了这个节点以外再度寻找一个节点取代它的位置，只需要更换一下key的数值即可，那么什么样的节点可以代替目标节点的位置而不会破坏搜索二叉树呢？
答案是，该节点左子树的最大值，也就是左子树一直往右找，或者右子树的最小值，也就是右子树一直往左找，这样找到的节点放到这个位置，完全可以取代源节点。
更换完毕后，我们只需要删除被更换的节点即可，我们拿右子树的最小值来说，在这种情况下，该节点的左节点一定为空，就相当于回到了第二三种情况里面，至于一些比较特殊的情况，在搜索二叉树的实现代码中会给与说明。
#include<iostream>
using namespace std;
template<class K>
struct BTtreeNode
{
BTtreeNode* _left;
BTtreeNode* _right;
K _key;
BTtreeNode(const K& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};
template<class K>
class BTtree
{
typedef BTtreeNode<K> Node;
private:
Node* _root;
public:
BTtree()
:_root(nullptr)
{}
bool insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* cur = _root;
Node* prev = nullptr;
while (cur)
{
if (cur->_key > key)
{
prev = cur;
cur = cur->_left;
}
else if(cur->_key<key)
{
prev = cur;
cur = cur->_right;
}
else
{
return false;
}
}
if (prev->_key < key)
{
prev->_right = new Node(key);
}
else
{
prev->_left = new Node(key);
}
return true;
}
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_key << " ";
_Inorder(root->_right);
}
void Inorder()
{
_Inorder(_root);
cout << endl;
}
bool erase(const K&key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if(cur->_key<key)
{
parent = cur;
cur = cur->_right;
}
else
{
//找到了，开始删除
if (cur->_left == nullptr)
{
if (cur == _root)//后文使用了parent指针，如果要删除的节点恰好是根节点，那么parent就会使用空指针报错
{ //所以我们直接给出限制，如果是根节点的话直接让根节点指向左或者右子树即可
_root = cur->_right;
}
else
{
if (parent->_key > key)
{
parent->_left = cur->_right;
}
else if (parent->_key < key)
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)//补充上述情况
{
_root = cur->_left;
}
else
{
if (parent->_key > key)
{
parent->_left = cur->_left;
}
else if (parent->_key < key)
{
parent->_right = cur->_left;
}
}
delete cur;
}
else//走到这种情况的时候，不需要再进行限制，因为这种情况里面的删除是更换删除，所以不需要动节点
{
Node* rightMinParent = cur;//因为后面涉及到rightMinParent的使用所以必须得保证其不为null，这种特殊情况后面附上图文解释
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMinParent->_left == rightMin)//更换指向的时候，也分两种情况，并不是全部是父节点指向子节点的右子树，后面附上图文
{
rightMinParent->_left = rightMin->_right;
}
else
{
rightMinParent->_right = rightMin->_right;
}
delete rightMin;
}
return true;
}
}
return false;
}
Node find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
return *cur;
}
}
};指针不能给空的情况：
在这种情况下，并不会进入循环，所以rightMinParent也就是为null，后面就会涉及到空指针的使用，会报错。
下一个问题也可以用这张图来解释，普通情况下，我们只需要让父指针的左指向子节点的右子树即可，但是在这种情况下，rightMinParent在cur的位置，进行交换的是7和8，这时候我们需要删除8，更换指向的时候便是rightMinParent的右指向rightMin的右。
三.搜索二叉树的K模型和KV模型
K模型便是整个上述的例子，节点里面只有一个数据key，而KV模型则是每个节点里面有一个key还有一个value，这样使用key去进行排序(不能动，否则破坏搜索二叉树的功能)，而value存储需求状况下的数据。
四.搜索二叉树的性能分析
如果树是完全二叉树，那么只需要搜索logN次便可以找到目标节点。
如果树是单支树的话，也就是一条链，那么就需要搜索一个遍，平均各种情况下(目标节点在第一个和目标节点在最后一个)，一共需要搜索的次数为N/2次。
标签：right,cur,右子,二叉,搜索,key,节点,left From： https://blog.csdn.net/2301_81245562/article/details/143634813