当前位置: 首页 > news >正文

二叉排序树的查找、插入、删除

目录

二叉排序树的定义

二叉排序树的查找

二叉排序树的插入


二叉排序树的定义

二叉排序树的定义
二叉排序树(Binary Sort Tree, BST),也称二叉查找树。
二叉排序树或者是一棵空树,或者是一棵具有下列特性的非空二叉树:
1) 若左子树非空,则左子树上所有结点关键字均小于根结点的关键字值;
2) 若右子树非空,则右子树上所有结点关键字均大于根结点的关键字值;
3) 左、右子树本身也分别是一棵二叉排序树。

由定义可知,二叉排序树是一个递归的数据结构,可以方便的使用递归算法对二叉排序树进行各种运算。
根据二叉树的定义,可得左子树结点值 < 根结点值 < 右子树结点值。
所以,对二叉排序树进行中序遍历,可以得到一个递增的有序序列。

二叉排序结点结构:

typedef struct BiTNode
{int data;struct BiTNode *left, *right;
}BiTNode,*Bitree;

二叉排序树的查找

二叉排序树的查找是从根结点开始的,沿某个分支逐层向下进行比较的过程。
 其查找过程描述如下:若二叉排序树非空,则将给定值与根结点的关键字比较,若相等,则查找成功;若不等,则当根结点的关键字值大于给定关键字值时,在根结点的左子树中查找;否则在根结点的右子树中查找。

递归查找:

Bitree SearchBST(Bitree root, int key){if(root->data == key){return root;}else if(key< root->data){return SearchBST(root->left, key);}else{return SearchBST(root->right, key);}
}

非递归查找

//查找的非递归算法
Bitree SearchBST(Bitree root, int key){Bitree p = root;while(p!=NULL && p->data!=key){if(key< p->data)p = p->left;elsep = p->right;}return p;
}

二叉排序树的插入

//插入的递归算法
Bitree Insert(Bitree root, int x) {if (root == NULL) {root = (Bitree)malloc(sizeof(BiTNode));root->data;root->left = NULL;root->right = NULL;return root;}if (x < root->data) {root->left = Insert(root->left, x);}if (x > root->data) {root->right = Insert(root->right, x);}return root;
}
//插入的非递归算法
void Inser_Node(Bitree &T, int key)
{Bitree parent = NULL;Bitree p = T;Bitree s = (Bitree)malloc(sizeof(BiTNode));s->data = key;s->left = NULL;s->right = NULL;if (T== NULL){T = s;return;}while (p != NULL){parent = p;if (p->data > key)//在左孩子继续查找{p = p->left;}if (p->data < key){p = p->right;}}if (parent->data > key){parent->left = s;}else {parent->right = s;}}

根据书上代码,将查找和插入整合:

/****************书上代码***************************/
int SearchBST(Bitree T,int key, Bitree f, Bitree& p)
{if (!T){p = f;return 0;}else if(T->data==key){p = T;printf("有重复");return 1;}else if (T->data > key){return SearchBST(T->left, key, T, p);}else{return SearchBST(T->right, key, T, p);}
}
void InserBST(Bitree& T, int key)
{Bitree p;if (SearchBST(T, key, NULL, p)==0)//查找失败,进行插入{Bitree s =(Bitree) malloc(sizeof(BiTNode));s->data = key;s->left = NULL;s->right = NULL;if (!p){T = s;}else if (key < p->data){p->left = s;//被插入点作为*s左孩子}else {p->right = s;}}
}

相关文章:

二叉排序树的查找、插入、删除

目录 二叉排序树的定义 二叉排序树的查找 二叉排序树的插入 二叉排序树的定义 二叉排序树的定义 二叉排序树&#xff08;Binary Sort Tree&#xff0c; BST&#xff09;&#xff0c;也称二叉查找树。 二叉排序树或者是一棵空树&#xff0c;或者是一棵具有下列特性的非空二叉…...

《Opencv3编程入门》学习笔记—第三章

《Opencv3编程入门》学习笔记 记录一下在学习《Opencv3编程入门》这本书时遇到的问题或重要的知识点。 第三章 HighGUI图形用户界面初步 一、图像的载入、显示和输出到文件 &#xff08;一&#xff09;OpenCV的命名空间 简单的OpenCV程序标配&#xff1a; #include <o…...

如何从Ubuntu Linux中删除Firefox Snap?

Ubuntu Linux是一款广受欢迎的开源操作系统&#xff0c;拥有强大的功能和广泛的应用程序选择。默认情况下&#xff0c;Ubuntu提供了一种称为Snap的软件打包格式&#xff0c;用于安装和管理应用程序。Firefox是一款流行的开源网络浏览器&#xff0c;而Firefox Snap是Firefox的Sn…...

数学建模的初阶-快速上手

目录 第一步&#xff1a;明确问题 第二步&#xff1a;选择建模方法 第三步&#xff1a;收集数据 第四步&#xff1a;构建数学模型 第五步&#xff1a;模型验证与评估 数学建模软件推荐 统计模型 (1) 线性回归模型 (2) 逻辑回归模型 (3) 时间序列模型 优化模型 (1) …...

复习向 C/C++ 编程语言简介和概括(C++复习向p1)

文章目录 C 编程语言C 和 C 关系标准的 C 组成ANSI 标准比较重要的标准化时间 C 编程语言 是一种静态类型的、编译式的、通用式的、大小写敏感、不规则的编程语言支持过程化编程&#xff0c;面向对象&#xff0c;泛型编程 C 和 C 关系 C 是 C 的一个超集&#xff0c;任何合法…...

DRF之过滤,排序,分页

一、权限组件源码解读 1.继承了APIView 才有的---》执行流程---》dispatch中----》三大认证 APIView的dispatch def initial(self, request, *args, **kwargs):self.perform_authentication(request)self.check_permissions(request)self.check_throttles(request) 2 读…...

我的Redis学习,共写了14篇博客文章

早在19和20年全面学习SpringBoot相关技术知识时也曾经有学习到Redis&#xff0c;主要是看了几家的视频教程&#xff0c;但是未曾有具体的实践&#xff0c;后来再学习到Docker和Spring Session框架的Redis存储时&#xff0c;又稍微的实践了一丢丢&#xff0c;所有的实践也就仅此…...

mPython软件使用指南

①软件界面 一、软件界面的介绍 1.模式切换 硬件编程 Python3.6 Jupyter python3.6模式细节补充&#xff08;一般不使用该模式&#xff0c;此处可跳过&#xff09; Python3.6模式的界面 左侧指令分类栏 Python3.6模式的图形化指令分类分为&#xff1a; Python语法基础相关指令&…...

龙芯2K1000实战开发-系统配置详解

目录 概要 整体架构流程 技术名词解释 技术细节 ​编辑 总结...

【一起撸个DL框架】5 实现:自适应线性单元

CSDN个人主页&#xff1a;清风莫追欢迎关注本专栏&#xff1a;《一起撸个DL框架》GitHub获取源码&#xff1a;https://github.com/flying-forever/OurDLblibli视频合集&#xff1a;https://space.bilibili.com/3493285974772098/channel/series 文章目录 5 实现&#xff1a;自适…...

开箱即用的工具函数库xijs更新指南(v1.2.6)

xijs 是一款开箱即用的 js 业务工具库, 聚集于解决业务中遇到的常用函数逻辑问题, 帮助开发者更高效的开展业务开发. 接下来就和大家一起分享一下 v1.2.6 版本的更新内容以及后续的更新方向. 贡献者列表: 1. 计算变量内存calculateMemory 该模块主要由 zhengsixsix 贡献, 我们可…...

【Netty】ChannelPipeline源码分析(五)

文章目录 前言一、ChannelPipeline 接口1.1 创建 ChannelPipeline1.2 ChannelPipeline 事件传输机制1.2.1 处理出站事件1.2.2 处理入站事件 二、ChannelPipeline 中的 ChannelHandler三、ChannelHandlerContext 接口3.1 ChannelHandlerContext 与其他组件的关系3.2 跳过某些 Ch…...

并行计算技术解密:MPI和OpenMP的学习和应用指南

欢迎来到并行计算技术的奇妙世界&#xff01;本指南将带您深入了解MPI&#xff08;Message Passing Interface&#xff09;和OpenMP&#xff08;Open Multi-Processing&#xff09;两种重要的并行计算技术&#xff0c;并为您提供学习和应用的指南。无论您是一个科研工作者、开发…...

什么是自动化测试框架?我们该如何搭建自动化测试框架?

无论是在自动化测试实践&#xff0c;还是日常交流中&#xff0c;经常听到一个词&#xff1a;框架。之前学习自动化测试的过程中&#xff0c;一直对“框架”这个词知其然不知其所以然。 最近看了很多自动化相关的资料&#xff0c;加上自己的一些实践&#xff0c;算是对“框架”…...

Debezium报错处理系列之六十七:TopicAuthorizationException: Not authorized to access topics

Debezium报错处理系列之六十七:TopicAuthorizationException: Not authorized to access topics 一、完整报错二、错误原因三、解决方法Debezium报错处理系列一:The db history topic is missing. Debezium报错处理系列二:Make sure that the same history topic isn‘t sha…...

javaWebssh中小学课件资源系统myeclipse开发mysql数据库MVC模式java编程计算机网页设计

一、源码特点 java ssh中小学课件资源系统是一套完善的web设计系统&#xff08;系统采用ssh框架进行设计开发&#xff09;&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用 B/S模式开发。开发环境为TOMCAT…...

MySQL高级查询操作

文章目录 前言聚集函数分组查询&#xff1a;GROUP BY过滤&#xff1a;HAVING嵌套子查询比较运算中使用子查询带有IN的子查询SOME(子查询)ALL(子查询)EXISTS子查询 前言 查询语句书写顺序&#xff1a; 1、select 2、from 3、where 4、group by 5、having 6、order by 7、limit …...

Day53【动态规划】1143.最长公共子序列、1035.不相交的线、53.最大子序和

1143.最长公共子序列 力扣题目链接/文章讲解 视频讲解 本题最大的难点还是定义 dp 数组 本题和718.最长重复子数组区别在于这里不要求是连续的了&#xff0c;但要有相对顺序 直接动态规划五部曲&#xff01; 1、确定 dp 数组下标及值含义 dp[i][j]&#xff1a;取 text1…...

Three.js--》实现3d地球模型展示

目录 项目搭建 实现网页简单布局 初始化three.js基础代码 创建环境背景 加载地球模型 实现光柱效果 添加月球模型 今天简单实现一个three.js的小Demo&#xff0c;加强自己对three知识的掌握与学习&#xff0c;只有在项目中才能灵活将所学知识运用起来&#xff0c;话不多…...

<SQL>《SQL命令(含例句)精心整理版(6)》

《SQL命令&#xff08;含例句&#xff09;精心整理版&#xff08;6&#xff09;》 18 DB2查询语句18.1 查询数据库大小18.2 查看表占表空间大小18.3 查看正在执行的语句18.4 db2expln 查看执行计划18.5 db2advis 查看优化建议 19 空值19.1 NULL19.2 TRIM 18 DB2查询语句 18.1 …...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...