【数据结构】初识二叉搜索树(Binary Search Tree)
文章目录
- 1. 二叉搜索树的概念
- 2. 二叉搜索树的操作
- 1.1 二叉搜索树的查找
- 1.2 二叉搜索树的插入
- 1.3 二叉搜索树的删除
1. 二叉搜索树的概念
二叉搜索树又称二叉排序树,它可能是一棵空树,也可能是具有以下性质的二叉树:
- 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值。
- 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值。
- 它的左右子树也分别为二叉搜索树。

2. 二叉搜索树的操作

int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
1.1 二叉搜索树的查找
- 从根开始比较、查找,比根大则往右边走查找,比根小则往左边走查找。
- 最多查找高度次,若走到空还没找到,则这个值不存在。
1.2 二叉搜索树的插入
- 树为空,则直接新增节点,赋值给 root 指针。
- 树不空,按二叉搜索树性质查找插入位置,插入新节点。

1.3 二叉搜索树的删除
首先查找元素是否在二叉搜索树中,如果不存在,就返回;否则要删除的节点可能分下面四种情况:
- 要删除的节点无孩子节点;
- 要删除的节点只有左孩子节点;
- 要删除的节点只有右孩子节点;
- 要删除的节点有左、右孩子节点。
看起来待删除节点有 4 种情况,实际情况 a 可以与情况 b 或者情况 c 合并起来,因此真正的删除过程如下:
- 情况 b :删除该节点且使被删除节点的双亲节点指向被删除节点的左孩子节点 - 直接删除;
- 情况 c :删除该节点且使被删除节点的双亲节点指向被删除节点的右孩子节点 - 直接删除;
- 情况 d :在它的右子树中寻找中序下的第一个节点(关键码最小),用它的值填补到被删除节点中,再来处理该节点的删除问题 - 替换法删除。

相关文章:
【数据结构】初识二叉搜索树(Binary Search Tree)
文章目录 1. 二叉搜索树的概念2. 二叉搜索树的操作1.1 二叉搜索树的查找1.2 二叉搜索树的插入1.3 二叉搜索树的删除 1. 二叉搜索树的概念 二叉搜索树又称二叉排序树,它可能是一棵空树,也可能是具有以下性质的二叉树: 若它的左子树不为空&am…...
数据库系统概念(第一周)
⚽前言 🏐四个基本概念 一、数据 定义 种类 特点 二、数据库 三、数据库管理系统(DBMS) 四、 数据库系统(DBS) 🏀数据库系统和文件系统对比 文件系统的弊端 🥎数据视图 数据抽象 …...
如何确定限流阈值:面试官问我,我怎么答?
在面试过程中,系统高并发是经常需要考察的,而熔断限流又是必考的,当面试官问及如何确定限流的阈值时,他们实际上是在考察你是否理解限流的本质及其在实际工作中是否有过经验。限流是一种常用的系统保护措施,用于防止过…...
HW干货集合 | HW面试题记录(1)
整理最近护网面试问的问题 前言 一开始会问问你在工作中负责的是什么工作(如果在职),参与过哪些项目。还有些会问问你之前有没有护网的经历,如果没有的话一般都会被定到初级(技术特牛的另说)。下面就是一…...
数据集踩的坑及解决方案汇总
数据集踩的坑及解决方案汇总 数据集各种格式构建并训练自己的数据集汇总Yolo系列SSDMask R-CNN报错 NotADirectoryError: [Errno 20] Not a directory: /Users/mia/Desktop/P-Clean/mask-RCNN/PennFudanPed2/labelme_json/.DS_StoreFaster R-CNN数据的格式转换划分数据集设定内…...
机器学习流程—数据预处理 Encoding
机器学习流程—数据预处理 Encoding 在机器学习中,我们经常会遇到分类变量,这些分量变量往往机器学习模型没有办法从中学习,往往有两种,一种是字符型,一种是数值型。通常需要对分类型变量做一些处理,常用的方法有两种:label encoding和one hot encoding。 例如,假设数…...
04-微服务 面试题
目录 1.Spring Cloud 常见的组件有哪些? 2.服务注册和发现是什么意思?(Spring Cloud 如何实现服务注册发现) 3.你们项目负载均衡如何实现的 ? 4.什么是服务雪崩,怎么解决这个问题? 5.你们服务是怎么监控的? 6.微服务限流(漏桶算法、令牌桶算法) 7.解释一下CAP…...
Qt连接所有同类部件到同一个槽函数
void MainWindow::AutoConnectSignals() {// 查找所有 QSpinBoxconst auto spinBoxes findChildren<QSpinBox*>();for (auto *spinBox : spinBoxes){connect(spinBox, static_cast<void(QSpinBox::*)(int)>(&QSpinBox::valueChanged), this, &ParameterW…...
spring boot 使用 webservice
spring boot 使用 webservice 使用 java 自带的 jax-ws 依赖 如果是jdk1.8,不需要引入任何依赖,如果大于1.8 <dependency><groupId>javax.jws</groupId><artifactId>javax.jws-api</artifactId><version>1.1</version&g…...
【嵌入式】嵌入式系统稳定性建设:最后的防线
🧑 作者简介:阿里巴巴嵌入式技术专家,深耕嵌入式人工智能领域,具备多年的嵌入式硬件产品研发管理经验。 📒 博客介绍:分享嵌入式开发领域的相关知识、经验、思考和感悟。提供嵌入式方向的学习指导、简历面…...
【算法】一类支持向量机OC-SVM
【算法】一类支持向量机OC-SVM 前言一类支持向量机OC-SVM 概念介绍示例编写数据集创建实现一类支持向量机OC-SVM完整的示例输出 前言 由于之前毕设期间主要的工具就是支持向量机,从基础的回归和分类到后来的优化,在接触到支持向量机还有一类支持向量机的…...
深入学习默认成员函数——c++指南
前言:类和对象是面向对象语言的重要概念。 c身为一门既面向过程,又面向对象的语言。 想要学习c, 首先同样要先了解类和对象。 本节就类和对象的几种构造函数相关内容进行深入的解析。 目录 类和对象的基本概念 封装 类域和类体 访问限定符…...
psutil, 一个超级有用的Python库
Python的psutil是一个跨平台的库,可以用于获取系统运行时的各种信息,包括CPU使用率、内存使用情况、磁盘和网络信息等。它主要用来做系统监控,性能分析,进程管理。它实现了同等命令行工具提供的功能,如ps、top、lsof、…...
[Python]`threading.local`创建线程本地数据
在Python中,threading.local是一个用于创建线程本地数据的工具。它允许每个线程拥有自己独立的变量副本,这样可以在多线程程序中避免共享变量带来的问题。 通过使用threading.local,你可以为每个线程创建一个独立的变量空间,这样…...
删除数据表
oracle从入门到总裁:https://blog.csdn.net/weixin_67859959/article/details/135209645 删除数据表属于数据库对象的操作 drop table 表名称; 删除 emp30 表 SQL> drop table emp30;表已删除。 上面这个语句运行后,就会把数据表 emp30 删除 在…...
前端自带的base64转化方法
前端html的base64使用方法window.btoa()和window.atob()_html用window.btoa();-CSDN博客...
图论(二)之最短路问题
最短路 Dijkstra求最短路 文章目录 最短路Dijkstra求最短路栗题思想题目代码代码如下bellman-ford算法分析只能用bellman-ford来解决的题型题目完整代码 spfa求最短路spfa 算法思路明确一下松弛的概念。spfa算法文字说明:spfa 图解: 题目完整代码总结ti…...
.NET Core 日志记录功能详解
在软件开发和运维过程中,日志记录是一个非常重要的功能。它可以帮助开发者跟踪应用程序的运行状况、诊断和监控问题。.NET Core 提供了一个灵活且易于使用的日志系统,本文将详细介绍.NET Core日志的相关概念、配置和使用方法。 1. 什么是日志记录以及它…...
docker——启动各种服务
1.Mysql 2.Redis 3.nginx 4.ES 注意:ES7之后环境为 -e ELASTICSEARCH_HOSTS http://ip地址:9200...
git远程仓库使用
赋值这个地址clone 克隆之后 cd slam_oncloud/ git remote add chenxnew ssh://git192.168.3.40:1022/chenxiao/slam_oncloud.git 查看一下 linuxchenxiao:/media/linux/mydisk/cloud_slam/slam_oncloud$ git remote add chenxnew ssh://git192.168.3.40:1022/chenxiao/sla…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
五子棋测试用例
一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏,有着深厚的文化底蕴。通过将五子棋制作成网页游戏,可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家,都可以通过网页五子棋感受到东方棋类…...
如何在Windows本机安装Python并确保与Python.NET兼容
✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...
