【C++】搜索二叉树
1、BST简介
搜索二叉树是一种二叉树，其中每个节点的左子节点的值都小于该节点的值，而右子节点的值都大于该节点的值。这种性质使得在BST中进行搜索、插入和删除操作的平均时间复杂度为O(log n)，其中n是树中节点的数量。
例子：
5
/ \
3 8
/ \ / \
2 4 7 9
2、结点定义
在定义和表示二叉搜索树（BST）的节点结构时，可以使用类（class）或结构体（struct）来表示节点，并包含键（key）、值（value）、左子节点指针和右子节点指针等属性。
struct BSTreeNode
{
BSTreeNode<K, V>* _left;
BSTreeNode<K, V>* _right;
K _key;
V _value;
BSTreeNode(const K& key, const V& value)
:_left(nullptr)
, _right(nullptr)
, _key(key)
, _value(value)
{}
};
在定义结点时，我们既可以使用键值和值来定义，也可以只使用键值定义
使用键值和值来定义树可以提供更丰富的信息和灵活性，使节点可以携带额外的数据。而只使用键值定义树则更加简洁，适用于只需要存储键值对关系的场景。选择何种方式取决于具体的需求和数据结构设计的目标。
3、插入搜索
3.1 插入结点
bool Insert(const K& key, const V& value)
{
if (_root == nullptr)
{
_root = new Node(key, value);
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, value);
// 链接
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
函数 Insert 接受键值 key 和值 value 作为参数，用于将新节点插入到二叉搜索树中。下面是代码的解释：
- 如果树为空（即根节点为空），则创建一个新节点，并将根节点指向新节点，然后返回
true。 - 如果树不为空，则从根节点开始遍历，找到合适的插入位置：
- 如果当前节点的键值小于
key，则继续向右子树遍历，更新父节点为当前节点，直到找到一个节点的键值大于key。 - 如果当前节点的键值大于
key，则继续向左子树遍历，更新父节点为当前节点，直到找到一个节点的键值小于key。 - 如果当前节点的键值等于
key，表示树中已经存在相同的键值，返回false，表示插入失败。
- 如果当前节点的键值小于
- 在找到合适的插入位置后，创建一个新节点，并根据父节点的键值与
key的比较结果，将新节点链接到父节点的左子节点或右子节点上。 - 返回
true，表示插入成功。
该代码实现了二叉搜索树的插入操作，根据节点的键值和比较结果，通过遍历找到合适的插入位置，并创建新节点进行插入。同时，它还考虑了树为空的情况和键值已存在的情况，返回相应的结果表示操作的成功与否。
3.2 查找结点
Node* 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 cur;
}
}
return nullptr;
}
函数 Find 接受键值 key 作为参数，用于在二叉搜索树中查找具有该键值的节点。下面是代码的解释：
- 从根节点开始遍历二叉搜索树，将当前节点指针
cur初始化为根节点。 - 在遍历过程中，根据当前节点的键值与目标键值
key的比较结果，决定向左子树还是右子树遍历：- 如果当前节点的键值小于
key，则说明目标节点可能在右子树中，将cur指针更新为当前节点的右子节点。 - 如果当前节点的键值大于
key，则说明目标节点可能在左子树中，将cur指针更新为当前节点的左子节点。 - 如果当前节点的键值等于
key，则找到了目标节点，直接返回该节点的指针。
- 如果当前节点的键值小于
- 如果遍历过程中未找到与目标键值匹配的节点，即遍历到叶子节点仍然未找到，则返回
nullptr表示未找到目标节点。
该代码实现了二叉搜索树的查找操作，通过比较节点的键值和目标键值，沿着合适的子树进行遍历，直到找到目标节点或遍历到叶子节点。如果找到目标节点，则返回该节点的指针；如果未找到，则返回 nullptr 表示未找到目标节点。
4、删除操作
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
{
// 删除
// 1、左为空
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
} // 2、右为空
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
{
// 找右树最小节点替代，也可以是左树最大节点替代
Node* pminRight = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{
pminRight = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
if (pminRight->_left == minRight)
{
pminRight->_left = minRight->_right;
}
else
{
pminRight->_right = minRight->_right;
}
delete minRight;
}
return true;
}
}
return false;
}
这段代码是二叉搜索树的删除操作的实现。
函数 Erase 接受键值 key 作为参数，用于删除二叉搜索树中具有该键值的节点。下面是代码的解释：
- 初始化父节点指针
parent为nullptr，当前节点指针cur为根节点_root。 - 在遍历过程中，根据当前节点的键值与目标键值
key的比较结果，决定向左子树还是右子树遍历：- 如果当前节点的键值小于
key，则说明目标节点可能在右子树中，将cur指针更新为当前节点的右子节点，同时更新parent指针为当前节点。 - 如果当前节点的键值大于
key，则说明目标节点可能在左子树中，将cur指针更新为当前节点的左子节点，同时更新parent指针为当前节点。 - 如果当前节点的键值等于
key，表示找到了目标节点，执行删除操作。
- 如果当前节点的键值小于
- 删除操作根据目标节点的情况分为以下三种情况：
- 如果目标节点的左子树为空，将目标节点的右子树链接到父节点的相应位置，并释放目标节点的内存。
- 如果目标节点的右子树为空，将目标节点的左子树链接到父节点的相应位置，并释放目标节点的内存。
- 如果目标节点的左右子树都不为空，需要找到目标节点的后继节点（右子树的最小节点或左子树的最大节点），将后继节点的键值替换目标节点的键值，然后在后继节点所在子树中递归删除后继节点。
- 执行删除操作后，返回
true表示删除成功。 - 如果遍历过程中未找到与目标键值匹配的节点，即遍历到叶子节点仍然未找到，则返回
false表示删除失败。
接到父节点的相应位置，并释放目标节点的内存。文章来源：https://www.toymoban.com/news/detail-522393.html
- 如果目标节点的右子树为空，将目标节点的左子树链接到父节点的相应位置，并释放目标节点的内存。
- 如果目标节点的左右子树都不为空，需要找到目标节点的后继节点（右子树的最小节点或左子树的最大节点），将后继节点的键值替换目标节点的键值，然后在后继节点所在子树中递归删除后继节点。
- 执行删除操作后，返回
true表示删除成功。 - 如果遍历过程中未找到与目标键值匹配的节点，即遍历到叶子节点仍然未找到，则返回
false表示删除失败。
该代码实现了二叉搜索树的删除操作，根据键值查找到目标节点后，根据节点的情况进行删除操作。其中包括节点无子树、只有左子树或只有右子树的情况，以及节点同时具有左右子树的情况。删除节点后，需要进行相应的链接操作，并释放节点的内存。文章来源地址https://www.toymoban.com/news/detail-522393.html
到了这里，关于【C++】搜索二叉树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
