【C++课程学习】：二叉搜索树
🎁个人主页：我们的五年
🔍系列专栏：C++课程学习
🎉欢迎大家点赞👍评论📝收藏⭐文章
目录
二叉树搜索树的概念：
节点的结构：
⚽️结构：
⚽️ 构造函数：
搜索二叉树的查找：
⛳️查找步骤：
⛳️时间复杂度：
⛳️代码实现：
搜索二叉树的插入：
🌴插入步骤：
🌴插入代码：
二叉树的删除：
🍁删除步骤：
●叶子节点（左右指针都为空）：
●只有一个孩子（左子树为空，或者右子树为空）：
●有两个孩子：
🍁实现代码：
拷贝构造，析构函数：
搜索二叉树的应用：
二叉树搜索树的概念：
二叉搜索树也叫二叉排序树，二叉查找树。
二叉搜索树可以为空，但是不为空的时候，具有下面的性质：
●非空左子树的所有键值小于根的键值。
●非空右子树的所有键值大于根的键值。
●左右子树任然是搜索二叉树。
节点的结构：
⚽️结构：
因为搜索二叉树也是二叉树，要定义左右两个节点指针。此时先以K树讲解。此时的节点结构为：
⚽️ 构造函数：
在实践情况中，我们一般用一个T类型的值（键值）去进行构造一个节点。其他的用BST_node去进行拷贝构造基本是不可能的。所以写这一个构造函数就够了。
struct BST_Node {
//用key值进行构造
BST_Node(const T& key=T())
:_left(nullptr)
,_right(nullptr)
,_key(key)
{
}
//左右节点指针，以及键值
BST_Node<T>* _left;
BST_Node<T>* _right;
T _key;
};另外下面还有对该节点和节点指针重命名的。
typedef BST_Node<T> node;
typedef node* pnode;
搜索二叉树的查找：
⛳️查找步骤：
如果要查找一个值，根据二插树的性质。从根节点开始，如果根的键值不是，那么如果要查找的键值大于根，就往右子树走。如果小于根的键值，那么就往左子树走。如果走到空了，还没找到，那么这个值就不存在。
⛳️时间复杂度：
最坏情况是查找树的高度次。
但是此时不是满二叉树，不能认为现在的二叉树的高度为（logN）+1。
最坏二叉树的高度为N，所以查找就是N次。时间复杂度就是O（N）。
⛳️代码实现：
bool find(T& key)
{
pnode p=_root;
while (p)
{
if (key < _root->_key)
p = p->_left;
else if (key > _root->_key)
p = p->_right;
else
return true;
}
return false;
}搜索二叉树的插入：
🌴插入步骤：
根据搜索二叉树的规则，如果要插入的值小于此时的键值，那么就往左边走，如果大于此时的键值就往右走。直到走到空为止，然后用一个键值为key的新节点插入到搜索二叉树中。要插入，就要知道父节点，所以在走的过程中，要用parent_cur时刻记录cur的父节点。
因为当_root为空时进行了特判，所以parent_cur不可能为nullptr,所以不会发生对野指针的解引用。
🌴插入代码：
bool insert(const T& key)
{
//当根节点为nullptr时，直接向_root插入节点
if (_root == nullptr)
{
_root = new node(key);
return true;
}
//_root为二叉搜索树的根节点
pnode cur = _root;
pnode parent_cur = nullptr;
while (cur)
{
//如果要插入的值小于此时的根节点，就往左边走
if (key < cur->_key)
{
parent_cur = cur;
cur = cur->_left;
}
//如果要插入的值大于此时的根节点，就往右边走
else if (key > cur->_key)
{
parent_cur = cur;
cur = cur->_right;
}
//此时表示二叉树中存在该值，就返回false
else
return false;
}
//申请节点，cur在parent_cur的左边就把新节点插入parent_cur的左边，如果不是就插入右边
pnode newnode = new node(key);
if (key< parent_cur->_key)
parent_cur->_left = newnode;
else
parent_cur->_right = newnode;
return true;
}二叉树的删除：
🍁删除步骤：
把搜索二叉树的节点进行分类，具体点可以分为三种情况：
●叶子节点（左右指针都为空）：
删除叶子节点时，直接删除即可，如果叶子节点在父节点的左边，就把父节点的左指针变为空，如果叶子节点在父节点的右边，就把父节点的右指针变为nullptr。
注意：如果此时叶子节点为_root（根节点），就没有父节点，只需把_root变为nullptr。
●只有一个孩子（左子树为空，或者右子树为空）：
要删除这样的节点也是比较简单的，只需要把该节点的孩子给父节点就可以。叶子节点也可以当成这种情况进行处理。
同样也应该注意该节点是不是根（_root）节点。
●有两个孩子：
这种情况，就不能直接把两个孩子都给父亲，因为一个节点最多有两个孩子，如果父节点已经有一个孩子了，就不能把要删除的节点两个孩子给父节点了。
所以我们就需要去找一个节点来带这两个孩子。要找的这个节点要有这样的性质：
●如果删除的节点在父节点左边，那么找到的新节点就要比父节点小。相反就比父节点大。
解决办法：
就在要删除的这棵树中找，就满足这样的性质。
下面图中在绿色这棵树中找，全部满足键值大于根节点5。
●新的节点必须比左树所有节点都大，比右树都小。
解决办法：
1.左树的节点都比根的键值小，那就比所有右树节点小。左树所有节点都满足了比右树都小。
2.在左树中找到最大就满足了左树节点都小于这个节点。从左树开始，一直往右边走，就可以满足这三个性质。
上图的键值为7的节点。
🍁实现代码：
bool erase(const T& key)
{
pnode parent_cur = nullptr;
pnode cur = _root;
//寻找键值为key的节点
while (cur)
{
if (key < cur->_key)
{
parent_cur = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent_cur = cur;
cur = cur->_right;
}
else
break; //找到了
}
if(cur==nullptr)
return false;
//只有右孩子，叶子节点可以当成这种情况处理
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent_cur->_left == cur)
parent_cur->_left = cur->_right;
else
parent_cur->_right = cur->_right;
}
delete cur;
return true;
}
//只有左孩子
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent_cur->_left == cur)
parent_cur->_left = cur->_left;
else
parent_cur->_right = cur->_left;
}
delete cur;
return true;
}
//有两个孩子
else
{
pnode left_max_parent = cur;
pnode left_max = cur->_right;
while (left_max->_right)
{
left_max_parent = left_max;
left_max = left_max->_right;
}
cur->_key = left_max->_key;
if (left_max == left_max_parent->_left)
left_max_parent->_left=left_max->_left;
else
left_max_parent->_right=left_max->_left;
delete left_max;
return true;
}
}拷贝构造，析构函数：
进行深拷贝，从_root开始遍历，进行深拷贝。
析构函数也要进行逐一释放。
BST(const BST<T>& t)
{
_root = copy(t._root);
}
pnode copy(pnode root)
{
if (root == nullptr)
return root;
pnode newnode = new node;
newnode->_key = root->_key;
newnode->_left = copy(root->_left);
newnode->_right = copy(root->_right);
return newnode;
}
~BST()
{
Destroy(_root);
}
void Destroy(pnode root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}搜索二叉树的应用：
K模型：
上面所说的是K模型，在插入一些数以后，可以去查找某个值在不在这棵树中。例如：查找一个单词是否正确，就可以去一棵有所以单词的搜索二叉树中寻找在不在树中。
KV模型：
就是一个Key值，会与一个value值对应，找到了key值，就可以得到value值。
例如：英汉字典，每个单词就可以对应一个中文意思，找到了key（英文）就可以得到value（中文）。
这种二叉树有极端情况：
使得它的时间复杂度为O（N）。