二叉树进阶——二叉搜索树

关于二叉树的基本概念与内容作者在之前的数据结果初阶系列均有讲解,需要的小伙伴可以去作者的往期博客里查看。本篇内容算是对二叉树内容部分的收尾。

一、什么是二叉搜索树

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:

若它的左子树不为空,则左子树上所有节点的值都小于根节点的值

若它的右子树不为空,则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

二叉搜索数采取中序遍历的顺序,这样就会实现数据从小到大的排列。

二、二叉搜索树的相关操作

1.插入数据

我们先手搓一棵树

接下来我们写一下插入函数(insert),先点一下思路:我们要利用二叉搜索树的性质,我们先用插入的数据与根去比,比根小向左走,比根大向右走,这样它最多比较树的高度次即可完成插入(当然,为了不让数据冗余,如果这棵数中已经有和插入的数据一样大的,那么就选择不插入,所以,我们也应完善它的查找功能)。值得一提的是,这个部分可以用循环写。

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)//判断插在left还是right{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;}}
}

2.中序遍历

void inorder(node* root)
{if (root == nullptr){return;}inorder(root->_left);cout << root->_key << " ";inorder(root->_right);
}

看起来没什么问题,但如果我们调用这个传参的时候,发现传根节点指针是不行的,因为是私有成员无法访问,直接写一个子函数放在private嵌套即可:

由此可见,二叉搜索树可以提供我们查找,去重,排序的便利。

3.删除数据 (难点)

我们以下面这棵树为例:

我们发现,删除某一个数据分为三类:没有孩子的删除(1、7),一个孩子的删除(6、14),这两种类型的删除比较简单,释放空间然后让其父节点指向其左右孩子构成新的链接即可(一会我们将用代码实现)。真正麻烦的是第三类:有两个孩子节点的删除(3、8),这里直接提供思路,我们要利用二叉搜索树的性质,假设我们要删除3,只需要在以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(parent==nullptr)//删除根的时候是没有父节点的{_root = cur->_right;}else//正常情况{if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr)//与上面同理{if (parent==nullptr){_root = cur->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;return true;}else//第三种情况,2个孩子{//右子树中的最小节点node* rightminp = cur;node* rightmin = cur->_right;while (rightmin->_left)//找到右子树中的最小{rightminp = rightmin;rightmin = rightmin->_left;}cur->_key = rightmin->_key;//将最小值替换到目标位置if (rightminp->_left == rightmin)//替换后的删除rightminp->_left = rightmin->_right;elserightminp->_right = rightmin->_right;delete rightmin;return true;}}}return false;//上面情况均未满足,即删除失败
}

以上就是二叉树的加餐内容,二叉搜索树是一个非常重要的内容,它是后续许多结构的底层,作者在后续的讲解的时候还会提到这棵树哦。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/422962.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

How to implement custom environment in keras-rl / OpenAI GYM?

题意&#xff1a;如何在 Keras-RL / OpenAI GYM 中实现自定义环境&#xff1f; 问题背景&#xff1a; Im a complete newbie to Reinforcement Learning and have been searching for a framework/module to easily navigate this treacherous terrain. In my search Ive come…

axure判断

在auxre中我们也可以实现判断的功能&#xff0c;当目标等于什么内容时则执行下方的功能。 一、判断输入框中是否有值 画布添加一个输入框、一个文本标签删除其中内容&#xff0c;添加一个按钮&#xff0c;输入框命名为【文本显示】文本标签命名为【提示】 给按钮新增一个交互…

缓存预热/雪崩/穿透/击穿

1. 缓存预热 预先将MySQL中的数据同步至Redis的过程 2. 缓存雪崩 Redis主机出现故障&#xff0c;或有大量的key同时过期大面积失效导致Redis不可用 Redis中key设置为永不过期&#xff0c;或者过期时间错开Redis缓存集群实现高可用多缓存结合预防雪崩服务降级 3. 缓存穿透 …

消息队列面试

一、基础实战 &#xff08;一&#xff09;MQ的作用&#xff1a;异步、解耦、流量削峰填谷 &#xff08;二&#xff09;MQ应用场景 传统的金融项目一般使用IBMMQ&#xff08;收费&#xff09;&#xff0c;比如某丰银行项目。ActiveMQ已经成为历史&#xff0c;因为现在很少使用…

Redis 篇-深入了解基于 Redis 实现消息队列(比较基于 List 实现消息队列、基于 PubSub 发布订阅模型之间的区别)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 消息队列的认识 2.0 基于 List 实现消息队列 2.1 基于 List 实现消息队列的优缺点 3.0 基于 PubSub 实现消息队列 3.1 基于 PubSub 的消息队列优缺点 4.0 基于 St…

Unity数据持久化 之 使用Excel.DLL读写Excel表格

本文仅作笔记学习和分享&#xff0c;不用做任何商业用途 本文包括但不限于unity官方手册&#xff0c;unity唐老狮等教程知识&#xff0c;如有不足还请斧正​​ 终于找到一个比较方便容易读表的方式了&#xff0c;以前用json读写excel转的cvs格式文件我怎么使用怎么别扭&#xf…

AlmaLinux 9 上配置静态 IP 地址

在 Rocky Linux 9 中&#xff0c;密钥文件的新默认存储位置在 /etc/NetworkManager/system-connections 中 cd /etc/NetworkManager/system-connections默认dhcp配置 ~ …

免费SSL证书正在逐渐被淘汰,证书部署自动化的发展趋势即将到来!

目录 背景解决方案。1.使用自签证书&#xff08;浏览器报警、免费&#xff09;2.更换支持自签自续的CA机构&#xff08;免费&#xff09;3.付费选择CA机构 免费SSL证书正在逐渐被淘汰&#xff0c;证书部署自动化的发展趋势即将到来免费的SSL证书有以下弊端1.有效期短&#xff1…

stm32驱动开发与linux驱动的区别

stm32&#xff0c;gpio设置原理 下图&#xff0c;定义了gpio E的基地址&#xff0c;只要将这个地址强制转换成gpiotypedf的类型&#xff0c;解析时&#xff0c;结构体地址就会自增。这样就可以对不同gpio组&#xff0c;就像定义。 全部gpio定义&#xff0c;强制为结构体类型…

Linux CentOS更换阿里云源解决Could not retrieve mirrorlist http://mirrorlist.centos.org

Linux CentOS7 更新yum 操作的时候出现这个问题&#xff1a; Loading mirror speeds from cached hostfile Could not retrieve mirrorlist http://mirrorlist.centos.org 然后我执行 grep -nr "mirrorlist.centos.org" /etc/yum.repos.d/* 出现 这个问题时可以…

搭建 WordPress 及常见问题与解决办法

浪浪云活动链接 &#xff1a;https://langlangy.cn/?i8afa52 文章目录 环境准备安装 LAMP 堆栈 (Linux, Apache, MySQL, PHP)配置 MySQL 数据库 安装 WordPress配置 WordPress常见问题及解决办法数据库连接错误白屏问题插件或主题冲突内存限制错误 本文旨在介绍如何在服务器上…

爬虫使用代理IP后报错?解决方案在这里!

在数据抓取的过程中&#xff0c;使用代理IP是避免被封禁、提高抓取效率的重要手段。然而&#xff0c;有时候即使配置了代理IP&#xff0c;依然会遇到各种报错问题。本文将详细解析常见的报错类型&#xff0c;并提供解决方案&#xff0c;帮助你顺利进行数据抓取。 常见报错类型…

MySQL表的操作与数据类型

目录 前言 一、表的操作 1.创建一个表 2.查看表的结构 3.修改表 4.删除一个表 二、 MySQL的数据类型 0.数据类型一览&#xff1a; 1.整数类型 2.位类型 3.小数类型 4.字符类型 前言 在MySQL库的操作一文中介绍了有关MySQL库的操作&#xff0c;本节要讲解的是由库管理的结构——…

智能体 vs AI智能体:区别与联系,一文读懂!

​ 在AI技术蓬勃发展的今天&#xff0c;“智能体”&#xff08;Agent&#xff09;和”AI智能体”&#xff08;AI Agent&#xff09;两个概念经常被提及&#xff0c;二者在很多场合下会被混淆&#xff0c;但其实它们有着不同的定义和应用。我觉得很有必要小小科普下两者的定义与…

软件测试学习笔记丨Pytest的使用

本文转自测试人社区&#xff0c;原文链接&#xff1a;https://ceshiren.com/t/topic/22158 1. 简介 pytest是一个成熟的全功能python测试框架测试用例的skip和xfail&#xff0c;自动失败重试等处理能够支持简单的单元测试和复杂的功能测试&#xff0c;还可以用来做selenium/ap…

HTML的块级元素与行内元素

在HTML中&#xff0c;元素可以分为两大类&#xff1a;块级元素&#xff08;block-level elements&#xff09;和行内元素&#xff08;inline elements&#xff09;。这两种类型的元素在网页布局和呈现中扮演着不同的角色。 块级元素&#xff08;Block-level Elements&#xff…

CMU 10423 Generative AI:HW1(编程部分:在GPT-2模型中实现RoPE、GQA)

完整代码和PDF笔记&#xff1a;https://github.com/YM2025/CMU_10423_2024S 文章目录 1 概述Rotary Positional Embeddings (RoPE)Grouped Query Attention (GQA)实验任务 2 项目文件1. requirements.txt2. input.txt3. chargpt.py4. mingpt/a. model.pyb. trainer.pyc. utils.…

毕业论文选题难?5招帮你轻松搞定选题!

AIPaperGPT&#xff0c;论文写作神器~ https://www.aipapergpt.com/ 你是不是已经为毕业论文的选题愁得头发都要掉光了&#xff1f;每次打开文档&#xff0c;都觉得什么都想写&#xff0c;又好像什么都写不了。选题看起来很简单&#xff0c;但真正开始动手的时候&#xff0c;…

深入探索系统架构设计

目录 前言 软件的体系结构 软件架构定义 软件架构设计与生命周期 1、需求分析阶段 2、设计阶段 3、实现阶段 4、构件组装阶段 5、部署阶段 6、后开发阶段 软件架构的重要性 1、架构设计能够满足系统的品质 2、架构设计使受益人达成一致的目标 3、架构设计能够支持…

UDS 诊断 - RequestTransferExit(请求传输终止)(0x37)服务

UDS 诊断服务系列文章目录 诊断和通信管理功能单元 UDS 诊断 - DiagnosticSessionControl&#xff08;诊断会话控制&#xff09;&#xff08;0x10&#xff09;服务 UDS 诊断 - ECUReset&#xff08;ECU重置&#xff09;&#xff08;0x11&#xff09;服务 UDS 诊断 - SecurityA…