数据结构——“二叉搜索树”

news/2024/9/23 18:09:01/

        二叉搜索树是一个很重要的数据结构，它的特殊结构可以在很短的时间复杂度找到我们想要的数据。最坏情况下的时间复杂度是O(n)，最好是O(logn)。接下来看一看它的接口函数的实现。

        为了使用方便，这里采用模版的方式：

一、节点

template <class K>
struct BSnode
{BSnode(K key):_key(key){}K _key;BSnode* _left = nullptr;BSnode* _right = nullptr;
};

        _key用来储存数据，_left和_right用来储存左子树和右子树的节点。

二、搜索树的类的定义

template <class K>
class BSTree
{
private:using Node = BSnode<K>;Node* _root = nullptr;
};

        这里typedef了BSnode<K>为Node的类型，方便使用。并创建了根节点，缺省值为空指针。

三、搜索树的插入

        搜索树的结构是左子树所有节点的值小于等于根结点的值，右子树所有节点的值大于等于根节点的值。在这里我不考虑等于的情况，即一棵树中不允许出现相同的值。代码如下：

	//搜索树的插入bool Insert(K& key){Node* cur = _root;Node* parent = nullptr;if (cur == nullptr){_root = new Node(key);}else{while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}if (key > parent->_key)//插入的值大于父亲节点，那么就需要在父亲节点的右边插入{parent->_right = new Node(key);}else//插入的值小于父亲节点，那么就需要在父亲节点的左边插入{parent->_left = new Node(key);}}return true;}

        代码大体情况如下：

        1.第一次插入数据的时候，根节点指向空，需要单独讨论。

        2.根节点不为空，那么就根据搜索树的特点找到最后插入的位置，申请新节点，连接新节点。

        3.找不到插入的位置，即插入的数据已经存在，返回false。

四、搜索树的查找

	//搜索树的查找Node* Find(const K& key){assert(_root);Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key <  key){cur = cur->_right;}else{return cur;}}return nullptr;}

        这段代码是根据搜索树的特点进行查找（搜索的值大于根，那么去右子树查找，小于则去左子树查找），倘若找到，返回该节点指针，找不到，返回空指针。

五、搜索树的删除

        搜索树的删除偏向复杂，在我写出的代码中大致分为以下几点：

        1.删除的数据在叶子节点上。

        2.删除的节点不在叶子节点上，但是它的左右节点至少有一个是空。

        3.删除的节点不在叶子节点上，且左右子树都不为空。

        4.删除的节点在根节点，根节点至少有一个为空。

通过总结可以精简以上条件：

        1.删除的节点的左右节点至少有一个为空。

        2.删除的节点的左右节点都不为空。

代码如下：

	//搜索二叉树的删除bool Erase(const K& key){assert(_root);//先找到要删除的节点Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{break;}}//找不到要删除的数据，返回falseif (cur == nullptr)return false;//找到了//处理“该节点的左孩子或者右孩子为空,或者左右孩子均为空”if (cur->_left == nullptr || cur->_right == nullptr){//该节点是根，且且根节点至少一个子树为空if (parent == nullptr)//parent为空，证明输入的是根节点，且根节点至少一个子树为空 {_root->_left == nullptr ? _root = _root->_right : _root = _root->_left;delete cur;}//该节点是左孩子else if (cur == parent->_left){//左节点为空if (cur->_left == nullptr && cur->_right != nullptr){parent->_left = cur->_right;}//右节点为空else if(cur->_left != nullptr && cur->_right == nullptr){parent->_left = cur->_left;}//左右节点均为空else{parent->_left = nullptr;}//释放资源delete cur;}//该节点是右孩子else if (cur == parent->_right){//左节点为空if (cur->_left == nullptr && cur->_right != nullptr){parent->_right = cur->_right;}//右节点为空else if (cur->_left != nullptr && cur->_right == nullptr){parent->_right = cur->_left;}//左右节点均为空else{parent->_right = nullptr;}//释放资源delete cur;}}
//处理“该节点的左右孩子均不为空”else{//找到左节点的最大值Node* Fparent = cur;Node* Fcur = cur->_left;while (Fcur ->_right){Fparent = Fcur;Fcur = Fcur->_right;}//交换节点的值cur->_key = Fcur->_key;//Fcur的左边有数据if (Fcur->_left){Fparent->_right = Fcur->_left;delete Fcur;}//Fcur的左边没有数据else{if(Fcur == Fparent->_left){Fparent->_left = nullptr;}else{Fparent->_right = nullptr;}delete Fcur;}}return true;}

        首先是先要找到删除的数据，若找不到，返回false，若找到，那么进行下一步：

找到后还有如下情况：

        1.删除的节点的左右节点至少有一个为空。

        对应代码：

//处理“该节点的左孩子或者右孩子为空,或者左右孩子均为空”if (cur->_left == nullptr || cur->_right == nullptr){//该节点是根，且且根节点至少一个子树为空if (parent == nullptr)//parent为空，证明输入的是根节点，且根节点至少一个子树为空 {_root->_left == nullptr ? _root = _root->_right : _root = _root->_left;delete cur;}//该节点是左孩子else if (cur == parent->_left){//左节点为空if (cur->_left == nullptr && cur->_right != nullptr){parent->_left = cur->_right;}//右节点为空else if(cur->_left != nullptr && cur->_right == nullptr){parent->_left = cur->_left;}//左右节点均为空else{parent->_left = nullptr;}//释放资源delete cur;}//该节点是右孩子else if (cur == parent->_right){//左节点为空if (cur->_left == nullptr && cur->_right != nullptr){parent->_right = cur->_right;}//右节点为空else if (cur->_left != nullptr && cur->_right == nullptr){parent->_right = cur->_left;}//左右节点均为空else{parent->_right = nullptr;}//释放资源delete cur;}}

        原理：由于删除的节点左右子树至少有一个为空，那么就可以让父节点继承被删除节点的非空节点。继承后，删除该节点。如果被删除的节点的左右子树都为空，即被删除的节点是叶子节点，那么就可以直接删除叶子节点，然后将父节点指向空。

        以上代码分别对删除的节点是左子树还是右子树的情况下，删除的节点是否有左子树，是否有右子树，还是左右子树都没有进行讨论，涵盖所有情况。值得注意的是，当搜索树呈现链状的时候，如果删除的是根节点，此时的父节点是空，不能进行访问，那么需要在这里单独讨论。将根节点移动到有数据的那个子节点。

2.删除的节点的左右节点都不为空。

        对应代码：

//处理“该节点的左右孩子均不为空”else{//找到左节点的最大值Node* Fparent = cur;Node* Fcur = cur->_left;while (Fcur ->_right){Fparent = Fcur;Fcur = Fcur->_right;}//交换节点的值cur->_key = Fcur->_key;//Fcur的左边有数据if (Fcur->_left){Fparent->_right = Fcur->_left;delete Fcur;}//Fcur的左边没有数据else{if(Fcur == Fparent->_left){Fparent->_left = nullptr;}else{Fparent->_right = nullptr;}delete Fcur;}}

        第二种情况就不能直接进行交换。因为父节点没有多余的指针指向被删除节点的左右节点。那么在这里的思想是找到一个比被删除的节点的左孩子大，右孩子小。符合条件的是：左子树的最大值，或者右子树的最小值。找到之后交换节点值。但是还是需要注意的是，找到最大值以后，分为两种情况：

        a.最大值的左边为空。

        b.最大值的左边不为空。

那么进行讨论：比如删除的数据是8。

a.最大值的左边为空：

这个条件下可以直接交换删除

b.最大值的左边不为空：

        这种情况下就需要将父节点的右节点（最大值的位置）指向最大值的左节点。

在这段代码中：

			//找到左节点的最大值Node* Fparent = cur;Node* Fcur = cur->_left;while (Fcur ->_right){Fparent = Fcur;Fcur = Fcur->_right;}

        Node* Fparent = cur;的目的是避免这种情况下，空指针解引用的问题：删除的数据是3：

倘若Fparent 为空

        此时Fcur已经为叶子节点（已经为3的左子树的最大值），while循环不会进而以下代码会对Fparent解引用，造成访问空指针的错误。如果将Fparent复制为cur，那么从一开始，Fparent就是Fcur的父节点，既不违反逻辑，也解决了问题。

        因为此时1在父节点的左边，所以综上所述，再删除节点的同时也是需要判断被删除的节点是左节点还是右节点。

示例：

int main()
{BSTree<int> tree;int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto f : a){tree.Insert(f);}for (auto f : a){tree.Erase(f);tree.InTraversal();cout << endl;}return 0;
}

结果（中序遍历）：


http://www.ppmy.cn/news/1529437.html

相关文章

【监控】【Nginx】使用 Docker 部署 Prometheus + Grafana 监控 Nginx

【监控】【Nginx】使用 Docker 部署 Prometheus + Grafana 监控 Nginx

在现代应用程序中&#xff0c;监控是确保服务高可用性和性能的关键。本文将详细介绍如何使用 Docker 部署 Prometheus 和 Grafana&#xff0c;以监控 Nginx。我们将分步骤讲解每个环节&#xff0c;以确保你能够顺利完成整个过程。 准备工作 在开始之前&#xff0c;请确保你的…
阅读更多...
Redis详细解析

Redis详细解析

Redis 什么是Redis?关系型与非关系型数据库Redis可以做什么Redis入门安装在Windows系统上安装在Linux系统上安装 Redis在Linux系统上启动运行如何设置redis-server后台运行与关闭如何设置redis客户端登录时需要验证密码**设置允许远程连接redis服务**Redis数据类型Redis常用命…
阅读更多...
帝可得项目总结

帝可得项目总结

业务需求 在区域列表查询中&#xff0c;需要显示每个区域的点位数 (1)同步存储:在区域表中有点位数的字段&#xff08;冗余字段6.&#xff09;&#xff0c;当点位发生变化时&#xff0c;同步区域表中的点位数。 优点:由于是单表查询操作&#xff0c;查询列表效率最高。 缺点…
阅读更多...
RHEL7(RedHat红帽)软件安装教程

RHEL7(RedHat红帽)软件安装教程

目录 1、下载RHEL7镜像 2、安装RedHat7 注&#xff1a;如果以下教程不想看&#xff0c;可以远程控制安装V:OYH-Cx330 【风险告知】 本人及本篇博文不为任何人及任何行为的任何风险承担责任&#xff0c;图解仅供参考&#xff0c;请悉知&#xff01;本次安装图解是在一个全新的演…
阅读更多...
【人工智能学习之卷积神经网络发展简述】

【人工智能学习之卷积神经网络发展简述】

【人工智能学习之卷积神经网络发展简述】 早期探索&#xff08;1960s-1980s&#xff09;初步发展&#xff08;1990s-2000s&#xff09;快速增长&#xff08;2010s&#xff09;当前进展&#xff08;2010s末-2020s&#xff09;未来趋势总结 卷积神经网络&#xff08;Convolutiona…
阅读更多...
[论文笔记]MRRNET

[论文笔记]MRRNET

这是一篇河大的论文 感觉跟SANET很像 摘要 摘要&#xff1a;随着物联网&#xff08;IoT&#xff09;的大规模部署&#xff0c;道路场景中实时感知和环境理解的需求变得越来越迫切。 同时&#xff0c;语义分割作为像素级场景解析得到了广泛的研究。 然而&#xff0c;资源有限…
阅读更多...
解决 TortoiseGitPlink Fatal Error：深入解析

解决 TortoiseGitPlink Fatal Error：深入解析

解决 TortoiseGitPlink Fatal Error&#xff1a;深入解析 在 Windows 平台上&#xff0c;开发者使用 Git 和 TortoiseGit 进行版本控制时&#xff0c;有时会遇到 TortoiseGitPlink Fatal Error。该错误通常是在推送/拉取代码时&#xff0c;客户端未能提供正确的 SSH 密钥。 1…
阅读更多...
11年408考研真题解析-计算机网络

11年408考研真题解析-计算机网络

第一题&#xff1a; 解析&#xff1a;网络层虚电路服务和数据报服务 传输服务只有&#xff1a;有连接可靠和无连接不可靠两种&#xff0c;直接排除BC。 网络层指的是IP协议&#xff0c;由图二可知&#xff1a;运输层&#xff0c;网际层&#xff0c;网络接口层唯一有连接可靠的协…
阅读更多...
最新文章

Copyright @ 2022~2023