【数据结构】二叉搜索树

🕗 发布于 2024-09-23 04:25 数据结构 java 开发语言

文章目录

一、二叉搜索树的概念
二、二叉搜索树的中序遍历用于排序
三、二叉搜索树的查找
四、二叉搜索树的插入
五、二叉搜索树的删除
六、⼆叉搜索树key和key/value使⽤场景

一、二叉搜索树的概念

⼆叉搜索树⼜称⼆叉排序树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树:

• 若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值

• 若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结点的值

• 它的左右⼦树也分别为⼆叉搜索树

• ⼆叉搜索树中可以⽀持插⼊相等的值，也可以不⽀持插⼊相等的值，具体看使⽤场景定义，后续我
们学习map/set/multimap/multiset系列容器底层就是⼆叉搜索树，其中map/set不⽀持插⼊相等
值，multimap/multiset⽀持插⼊相等值

之所以又叫二叉排序树，是因为二叉搜索树中序遍历的结果是有序的。

下图是二叉搜索树的示例：

在这里插入图片描述

二、二叉搜索树的中序遍历用于排序

通过上面那张图不难发现，用二叉搜索树走个中序，就是升序+去重排序，这也是二叉搜索树又被称为二叉排序树的原因。

//中序遍历
void _InOrder(Node* _root)
{
    if (_root == nullptr)
    {
        return;
    }
    _InOrder(_root->_left);
    std::cout << _root->_key << " ";
    _InOrder(_root->_right);
}
void InOrder()//因为外部取不到_root,所以这里套了一层调用函数
{
    _InOrder(_root);
    std::cout << std::endl;
}

使用InOrder调用_InOrder的原因是类外面传参传不了私有的_root，所以采用多套一层的方法。

三、二叉搜索树的查找

查找规则：

从根开始⽐较，查找x，x⽐根的值⼤则往右边⾛查找，x⽐根值⼩则往左边⾛查找。
最多查找⾼度次，⾛到到空，还没找到，这个值不存在。
如果不⽀持插⼊相等的值，找到x即可返回
如果⽀持插⼊相等的值，意味着有多个x存在，⼀般要求查找中序的第⼀个x。如下图，查找3，要找到1的右孩⼦的那个3返回

在这里插入图片描述
代码实现：

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;
}

四、二叉搜索树的插入

二叉搜索树的插入需要考虑插入后，需要维持二叉搜索树的形态。

插入规则：

树为空，则直接新增结点，赋值给root指针
树不空，按⼆叉搜索树性质，插⼊值⽐当前结点⼤往右⾛，插⼊值⽐当前结点⼩往左⾛，找到空位
置，插⼊新结点。
如果⽀持插⼊相等的值，插⼊值跟当前结点相等的值可以往右⾛，也可以往左⾛，找到空位置，插
⼊新结点。（要注意的是要保持逻辑⼀致性，插⼊相等的值不要⼀会往右⾛，⼀会往左⾛）

bool Insert(const K& key)
{
    if (_root == nullptr)
    {
        _root = new Node(key);//BSTreeNode对象中存放key值，构造一个二叉搜索树节点 
    }
    else
    {
        Node* parent = nullptr;
        Node* cur = _root;
        //cur一直走，走到要插入的位置
        while (cur)
        {
            parent = cur;
            if (cur->_key < key)
            {
                cur = cur->_right;
            }
            else if (cur->_key > key)
            {
                cur = cur->_left;
            }
            else//说明数字重复，插入失败
                return false;
        }
        cur = new Node(key);
        //判断插入节点放在parent节点的左子树还是右子树
        if (parent->_key < key)
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
    }
    return true;
}

五、二叉搜索树的删除

二叉搜索树的节点进行删除后，同样需要维持二叉搜索树的形态。

删除规则：

⾸先查找元素是否在⼆叉搜索树中，如果不存在，则返回false。

如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为N）

要删除结点N左右孩⼦均为空
要删除的结点N左孩⼦位空，右孩⼦结点不为空
要删除的结点N右孩⼦位空，左孩⼦结点不为空
要删除的结点N左右孩⼦结点均不为空

对应以上四种情况的解决⽅案：

把N结点的⽗亲对应孩⼦指针指向空，直接删除N结点（情况1可以当成2或者3处理，效果是⼀样的）
把N结点的⽗亲对应孩⼦指针指向N的右孩⼦，直接删除N结点
把N结点的⽗亲对应孩⼦指针指向N的左孩⼦，直接删除N结点
⽆法直接删除N结点，因为N的两个孩⼦⽆处安放，只能⽤替换法删除。找N左⼦树的值最⼤结点R(最右结点)或者N右⼦树的值最⼩结点R(最左结点)替代N，因为这两个结点中任意⼀个，放到N的位置，都满⾜⼆叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转⽽变成删除R结点，R结点符合情况2或情况3，可以直接删除。

代码实现：

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 (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;

}
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* replaceParent = cur;
Node* replace = cur->_right;
while (replace->_left)
{
replaceParent = replace;
replace = replace->_left;
}

cur->_key = replace->_key;

if (replaceParent->_left == replace)
replaceParent->_left = replace->_right;
else
replaceParent->_right = replace->_right;

delete replace;
}

return true;
}
}

return false;
}

六、⼆叉搜索树key和key/value使⽤场景

6.1 key搜索场景：

只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的⼆叉树搜索树⽀持增删查，但是不⽀持修改，修改key破坏搜索树结构了。

场景1：⼩区⽆⼈值守⻋库，⼩区⻋库买了⻋位的业主⻋才能进⼩区，那么物业会把买了⻋位的业主的⻋牌号录⼊后台系统，⻋辆进⼊时扫描⻋牌在不在系统中，在则抬杆，不在则提⽰⾮本⼩区⻋辆，⽆法进⼊。

场景2：检查⼀篇英⽂⽂章单词拼写是否正确，将词库中所有单词放⼊⼆叉搜索树，读取⽂章中的单词，查找是否在⼆叉搜索树中，不在则波浪线标红提⽰。

6.2 key搜索模型整体代码

namespace key
{
template<class K>
struct BSTNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;

BSTNode(const K& key)
:_key(key)
, _left(nullptr)
, _right(nullptr)
{}
};

// Binary Search Tree
// Key
template<class K>
class BSTree
{
//typedef BSTNode<K> Node;
using Node = BSTNode<K>;
public:

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;
}

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;
}

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 (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;

}
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* replaceParent = cur;
Node* replace = cur->_right;
while (replace->_left)
{
replaceParent = replace;
replace = replace->_left;
}

cur->_key = replace->_key;

if (replaceParent->_left == replace)
replaceParent->_left = replace->_right;
else
replaceParent->_right = replace->_right;

delete replace;
}

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);
}

private:
Node* _root = nullptr;
};
}

6.3 key/value搜索场景：

每⼀个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value，增/删/查还是以key为关键字⾛⼆叉搜索树的规则进⾏⽐较，可以快速查找到key对应的value。key/value的搜索场景实现的⼆叉树搜索树⽀持修改，但是不⽀持修改key，修改key破坏搜索树结构了，可以修改value。

场景1：简单中英互译字典，树的结构中(结点)存储key(英⽂)和vlaue(中⽂)，搜索时输⼊英⽂，则同时查找到了英⽂对应的中⽂。

场景2：商场⽆⼈值守⻋库，⼊⼝进场时扫描⻋牌，记录⻋牌和⼊场时间，出⼝离场时，扫描⻋牌，查找⼊场时间，⽤当前时间-⼊场时间计算出停⻋时⻓，计算出停⻋费⽤，缴费后抬杆，⻋辆离场。

场景3：统计⼀篇⽂章中单词出现的次数，读取⼀个单词，查找单词是否存在，不存在这个说明第⼀次出现，（单词，1），单词存在，则++单词对应的次数。

6.4 key/value搜索模型整体代码

namespace key_value
{
template<class K, class V>
struct BSTNode
{
K _key;
V _value;

BSTNode<K, V>* _left;
BSTNode<K, V>* _right;

BSTNode(const K& key, const V& value)
:_key(key)
, _value(value)
, _left(nullptr)
, _right(nullptr)
{}
};

// Binary Search Tree
// Key/value
template<class K, class V>
class BSTree
{
//typedef BSTNode<K> Node;
using Node = BSTNode<K, V>;
public:
// 强制生成构造
BSTree() = default;

BSTree(const BSTree& t)
{
_root = Copy(t._root);
}

BSTree& operator=(BSTree tmp)
{
swap(_root, tmp._root);
return *this;
}

~BSTree()
{
Destroy(_root);
_root = nullptr;
}

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;
}

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;
}

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 (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;

}
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* replaceParent = cur;
Node* replace = cur->_right;
while (replace->_left)
{
replaceParent = replace;
replace = replace->_left;
}

cur->_key = replace->_key;

if (replaceParent->_left == replace)
replaceParent->_left = replace->_right;
else
replaceParent->_right = replace->_right;

delete replace;
}

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 << ":" << root->_value << endl;
_InOrder(root->_right);
}

void Destroy(Node* root)
{
if (root == nullptr)
return;

Destroy(root->_left);
Destroy(root->_right);
delete root;
}

Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;

Node* newRoot = new Node(root->_key, root->_value);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
private:
Node* _root = nullptr;
};
}

原文地址：https://blog.csdn.net/f_2789889770/article/details/142420137

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：screen使用——关机时在服务器上跑代码
下一篇：AIGC时代算法工程师的面试秘籍（第二十二式2024.9.2-9.15） |【三年面试五年模拟】

【大数据入门 | Hive】DDL数据定义语言（数据库DataBase）
注：若不指定路径，其默认路径为${hive.metastore.warehouse.dir}/database_name.db。需要注意的是：修改数据库location，不会改变当前已有表的路径信息，
阅读更多2024-09-24
软件测试基础知识
本文主要介绍了软件测试的一些基本知识点
阅读更多2024-09-24
异常值理解
统计定义在统计学中，异常值通常是指在数据分布的尾部的点。比如，可以用标准差来定义：数据点如果离均值超过一定的标准差范围（如3个标准差），则可视为异常值。领域定义不同领域的异常值可能有不同的含义。在金融
阅读更多2024-09-24
从 Oracle 集群到单节点环境（详细记录一次数据迁移过程）之二：生产服务器的备份操作
（1）设置备份文件格式。
阅读更多2024-09-24
串口问题汇总：串口发送乱码，重定义使用printf ，输出顺序出错，缓存区思想，串口项目应用
这是因为你的编码格式和你的串口助手编码格式不一样，或者你的编码格式压根不支持中文，这里还要特别注意，keil显示乱码那是因为你翻译器解读代码，你改正确了以后并不代表你串口输出也是正确的，因为编译器和翻
阅读更多2024-09-24
STL之vector篇（上）还在为学习vector而感到烦恼吗？每次做算法题都要回忆很久，不如来看看我的文章，精简又易懂，帮你快速掌握vector的相关用法
vector是C++标准模板库（STL）中的一个非常重要和常用的容器。它提供了一种动态数组的功能，即可以在运行时根据需要自动调整其大小以存储元素。与普通的C数组相比，提供了更多的灵活性和安全性。
阅读更多2024-09-24
实现领域驱动设计（DDD）系列详解：集成限界上下文
一个项目中通常存在着多个限界上下文，并且我们需要在它们之间进行集成。在**上下文映射图**中存在两种主要形式：一种是通过绘制一些简单的框图来展示它们之间的集成关系；另一种则是通过代码来实现这些集成关系
阅读更多2024-09-24
【触想智能】工业显示器在智慧城市中的应用市场分析
例如，通过在路口、高速公路等重要交通节点安装工业显示器，可以实时显示交通状况，帮助交警和驾驶员做出准确的决策，提高交通管理的效率和安全性。在技术方面，越来越多的创新技术将被应用于工业显示器中，如触控技
阅读更多2024-09-24
基于YOLOv5s的无人机航拍输电线瓷瓶检测(附数据集与操作步骤)
Coovally利用先进的机器视觉技术和成熟的解决方案，运用YOLO算法进行模型训练，可以对瓷瓶破损、污染及老化等异常状况快速识别。
阅读更多2024-09-24
[万字长文]stable diffusion代码阅读笔记
stable diffusion代码阅读笔记本文参考的配置文件信息:AutoencoderKL:stable-diffusion\configs\autoencoder\autoencoder_kl_
阅读更多2024-09-24