【数据结构】初识二叉搜索树(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…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)
UniApp 集成腾讯云 IM 富媒体消息全攻略(地理位置/文件) 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型,核心实现方式: 标准消息类型:直接使用 SDK 内置类型(文件、图片等)自…...
Python竞赛环境搭建全攻略
Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型(算法、数据分析、机器学习等)不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...
Mac flutter环境搭建
一、下载flutter sdk 制作 Android 应用 | Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 1、查看mac电脑处理器选择sdk 2、解压 unzip ~/Downloads/flutter_macos_arm64_3.32.2-stable.zip \ -d ~/development/ 3、添加环境变量 命令行打开配置环境变量文件 ope…...
小智AI+MCP
什么是小智AI和MCP 如果还不清楚的先看往期文章 手搓小智AI聊天机器人 MCP 深度解析:AI 的USB接口 如何使用小智MCP 1.刷支持mcp的小智固件 2.下载官方MCP的示例代码 Github:https://github.com/78/mcp-calculator 安这个步骤执行 其中MCP_ENDPOI…...
