数据结构之二叉搜索树
二叉搜索树
满足条件:
1.对于根节点:左子树中所有节点的值小于右子树中所有节点的值
2.任意节点的左右子树也是二叉搜索树,同样满足条件1
二叉搜索树的常用操作
我们将二叉搜索树封装为一个类
BinarySearchTree,并声明一个成员变量root,指向树的根节点
查找节点
给定目标值target,我们可以根据二叉搜索树的性质来查找,声明一个节点cur从根节点开始遍历
- 若
cur.val<target说明target在cur的右子树,执行cur=cur.right - 若
cur.val>target说明target在cur的左子树,执行cur=cur.left - 若
cur.val=target,返回该节点,跳出循环
/* 查找节点 */
TreeNode *search(int num) {TreeNode *cur = root;// 循环查找,越过叶节点后跳出while (cur != nullptr) {// 目标节点在 cur 的右子树中if (cur->val < num)cur = cur->right;// 目标节点在 cur 的左子树中else if (cur->val > num)cur = cur->left;// 找到目标节点,跳出循环elsebreak;}// 返回目标节点return cur;
}
插入节点
查找插入位置:从根节点出发,根据当前节点值和
num的大小关系循环向下搜索,直到越过叶节点(遍历至None)时跳出循环在该位置插入节点:初始化节点
num,将该节点置于None的位置。注意:
二叉搜索树中不允许有重复的元素,否则就违反了二叉搜索树的定义,若待插入的节点在二叉搜索树中,则不执行任何操作,直接返回
为了实现插入节点,我们需要借助节点
pre保存上一轮循环的节点。这样在遍历至None时,我们可以获取到其父节点,从而完成节点插入操作
/* 插入节点 */
void insert(int num) {// 若树为空,则初始化根节点if (root == nullptr) {root = new TreeNode(num);return;}TreeNode *cur = root, *pre = nullptr;// 循环查找,越过叶节点后跳出while (cur != nullptr) {// 找到重复节点,直接返回if (cur->val == num)return;pre = cur;// 插入位置在 cur 的右子树中if (cur->val < num)cur = cur->right;// 插入位置在 cur 的左子树中elsecur = cur->left;}// 插入节点TreeNode *node = new TreeNode(num);if (pre->val < num)pre->right = node;elsepre->left = node;
}
删除节点
二叉搜索树的删除分为三种情况
- 当待删除节点的度为0时,可以直接删除这个节点。
- 当待删除节点的度为1时,我们将子节点替换待删除的节点即可
- 当待删除节点的度为2时,我们无法删除这个节点,而是需要一个节点替换这个节点,因为要维持搜索二叉树的性质,所以这个待删除节点的值可以是右子树的最小节点或者左子树的最大节点
/* 删除节点 */
void remove(int num) {// 若树为空,直接提前返回if (root == nullptr)return;TreeNode *cur = root, *pre = nullptr;// 循环查找,越过叶节点后跳出while (cur != nullptr) {// 找到待删除节点,跳出循环if (cur->val == num)break;pre = cur;// 待删除节点在 cur 的右子树中if (cur->val < num)cur = cur->right;// 待删除节点在 cur 的左子树中elsecur = cur->left;}// 若无待删除节点,则直接返回if (cur == nullptr)return;// 子节点数量 = 0 or 1if (cur->left == nullptr || cur->right == nullptr) {// 当子节点数量 = 0 / 1 时, child = nullptr / 该子节点TreeNode *child = cur->left != nullptr ? cur->left : cur->right;// 删除节点 curif (cur != root) {if (pre->left == cur)pre->left = child;elsepre->right = child;} else {// 若删除节点为根节点,则重新指定根节点root = child;}// 释放内存delete cur;}// 子节点数量 = 2else {// 获取中序遍历中 cur 的下一个节点TreeNode *tmp = cur->right;while (tmp->left != nullptr) {tmp = tmp->left;}int tmpVal = tmp->val;// 递归删除节点 tmpremove(tmp->val);// 用 tmp 覆盖 curcur->val = tmpVal;}
}
相关文章:
数据结构之二叉搜索树
二叉搜索树 满足条件: 1.对于根节点:左子树中所有节点的值小于右子树中所有节点的值 2.任意节点的左右子树也是二叉搜索树,同样满足条件1 二叉搜索树的常用操作 我们将二叉搜索树封装为一个类 BinarySearchTree ,并声明一个成员变…...
《设计模式的艺术》笔记 - 抽象工厂模式
介绍 提供了一个创建一系列相关或相互依赖的对象的接口,而无须指定它们具体的类。抽象工厂模式又称为Kit模式,它是一种对象创建型模式。 在抽象工厂模式中,每个具体工厂都提供了多个工厂方法用于产生多种不同类型的产品,这些产品构…...
7.11、Kali Linux中文版虚拟机安装运行教程
目录 一、资源下载准备工作 二、安装教程 三、kali linux换源 四、apt-get update 报错 一、资源下载准备工作 linux 中文版镜像历史版本下载:http://old.kali.org/kali-images/ 大家可以自行选择版本下载,本人下载的是2021版本 二、安装教程 打开vmvare wokst…...
Go+快速开始详细指南
Go快速开始 Go编程语言是为工程、STEM教育和数据科学设计的。 对于工程:用儿童能掌握的最简单的语言工作。对于STEM教育:学习一门可以在未来工作中使用的工程语言。对于数据科学:用同一种语言与工程师交流。 安装方法 现在,我们建议您从源代码安装Go。 注意:需…...
SQL:一行中存在任一指标就显示出来
当想要统计的两个指标不在一张表中时,需要做关联。但很多情况下,也没有办法保证其中一张表的维度是全的,用left join或right join可能会导致数据丢失。所以借助full join处理。 1)如,将下面的数据处理成表格中的效果&…...
【代码随想录06】454. 四数相加 II 383. 赎金信 15. 三数之和 18. 四数之和
目录 454. 四数相加 II题目描述做题思路参考代码 383. 赎金信题目描述做题思路参考代码 15. 三数之和题目描述参考代码 18. 四数之和题目描述参考代码 454. 四数相加 II 题目描述 给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请你…...
NodeJs 第十五章 session
Session代表服务器和客户端一次会话的过程。 在计算机科学领域来说,尤其是在网络领域,会话(session)是一种持久网络协议,在用户(或用户代理)端和服务器端之间创建关联,从而起到交换数据包的作用机制,session在网络协议…...
JRTP实时音视频传输(1)-必做的环境搭建与demo测试
1.需求 1)支持协议自动切换。在网络优的情况下使用TCP、网络差的情况下使用UDP,满足实时音视频传输需求, 2)支持RTCP ,流量控制,阻塞控制等。需要能支持RTCP,这样便能在这个基础上,…...
腿部臀部训练
坐式蹬腿器 100kg,是器械的极限了,也差不多是我的极限,深蹲是40kg,应该还可以加点,大腿外扩器55kg,没有尝试能不能做更重的,羡慕健身房里面的好身材的同学,自己得好好练 1.21健身房关…...
windows系统下docker软件中使用ubuntu发行版本的linux系统
1.软件下载 官网下载地址 下载安装之后,再去微软商店下载wsl软件,可以直接用,或者也可以使用命令行拉取(下面会讲) 2.在docker里面创建容器的两种方法 2.1.命令行创建 前言:输入 winr 打开命令行进行下面…...
vue实现小球掉落
首先,将小球儿动画代码封装成组件,创建个文件,例如qiu.js let createBall (left, top,box) > {// 点击事件 const {clientX,clienty} ev createBall(clientX,clienty)const ball document.createElement(div);ball.style.position a…...
k8s的存储卷、数据卷---动态PV创建
当发布PVC之后可以生成PV,还可以在动态服务器上直接生成挂载目录。PVC直接绑定和使用PV。 动态PV需要两个组件 存储卷插件:Provisioner(存储分配器)根据定义的属性创建PV StorageClass:定义属性 存储卷插件 存储卷插件:k8s本…...
go最佳实践:如何舒适地编码
什么是 "最佳 "做法? 有很多做法:你可以自己想出来,在互联网上找到,或者从其他语言中拿来,但由于其主观性,并不总是容易说哪一个比另一个好。”最佳”的含义因人而异,也取决于其背景…...
C# 消息队列、多线程、回滚、并行编程、异步编程、反射
消息队列 消息队列是一种在应用程序之间传递消息的异步通信机制。它可以使应用程序解耦并提高系统的可伸缩性和可靠性。在 C# 中,你可以使用多个消息队列技术,其中一种广泛使用的技术是 RabbitMQ。 RabbitMQ 是一个开源的消息代理,实现了高…...
汇编代码生成和编译器的后端
1.前置程序:语义分析和中间代码生成 基于SLR(1)分析的语义分析及中间代码生成程序-CSDN博客https://blog.csdn.net/lijj0304/article/details/135097554?spm1001.2014.3001.5501 2.程序目标 在前面编译器前端实现的基础上,将所生成的中间代码翻译成某…...
MySQL 8.0中新增的功能(九)
FROM_UNIXTIME()、UNIX_TIMESTAMP()和CONVERT_TZ()的64位支持 根据MySQL 8.0.28版本的更新,FROM_UNIXTIME()、UNIX_TIMESTAMP() 和 CONVERT_TZ() 函数现在在支持64位的平台上处理64位值。这包括64位版本的Linux、MacOS和Windows。在兼容的平台上,UNIX_T…...
QT基础篇(8)QT5模型视图结构
1.概述 QT5的模型视图结构主要包括模型(Model)、视图(View)和委托(Delegate)三个部分。 模型(Model):模型是数据的抽象表示,负责存储和管理数据。它可以是自…...
vue3-响应式基础之reactive
reactive() 还有另一种声明响应式状态的方式,即使用 reactive() API。与将内部值包装在特殊对象中的 ref 不同,reactive() 将使对象本身具有响应性: 「点击按钮1」 <script lang"ts" setup> import { reactive } from vuec…...
【ceph】如何将osd的内容挂载出来---ceph-objectstore-tool 实现
本站以分享各种运维经验和运维所需要的技能为主 《python零基础入门》:python零基础入门学习 《python运维脚本》: python运维脚本实践 《shell》:shell学习 《terraform》持续更新中:terraform_Aws学习零基础入门到最佳实战 《k8…...
怎样实现安全便捷的网间数据安全交换?
数据安全交换是指在数据传输过程中采取一系列措施来保护数据的完整性、机密性和可用性。网间数据安全交换,则是需要进行跨网络、跨网段甚至跨组织地进行数据交互,对于数据的传输要求会更高。 大部分企业都是通过网闸、DMZ区、VLAN、双网云桌面等方式实现…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
