数据结构-二叉搜索树
二叉搜索树:BST(Binary Search Tree)
二叉搜索树是二叉树,可以为空,如果不为空,满足以下性质:
- 非空左子树的所有键值小于其根节点的键值
- 非空右子树的所有键值大于其根节点的键值
- 左、右字数本身也都是二叉搜索树
二叉搜索树的特点:
- 二叉搜索树的特点就是相对较小的值总是保存在左节点上,相对较大的值总是保存在右节点上
- 查找效率非常高
二叉搜索树常见的操作:
- insert(key, value):向树中插入数据
- search(key):在树中查找
- remove(key):从树中移除
- update(key,value):修改节点数据
- inOrderTraverse:通过中序遍历方式遍历所有节点
- preOrderTraverse:通过先序遍历方式遍历所有节点
- postOrderTraverse:通过后序遍历方式遍历所有节点
- min:返回树中最小的键/值
- max:返回树中最大的键/值
class Node {constructor(key) {this._key = key;this._left = null;this._right = null;}
}
class BinarySearchTree {constructor() {this._root = null;}insert(key) {const insertNode = (node, newNode) => {if(newNode._key <= node._key) {if(node._left === null) {node._left = newNode;} else {insertNode(node._left, newNode);}} else {if(node._right === null) {node._right = newNode;} else {insertNode(node._right, newNode);}}}const newNode = new Node(key)if (this._root === null) {this._root = newNode} else {insertNode(this._root, newNode) }}preOrderTraverse(handler = (value) => {console.log(value)}) {const preOrderTraverseNode = (node) => {if (node === null) {return }handler(node._key)preOrderTraverseNode(node._left)preOrderTraverseNode(node._right)}preOrderTraverseNode(this._root)}midOrderTraverse(handler = (value) => {console.log(value)}) {const midOrderTraverseNode = (node) => {if (node === null) {return }midOrderTraverseNode(node._left)handler(node._key)midOrderTraverseNode(node._right)}midOrderTraverseNode(this._root)}postOrderTraverse(handler = (value) => {console.log(value)}) {const postOrderTraverseNode = (node) => {if (node === null) {return }postOrderTraverseNode(node._left)postOrderTraverseNode(node._right)handler(node._key)}postOrderTraverseNode(this._root)}min() {if (this._root === null) {return null}let node = this._rootwhile(true) {if (node._left === null) {return node._key}node = node._left}}max() {if (this._root === null) {return null}let node = this._rootwhile(true) {if (node._right === null) {return node._key}node = node._right}}search(key) {const searchNode = (node, key) => {if (node === null) {return false}if (node._key === key) {return true}if (key < node._key) {return searchNode(node._left, key)} else {return searchNode(node._right, key)}}return searchNode(this._root, key)}remove(key) {if (this._root === null) {return false}let current = this._rootlet parent = nulllet isLeftChild = truewhile (current._key !== key) {parent = currentif (key < current._key) {isLeftChild = truecurrent = current._left} else {isLeftChild = falsecurrent = current._right}if (current === null) {return false}}// 删除叶子节点if (current._left === null && current._right === null) {if (current === this._root) {this._root = null} else {if (isLeftChild) {parent._left = null} else {parent._right = null}}}// 删除有一个子节点else if (current._left === null ) {if (current === this._root) {this._root = current._right} else if (isLeftChild) {parent._left = current._right} else {parent._right = current._right}} else if (current._right === null) {if (current === this._root) {this._root = current._left} else if (isLeftChild) {parent._left = current._left} else {parent._right = current._left}} else {const getExChangeTargetNode = (current) => {let node = current._rightlet parentNode = currentlet isRightClick = truewhile(true) {if (node._left === null) {if (isRightClick) {parentNode._right = node._right} else {parentNode._left = node._right}return node}isRightClick = falseparentNode = nodenode = node._left}}const targetNode = getExChangeTargetNode(current);if (current !== this._root) {if (isLeftChild) {parent._left = targetNode} else {parent._right = targetNode}} else {this._root = targetNode}targetNode._right = current._righttargetNode._left = current._left}return true}}
相关文章:
数据结构-二叉搜索树
二叉搜索树:BST(Binary Search Tree) 二叉搜索树是二叉树,可以为空,如果不为空,满足以下性质: 非空左子树的所有键值小于其根节点的键值非空右子树的所有键值大于其根节点的键值左、右字数本身也都是二叉搜索树 二叉…...
JUnit:Java开发者不可或缺的单元测试框架
在软件开发过程中,测试是确保代码质量的关键环节。单元测试作为测试体系的基础,对提升代码质量、降低bug率、增强软件稳定性具有重要作用。JUnit 作为 Java 语言事实上的标准单元测试框架,已经成为 Java 开发者进行单元测试的首选工具。本文将…...
NG32单片机GPIO口配置方式
目录 一、引言 二、GPIO口基本结构 三、GPIO口配置方式 四、工作原理 五、总结 一、引言 NG32单片机是一款集成度高、功能强大的微控制器。其中,GPIO(General Purpose Input/Output)口作为单片机与外部设备通信的重要接口,具…...
SpringCloud-OpenFeign拓展-连接池、最佳使用方法、日志输出
目录 1 OpenFeign连接池 1.1 常见连接类型 1.2 连接池使用方法 1.2.1 引入依赖 1.2.2 开启连接池功能 1.2.3 配置完成,重启实例即可,底层将更改设置。 2 OpenFeign最佳使用方法 2.1 每个微服务都是单独的project,内部有三个独立模块 …...
跨链协议中Cosmos IBC、Polkadot/XCM、Celer Network的区别以及用途
跨链协议是实现不同区块链之间通信和价值转移的关键技术。Cosmos IBC、Polkadot/XCM 和 Celer Network 是三个在跨链领域内具有代表性的协议,它们各自有着独特的设计理念和应用场景。下面是这三个协议的详细对比: Cosmos IBC (Inter-Blockchain Communi…...
电子画册制作与传统画册相比,有哪些优势?
在当今数字化时代,电子画册作为一种新兴的媒体形式,其制作与传统画册相比具有显著的优势。以下是对这些优势的详细探讨。 首先,电子画册的制作过程通常更加便捷和经济。相较于传统画册需要经历的繁琐的印刷过程,电子画册的制作大多…...
postman如何导入证书
1、打开postman,点击Settings。 2、添加证书。 3、填写要访问平台的URL路径及端口、证书文件、证书密码。 4、添加完之后即可立即调用postman。...
RocketMQ教程(八):RocketMQ的集群搭建
传送门:RocketMQ教程汇总,让你从入门到精通 集群架构 RocketMQ 的各个组件都可以搭建成集群部署,Broker 还可以搭建成主从架构,下面介绍的主要是 Broker 集群。 数据复制策略 复制策略是Broker的Master与Slave间的数据同步方式。分为同步复制与异步复制: 同步复制 消…...
线上观看人次2万+!「飞天技术沙龙-CentOS 迁移替换专场」北京站圆满结束
5 月 29 日,阿里云联合龙蜥社区共同举办的「飞天技术沙龙-CentOS 迁移替换专场」于北京圆满结束,在线观看人次 2 万。本次活动现场汇聚了来自浪潮信息、Intel、龙芯、统信软件、红旗软件、电子五所等多家操作系统产业头部企业和机构,大家围绕…...
Docker基本架构概览-1
Docker基本架构概览 Docker架构 Docker采用客户端-服务器(C/S)架构,主要组件包括: Docker Client 用户与Docker交互的接口,发送命令到Docker守护进程。 Docker Daemon 运行在后台,接收并处理Docker客户端…...
OZON云仓靠谱吗,OZON云仓垫资提货模式
在电商飞速发展的今天,物流仓储成为了支撑整个电商生态的重要基石。OZON云仓作为市场上新兴的仓储物流服务提供商,凭借其先进的技术和灵活的服务模式,受到了不少电商卖家和消费者的关注。但随之而来的是一系列疑问:OZON云仓靠谱吗…...
数据集笔记:DGraph 大规模动态图数据集
dgraph-web (xinye.com) 1 数据集介绍 DGraph 是一个有向无权的动态图,包含超过 370 万个节点以及 430 万条动态边DGraph 中的节点表示金融借贷用户,有向边表示紧急联系人关系,每个节点包含脱敏后的属性特征,以及表示是否为金融…...
一些常用的git指令总结
1、git add 文件名 :该 命令可将该文件的修改添加到暂存区 比如:我刚刚修改了my_test.cpp文件,这时就可以使用git add my_test.cpp. 就将该修改添加到了暂存区。 2、git commit -m "......说明" 就是将当前的修改记录提交到本地…...
【HarmonyOS】遇见的问题汇总
一、当前编辑的页面,预览打不开 1、问题说明 当前编辑的页面,预览打不开,日志提示如下: Route information is not configured for the current page. To avoid possible redirection issues, configure route information for…...
C# NX二次开发-获取圆弧中心点和半径
使用UF函数可以获取圆弧边或圆弧线中心点和半径: 1.使用 UF_CURVE_ask_arc_data: theUf.Curve.AskArcData(edge.Tag, out UFCurve.Arc arc);theUf.Curve.CreateArc(ref arc, out Tag arc_tag);double[] matrix_values new double[9];double[] vec_product new double[3];theU…...
鸿蒙原生应用元服务开发-位置服务地理编码转化开发
(逆)地理编码转化开发 场景概述 使用坐标描述一个位置,非常准确,但是并不直观,面向用户表达并不友好。系统向开发者提供了以下两种转化能力。 地理编码转化:将地理描述转化为具体坐标。 逆地理编码转化能力…...
【ArcGISPro SDK】构建多面体要素
结果展示 每个面构建顺序 代码 using ArcGIS.Core.CIM; using ArcGIS.Core.Data; using ArcGIS.Core.Geometry; using ArcGIS.Desktop.Catalog; using ArcGIS.Desktop.Core; using ArcGIS.Desktop.Editing; using ArcGIS.Desktop.Extensions; using ArcGIS.Desktop.Framework;…...
leetcode够用之java语法
常用方法 Arrays.sort()排序 import java.util.Arrays;public class Main {public static void main(String[] args) {int[] numbers {9, 2, 5, 1, 7, 3};Arrays.sort(numbers);System.out.println(Arrays.toString(numbers)); // 输出: [1, 2, 3, 5, 7, 9]} }获取str中的第…...
pdf文件怎么改变大小?在线快速压缩pdf的方法
pdf作为一种常用的文件格式,使用这种文件类型的好处在于不仅拥有更好的兼容性,还可以设置密码来保证安全性,防止未授权用户查看内容,所以现在导出文件展示都会采用这种格式的来做内容展示。当遇到pdf文件过大问题时,想…...
inferCNV:scRNA-seq数据推断染色体拷贝数变化
inferCNV分析简介 inferCNV用于探索肿瘤单细胞RNA-Seq 数据,以确定体细胞大规模染色体拷贝数改变的证据,例如整个染色体或大片段染色体的增益或缺失。这是通过与一组参考“正常”细胞(这里的正常细胞可自行定义)进行比较…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...
什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
ubuntu22.04 安装docker 和docker-compose
首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...
在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南
在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南 背景介绍完整操作步骤1. 创建Docker容器环境2. 验证GUI显示功能3. 安装ROS Noetic4. 配置环境变量5. 创建ROS节点(小球运动模拟)6. 配置RVIZ默认视图7. 创建启动脚本8. 运行可视化系统效果展示与交互技术解析ROS节点通…...
GraphRAG优化新思路-开源的ROGRAG框架
目前的如微软开源的GraphRAG的工作流程都较为复杂,难以孤立地评估各个组件的贡献,传统的检索方法在处理复杂推理任务时可能不够有效,特别是在需要理解实体间关系或多跳知识的情况下。先说结论,看完后感觉这个框架性能上不会比Grap…...
