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

        二叉搜索树是一个很重要的数据结构，它的特殊结构可以在很短的时间复杂度找到我们想要的数据。最坏情况下的时间复杂度是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.xdnf.cn/news/1536893.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

docker部署Stirling-PDF

docker部署Stirling-PDF

github网址&#xff1a; GitHub - Stirling-Tools/Stirling-PDF: #1 Locally hosted web application that allows you to perform various operations on PDF files 1、官方docker镜像无法拉取&#xff0c;使用别人阿里云私人镜像仓库下载Stirling-PDF镜像&#xff1a; regi…
阅读更多...
微服务以及注册中心

微服务以及注册中心

一、什么是微服务 微服务是指开发一个单个小型的但有业务功能的服务&#xff0c;每个服务都有自己的处理和轻量通讯机制&#xff0c;可以部署在单个或多个服务器上。微服务也指一种松耦合的、有一定的有界上下文的面向服务架构。也就是说&#xff0c;如果每个服务都要同时修改…
阅读更多...
Objects as Points基于中心点的目标检测方法CenterNet—CVPR2019

Objects as Points基于中心点的目标检测方法CenterNet—CVPR2019

Anchor Free目标检测算法—CenterNet Objects as Points论文解析 Anchor Free和Anchor Base方法的区别在于是否在检测的过程中生成大量的先验框。CenterNet直接预测物体的中心点的位置坐标。 CenterNet本质上类似于一种关键点的识别。识别的是物体的中心点位置。 有了中心点之…
阅读更多...
AI助力遥感影像智能分析计算，基于高精度YOLOv5全系列参数【n/s/m/l/x】模型开发构建卫星遥感拍摄场景下地面建筑物智能化分割检测识别系统

AI助力遥感影像智能分析计算，基于高精度YOLOv5全系列参数【n/s/m/l/x】模型开发构建卫星遥感拍摄场景下地面建筑物智能化分割检测识别系统

随着科技的飞速发展&#xff0c;卫星遥感技术已成为获取地球表面信息的重要手段之一。卫星遥感图像以其覆盖范围广、数据量大、信息丰富等特点&#xff0c;在环境监测、城市规划、灾害评估等多个领域发挥着不可替代的作用。然而&#xff0c;面对海量的卫星图像数据&#xff0c;…
阅读更多...
wx小程序渗透思路

wx小程序渗透思路

免责声明:本文仅做分享! 目录 WX小程序源代码 wx小程序目录位置: 反编译: e0e1-wx.py工具 unveilr.exe工具 查看源代码: 微信开发者工具: WX抓包 Fiddler抓包 官网下载 下载证书 操作: bp proxifier bp:(代理抓包) proxifier:(本地代理) WX小程序源代码 其实就…
阅读更多...
程序修改题（41-50）

程序修改题（41-50）

第四十一题 题目 给定程序modi1.c的主函数中&#xff0c;将a、b、c三个结点链成一个单向链表&#xff0c;并给各结点的数据域赋值&#xff0c;函数fun()的作用是:累加链表结点数据域中的数据作为函数值返回。 #include <stdio.h> typedef struct list { int data…
阅读更多...
【数据结构-扫描线】力扣57. 插入区间

【数据结构-扫描线】力扣57. 插入区间

给你一个 无重叠的 &#xff0c;按照区间起始端点排序的区间列表 intervals&#xff0c;其中 intervals[i] [starti, endi] 表示第 i 个区间的开始和结束&#xff0c;并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval [start, end] 表示另一个区间的开始和…
阅读更多...
李宏毅结构化学习 02

李宏毅结构化学习 02

文章目录 一、上篇博文复习二、Separable Case三、Non-separable Case四、Considering Errors五、Regularization六、Structured SVM七、Cutting Plane Algorithm for Structured SVM八、Multi-class and binary SVM九、Beyond Structured SVM 一、上篇博文复习 图中x表示输入的…
阅读更多...
Android Framework（六）WMS-窗口显示流程——窗口内容绘制与显示

Android Framework（六）WMS-窗口显示流程——窗口内容绘制与显示

文章目录 窗口显示流程明确目标 窗户内容绘制与显示流程窗口Surface状态完整流程图 应用端处理finishDrawingWindow 的触发 system_service处理WindowState状态 -- COMMIT_DRAW_PENDING本次layout 流程简述 窗口显示流程 目前窗口的显示到了最后一步。 在 addWindow 流程中&…
阅读更多...
基于Python的自然语言处理系列（10）：使用双向LSTM进行文本分类

基于Python的自然语言处理系列（10）：使用双向LSTM进行文本分类

在前一篇文章中&#xff0c;我们介绍了如何使用RNN进行文本分类。在这篇文章中&#xff0c;我们将进一步优化模型&#xff0c;使用双向多层LSTM来替代RNN&#xff0c;从而提高模型在序列数据上的表现。LSTM通过引入一个额外的记忆单元&#xff08;cell state&#xff09;来解决…
阅读更多...
24.Redis实现全局唯一ID

24.Redis实现全局唯一ID

是一种分布式系统下用来生成全局唯一ID的工具。 特点 1.唯一性 2.高可用 3.高性能 4.递增性&#xff0c;数据也要保持一种递增&#xff0c;有利于数据库进行查询。 5.安全性 全局唯一ID的生成策略 1.UUID(没有顺序&#xff0c;字符串类型&#xff0c;效率不高) 2.Redis…
阅读更多...
【电路笔记】-差分运算放大器

【电路笔记】-差分运算放大器

差分运算放大器 文章目录 差分运算放大器1、概述2、差分运算放大器表示2.1 差分模式2.2 减法器模式3、差分放大器示例3.1 相关电阻3.2 惠斯通桥3.3 光/温度检测4、仪表放大器5、总结1、概述 在之前的文章中，我们讨论了反相运算放大器和同相运算放大器，我们考虑了在运算放大器…
阅读更多...
floodfill算法（二）

floodfill算法（二）

目录 一、太平洋大西洋水流问题 1. 题目链接&#xff1a;417. 太平洋大西洋水流问题 2. 题目描述&#xff1a; 3. 解法 &#x1f334;算法思路&#xff1a; &#x1f334;算法代码&#xff1a; 二、扫雷游戏 1. 题目链接&#xff1a;529. 扫雷游戏 2. 题目描述&#xf…
阅读更多...
softmax回归的从零实现（附代码）

softmax回归的从零实现（附代码）

softmax回归是一个多分类模型&#xff0c;但是他跟线性回归一样将输入特征与权重做线性叠加&#xff0c;与线性不同的是他有多个输出&#xff0c;输出的个数对应分类标签的个数&#xff0c;比如四个特征和三种输出动物类别&#xff0c;则权重包含12个标量&#xff08;带下标的w…
阅读更多...
深度学习之线性代数预备知识点

深度学习之线性代数预备知识点

概念定义公式/案例标量(Scalar)一个单独的数值&#xff0c;表示单一的量。例如&#xff1a;5, 3.14, -2向量 (Vector)一维数组&#xff0c;表示具有方向和大小的量。 &#xff0c;表示三维空间中的向量 模(Magnitude)向量的长度&#xff0c;也称为范数&#xff08;通常为L2范数…
阅读更多...
HCIA--实验十六：ACL通信实验（2）

HCIA--实验十六：ACL通信实验（2）

2.高级ACL配置 一、实验内容 1.需求/要求&#xff1a; 使用三台PC和一台交换机&#xff0c;在交换机上配置高级ACL&#xff0c;测试PC1、PC2、PC3间的连通性。 二、实验过程 1.拓扑图&#xff1a; 2.步骤&#xff1a; 1.给PC3配置ip地址&#xff1a; 2.给交换机SW3配置高…
阅读更多...
Hello，Spring Boot...

Hello，Spring Boot...

今天开启了Spring Boot学习之旅。 首先就是&#xff0c;JDK、Maven、IDEA以及各种官网的下载、安装与配置 然后通过组件创建小类&#xff0c;最让人头痛的就是&#xff0c;这个spring-boot-starter-thymeleaf&#xff0c;下错版本了 其他的一切顺利&#xff0c;自动化明显 最后…
阅读更多...
2024最新版mysql数据库表的查询操作-总结

2024最新版mysql数据库表的查询操作-总结

序言 1、MySQL表操作(创建表&#xff0c;查询表结构&#xff0c;更改表字段等)&#xff0c; 2、MySQL的数据类型(CHAR、VARCHAR、BLOB,等)&#xff0c; 本节比较重要&#xff0c;对数据表数据进行查询操作&#xff0c;其中可能大家不熟悉的就对于INNER JOIN(内连接)、LEFT JOIN…
阅读更多...
Learn ComputeShader 15 Grass

Learn ComputeShader 15 Grass

1.Using Blender to create a single grass clump 首先blender与unity的坐标轴不同&#xff0c;z轴向上&#xff0c;不是y轴 通过小键盘的数字键可以快速切换视图&#xff0c;选中物体以后按下小键盘的点可以将物体聚焦于屏幕中心 首先我们创建一个平面&#xff0c;宽度为0.2…
阅读更多...
SpringBoot中使用EasyExcel并行导出多个excel文件并压缩zip后下载

SpringBoot中使用EasyExcel并行导出多个excel文件并压缩zip后下载

❃博主首页 &#xff1a; 「码到三十五」 &#xff0c;同名公众号 :「码到三十五」&#xff0c;wx号 : 「liwu0213」 ☠博主专栏 &#xff1a; <mysql高手> <elasticsearch高手> <源码解读> <java核心> <面试攻关> ♝博主的话 &#xff1a…
阅读更多...
最新文章

Copyright @ 2022~2023