二叉检索树(定义、意义、存储数据元素形式),二叉检索树插入方法的图解和实现

1、二叉检索树:

(1)定义

二叉检索树的任意一个结点,设其值为k,则该节点左子树中任意一个结点的值都小于k;该节点右子树中任意一个节点的值都大于或等于k
这里的比较规则可以是针对数字的,也可以是针对字符串的,总之只要该数据项具有可比较的规则,就可以用二叉检索树这样的结构存储
在这里插入图片描述
当二叉检索树结点中存放的数据元素是数字时对二叉检索树进行中序遍历得到一个递增的有序序列
在这里插入图片描述

(2)二叉检索树存在的意义:

数据结构存在的目的是为了用户对数据集合的各种操作(CRUD:增删改查)更便捷快速

对比之前学过的顺序表和链表,二叉树相当于在两者中取了平衡
在这里插入图片描述
增加删除操作背后原理相同,改在查的基础上完成,因此上面的表格可简化成:
在这里插入图片描述

(3)二叉树结点中的内容不一定是数字

前面提到只要数据集合中的数据元素中含有可以比较的数据项,那么就可以采用二叉检索树这样的数据结构
在这里插入图片描述
整个二叉检索树存放数据集合,数据元素存放在二叉树结点中,数据项作为对数据元素进行 增删改查 的key

2、英文字符串的比较规则

(1)示例

在这里插入图片描述

(2)比较规则

在英文字符串的比较中,比较步骤通常遵循字典顺序,即ASCII码的顺序。首先,比较字符串的第一个字符,如果它们不同,那么比较就基于这两个字符的ASCII值;如果相同,则继续比较下一个字符,直到找到不同的字符或者比较完所有字符。

对于’overlap’>'conflagration’这个比较:

比较第一个字符:‘o’(overlap的第一个字符)和’c’(conflagration的第一个字符)。在ASCII码表中,'o’的ASCII值大于’c’的ASCII值。

结果确定:由于第一个字符的比较就已经确定了结果,所以不需要继续比较后面的字符。

基于上述比较步骤,‘overlap’的第一个字符’o’在字典顺序上大于’conflagration’的第一个字符’c’,因此整个字符串’overlap’在字典顺序上也大于’conflagration’。

所以,‘overlap’>'conflagration’的结果是True。

3、假设要存放的数据元素是英文单词及含义。实现一个BST类,它有增删改查等方法

(1)为了操作方便,定义命令符号、命令格式如下

在这里插入图片描述

(2)对命令进行提取key,value

示例

注意,输入的英文含义中如果含有逗号一定是中文逗号
在这里插入图片描述

(3)封装一个Elem()接口

要插入的每一个数据元素都是一个Elem()对象
在这里插入图片描述

(4)插入函数

图解

在这里插入图片描述

代码

在这里插入图片描述

测试样例

在这里插入图片描述

测试结果(中序遍历)

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

js实现抽奖效果

<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>随机抽奖</title> </head> <body>…

synchronized锁升级原理

锁升级过程 jdk1.6之后的优化 synchronized锁有四种状态&#xff0c;无锁&#xff0c;偏向锁&#xff0c;轻量级锁&#xff0c;重量级锁&#xff0c;这几个状态会随着竞争状态逐渐升级&#xff0c;锁可以升级但不能降级&#xff0c;但是偏向锁状态可以被重置为无锁状态。 1、偏…

C++ 类和对象(终篇)

初始化列表 就是给我们每一个成员变量找了一个定义的位置&#xff0c;不然像const这样的成员不好处理 所有的成员能在初始化列表初始化的都在里面初始化 拷贝构造函数和构造函数都允许初始化 构造函数体中的语句只能将其称作为赋初值&#xff0c;而不能称作初始化。 因为初始…

牛客NC314 体育课测验(一)【中等 图,BFS,拓扑排序 Java,Go、PHP】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/1a16c1b2d2674e1fb62ce8439e867f33 核心 图&#xff0c;BFS,拓扑排序&#xff0c;队列参考答案Java import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定&#xff0c;请勿修…

Scala 03 —— Scala Puzzle 拓展

Scala 03 —— Scala Puzzle 拓展 文章目录 Scala 03 —— Scala Puzzle 拓展一、占位符二、模式匹配的变量和常量模式三、继承 成员声明的位置结果初始化顺序分析BMember 类BConstructor 类 四、缺省初始值与重载五、Scala的集合操作和集合类型保持一致性第一部分代码解释第二…

浅浅了解一下 LibTorch

&#x1f349; CSDN 叶庭云&#xff1a;https://yetingyun.blog.csdn.net/ LibTorch 是 PyTorch 提供的一个二进制发行版&#xff0c;包含了所有必要的头文件、库和 CMake 配置文件&#xff0c;便于开发者依赖 PyTorch 开发应用。用户可以从 PyTorch 官网下载包含最新 LibTorch…

【科研】YOLOv8中anchor_points可视化(更新中)

目录 写在前面anchor-point可视化 写在前面 感叹一下&#xff1a;如果GPT能在我刚上大学的时候出来&#xff0c;也许我能学的比现在好太多&#xff0c;毕竟大学有一个比自己优秀太多的人引导着是多么地捷径。 anchor-point可视化

使用免费SSL证书安全吗,怎么获取

许多人可能会有疑问&#xff0c;使用免费的SSL证书真的安全吗&#xff1f;我们又该如何获取它们呢&#xff1f; 让我们简单了解一下什么是SSL证书&#xff1f;SSL证书是一种用于保障网络数据传输安全的小型数据文件。它通过在用户的浏览器与服务器之间建立一个加密的连接&…

常用UI组件

一、文本组件 1.1 概述 Text为文本组件&#xff0c;用于显示文字内容 1.2 参数 Text组件的参数类型为string | Resource Entry Component struct Index {build() {Column({space : 50}) {Text(你好).fontSize(50)}.width(100%).height(100%).justifyContent(FlexAlign.Cent…

使用Docker搭建一主二从的redis集群

文章目录 一、根据基础镜像构建三个docker容器二、构建master机三、配置slave机四、测试 本文使用 主机指代 物理机、 master机指代“一主二从”中的 一主&#xff0c; slave机指代“一主二从”中的 二从 一、根据基础镜像构建三个docker容器 根据本文第一章&#xff08…

Group Query Attention (GQA) 机制详解以及手动实现计算

Group Query Attention (GQA) 机制详解 1. GQA的定义 Grouped-Query Attention (GQA) 是对 Multi-Head Attention (MHA) 和 Multi-Query Attention (MQA) 的扩展。通过提供计算效率和模型表达能力之间的灵活权衡&#xff0c;实现了查询头的分组。GQA将查询头分成了G个组&#…

PE文件注入恶意代码改变代码执行顺序教程

原理&#xff1a;因为PE文件3个段都需要对齐200h&#xff0c;这样就会导致会有很多填充0&#xff0c;在填充0的地方就有机会进行插入恶意代码 在原有的PE文件的基础上修改&#xff0c;文件是我之前发布的一篇博客PE文件构造 主要思路&#xff1a;原来的PE文件中.text的有Mess…

2024面试软件测试,常见的面试题(上)

一、综合素质 1、自我介绍 面试官您好&#xff0c;我叫XXX&#xff0c;一直从事车载软件测试&#xff0c;负责最多的是中控方面。 以下是我的一些优势&#xff1a; 车载的测试流程我是熟练掌握的&#xff0c;且能够独立编写测试用例。 平时BUG提交会使用到Jira&#xff0c;类似…

CSS中的盒子模型

目录 盒子模型介绍 盒子模型组成 盒子边框 边框的基本使用 边框影响盒子大小 盒子内边距 内边距的基本使用 内边距影响盒子大小 内边距不影响盒子大小的情况 盒子外边距 外边距的基本使用 外边距的常见使用 外边距合并问题 相邻块元素垂直外边距的合并 嵌套块元…

Qt - 窗口

目录 1. 前言 2. 菜单栏(QMenuBar) 2.1. 创建菜单栏 2.1.1. 方式一 2.1.2. 方式二 2.2. 在菜单栏中添加菜单和创建菜单项 2.3. 在菜单项之间添加分割线 2.4. 综合示例 3. 工具栏(QToolBar) 3.1. 创建工具栏 3.2. 设置停靠位置 3.2.1. 方式一 3.2.2. 方式二 3.3. 设…

【前端】input输入框输入文字加文字轮廓效果

【前端】input输入框输入文字加文字轮廓效果 两种方案 方案一 输入框文字轮廓DEMO1通过文字阴影实现 <!DOCTYPE html> <html lang"en"> <head><title>输入框文字轮廓DEMO1通过文字阴影实现</title> <meta charset"UTF-8&quo…

【Linux进阶之路】高级IO

一、 铺垫 I&#xff0c;即input为输入&#xff1b;O&#xff0c;即output为输出&#xff0c;IO&#xff0c;即input output为输入输出。IO一般是基于网卡&#xff0c;磁盘&#xff0c;光盘&#xff0c;U盘&#xff0c;磁盘&#xff0c;磁带等毫秒级别的外存&#xff0c;相较…

《QT实用小工具·三十一》基于QT开发的访客管理平台demo2

1、概述 源码放在文章末尾 该项目为访客管理平台demo&#xff0c;包含主界面、系统设置、警情查询、调试帮助、用户退出功能。 项目部分代码如下&#xff1a; #pragma execution_character_set("utf-8")#include "frmmain.h" #include "ui_frmmain…

SpringBoot + Redis实现用户信息登录的缓存

&#x1f34e;前言 &#x1f350;项目的背景 背景&#xff1a;&#x1f349;当我们在完成用户信息登录时&#xff0c;我们往往每次都会在数据库中查询用户的记录&#xff0c;生成token并返回给前端&#xff0c;不过这样会有一定的问题。 &#x1f350;造成的问题 问题&#xf…

Linux 用户和组

理解Linux 用户和组的概念 掌握passwd 文件的组成以及作用 掌握shadow 文件的组成以及作用 了解group 文件的内容 1.用户分类&#xff1a; 超级管理员&#xff08;root&#xff09; 普通用户 程序用户 1.用户信息文件 /etc/passwd 文件中存储了所有用户信息。 1.passwd 格…