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

java二叉排序树

1.先看一个需求

给你一个数列 (7, 3, 10, 12, 5, 1, 9),要求能够高效的完成对数据的查询和添加

2.解决方案分析

使用数组
数组未排序, 优点:直接在数组尾添加,速度快。 缺点:查找速度慢. [示意图]
数组排序,优点:可以使用二分查找,查找速度快,缺点:为了保证数组有序,在添加新数据时,找到插入位
置后,后面的数据需整体移动,速度慢。[示意图]

使用链式存储-链表
不管链表是否有序,查找速度都慢,添加数据速度比数组快,不需要数据整体移动。[示意图]

使用二叉排序树

3.二叉排序树介绍

二叉排序树:BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当
前节点的值小,右子节点的值比当前节点的值大。

特别说明:如果有相同的值,可以将该节点放在左子节点或右子节点

比如针对前面的数据 (7, 3, 10, 12, 5, 1, 9) ,对应的二叉排序树为

在这里插入图片描述

4.二叉排序树创建和遍历

一个数组创建成对应的二叉排序树,并使用中序遍历二叉排序树,比如: 数组为 Array(7, 3, 10, 12, 5, 1, 9) , 创
建成对应的二叉排序树为 :

在这里插入图片描述

5.二叉排序树的删除

二叉排序树的删除情况比较复杂,有下面三种情况需要考虑

  1. 删除叶子节点 (比如:2, 5, 9, 12)
  2. 删除只有一颗子树的节点 (比如:1)
  3. 删除有两颗子树的节点. (比如:7, 3,10 )
  4. 操作的思路分析
    在这里插入图片描述

//对删除结点的各种情况的思路分析:
第一种情况:
删除叶子节点 (比如:2, 5, 9, 12)
思路
(1) 需求先去找到要删除的结点 targetNode
(2) 找到 targetNode 的 父结点 parent
(3) 确定 targetNode 是 parent 的左子结点 还是右子结点
(4) 根据前面的情况来对应删除
左子结点 parent.left = null
右子结点 parent.right = null;
第二种情况: 删除只有一颗子树的节点 比如 1
思路
(1) 需求先去找到要删除的结点 targetNode
(2) 找到 targetNode 的 父结点 parent
(3) 确定 targetNode 的子结点是左子结点还是右子结点
(4) targetNode 是 parent 的左子结点还是右子结点
(5) 如果 targetNode 有左子结点
5. 1 如果 targetNode 是 parent 的左子结点
parent.left = targetNode.left;
5.2 如果 targetNode 是 parent 的右子结点
parent.right = targetNode.left;
(6) 如果 targetNode 有右子结点
6.1 如果 targetNode 是 parent 的左子结点
parent.left = targetNode.right;
6.2 如果 targetNode 是 parent 的右子结点
parent.right = targetNode.right
情况三 : 删除有两颗子树的节点. (比如:7, 3,10 )
思路
(1) 需求先去找到要删除的结点 targetNode
(2) 找到 targetNode 的 父结点 parent
(3) 从 targetNode 的右子树找到最小的结点
(4) 用一个临时变量,将 最小结点的值保存 temp = 11
(5) 删除该最小结点
(6) targetNode.value = temp

6.二叉排序树删除结点的代码实现:

public class BinarySortTreeDemo {public static void main(String[] args) {// TODO Auto-generated method stubint arr[] = { 7, 3, 10, 12, 5, 1, 9, 2 };BinarySortTree binarySortTree = new BinarySortTree();// 循环的添加结点到二叉树for (int i = 0; i < arr.length; i++) {binarySortTree.add(new Node(arr[i]));}// 中序遍历二叉排序树System.out.println("中序遍历二叉排序树");binarySortTree.infixOrder();// 1,3,5,7,9,10,12// 测试一下删除叶子节点
//		binarySortTree.delNode(2);
//		binarySortTree.delNode(1);binarySortTree.delNode(7);System.out.println("删除结点后");binarySortTree.infixOrder();}}//创建二叉排序树
class BinarySortTree {private Node root;// 查找要删除的结点public Node search(int value) {if (root == null) {return null;} else {return root.search(value);}}// 查找父结点public Node searchParent(int value) {if (root == null) {return null;} else {return root.searchParent(value);}}// 编写方法// 1.返回以node为根节点的二叉排序树的最小节点的值// 2.删除以node为根节点的二叉排序树的最小节点的值/*** * @param node 传入的结点(当作二叉排序树的根节点)* @return 返回的以node为结点的二叉树的最小结点的值*/public int delRightTreeMin(Node node) {Node target = node;// 循环的查找左节点,就会找到最小值while (target.left != null) {target = target.left;}// 这时target就指向了最小节点// 删除最小节点delNode(target.value);return target.value;}// 删除结点public void delNode(int value) {if (root == null) {return;} else {// 1.需要先去找到要删除的结点 targetNodeNode targetNode = search(value);// 如果没有找到要删除的结点if (targetNode == null) {return;}// 如果我们发现targetNode没有父结点if (root.left == null && root.right == null) {root = null;return;}// 去查找targetNode的父结点Node parent = searchParent(value);// 如果要删除的节点是叶子节点if (targetNode.left == null && targetNode.right == null) {// 判断targetNode是父结点的左指结点还是右子节点if (parent.left != null && parent.left.value == value) {// 是左指结点parent.left = null;} else if (parent.right != null && parent.right.value == value) {// 是右子结点parent.right = null;}} else if (targetNode.left != null && targetNode.right != null) {// 删除有两颗子树的节点int minVal = delRightTreeMin(targetNode.right);targetNode.value = minVal;} else {// 删除只有一颗子树的结点// 如果要删除的结点有左指结点if (targetNode.left != null) {// 如果targetNode是parent的左指结点if (parent.left.value == value) {parent.left = targetNode.left;} else {// targetNode是parent的右子结点parent.right = targetNode.left;}} else {// 如果要删除的节点有右子结点// 如果targetNode是parent的左指结点if (parent.left.value == value) {parent.left = targetNode.right;} else {// 如果targetNode是parent的右指结点parent.right = targetNode.right;}}}}}// 添加结点方法public void add(Node node) {if (root == null) {root = node;// 如果root为空则直接让root指向node} else {root.add(node);}}// 中序遍历public void infixOrder() {if (root != null) {root.infixOrder();} else {System.out.println("二叉排序树为空,不能遍历");}}
}//创建Node结点
class Node {int value;Node left;Node right;public Node(int value) {super();this.value = value;}// 查找要删除的结点/*** * @param value 希望删除的结点的值* @return 如果找到返回该节点,否则返回null*/public Node search(int value) {if (value == this.value) {return this;} else if (value < this.value) {// 如果查找的值小于当前节点,向左子树递归查找// 如果左子结点为空if (this.left == null) {return null;}return this.left.search(value);} else {// 如果查找的值不小于当前节点,向右子树递归查找if (this.right == null) {return null;}return this.right.search(value);}}// 查找要删除该节点的父节点/*** * @param value 要找到的结点的值* @return 返回的是要删除的结点的父节点,如果没有就返回null*/public Node searchParent(int value) {// 如果当前结点就是要删除的结点的父结点,就返回if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {return this;} else {// 如果要查找的值小于当前节点的值,并且当前节点的左指结点不为空if (value < this.value && this.left != null) {return this.left.searchParent(value);// 向左子树递归查找} else if (value >= this.value && this.right != null) {return this.right.searchParent(value);// 向右子树递归查找} else {return null;// 没有找到父结点}}}@Overridepublic String toString() {return "Node [value=" + value + "]";}// 添加结点方法// 递归的方式添加结点,需要满足二叉排序树的要求public void add(Node node) {if (node == null) {return;}// 判断传入结点的值,和当前子树的根结点的值关系if (node.value < this.value) {// 如果当前节点左子节点为nullif (this.left == null) {this.left = node;} else {// 递归的向左子树添加this.left.add(node);}} else {// 添加的结点的值大于当前节点的值if (this.right == null) {this.right = node;} else {// 递归向右子树添加this.right.add(node);}}}// 中序遍历public void infixOrder() {if (this.left != null) {this.left.infixOrder();}System.out.println(this);if (this.right != null) {this.right.infixOrder();}}
}

相关文章:

java二叉排序树

1.先看一个需求 给你一个数列 (7, 3, 10, 12, 5, 1, 9)&#xff0c;要求能够高效的完成对数据的查询和添加 2.解决方案分析 使用数组 数组未排序&#xff0c; 优点&#xff1a;直接在数组尾添加&#xff0c;速度快。 缺点&#xff1a;查找速度慢. [示意图] 数组排序&#xf…...

聊一聊 gRPC 的四种通信模式

温馨提示&#xff1a;本文需要结合上一篇 gRPC 文章一起食用&#xff0c;否则可能看不懂。 前面一篇文章松哥和大家聊了 gRPC 的基本用法&#xff0c;今天我们再来稍微深入一点点&#xff0c;来看下 gRPC 中四种不同的通信模式。 gRPC 中四种不同的通信模式分别是&#xff1a;…...

科技云报道:开源真的香,风险知多少?

科技云报道原创。 过去几年&#xff0c;开源界一片火热&#xff0c;开源软件技术已全面进军操作系统、云原生、人工智能、大数据、半导体、物联网等行业领域。 数据显示&#xff0c;我国超九成企业在使用或正计划使用开源技术。 与此同时&#xff0c;全球各大开源组织相继兴…...

国产化适配迁移记录

国产化适配迁移记录 本项目基于RuoYi-Vue的框架进行迁移。目前已完成覆盖测试暂无其他问题。 国产化环境 名称版本达梦数据库DmJdbcDriver18 8.1.2.144通用mapper – tk.mybatismapper-spring-boot-starter 4.2.5<!-- 达梦数据库--><dependency><groupId>…...

又一国产开源项目走向世界,百度RPC框架Apache bRPC正式成为ASF顶级项目

2023 年 1 月 26 日&#xff0c;Apache 软件基金会 (ASF) 官方正式宣布Apache bRPC 正式毕业&#xff0c;成为 Apache的顶级项目。 我听到这个消息是挺开心的&#xff0c;毕竟是又一款由国人主导的apche顶级项目&#xff0c;再次证明国内在开源界正在发挥越来越重要的作用。 …...

多数据库学习之GBase8s查询数据库表元信息常用SQL

多数据库学习之GBase8s查询数据库表元信息常用SQL简介常用SQL创建用户创建数据库及模式获取表元数据其他参考链接简介 背景介绍 GBase 8t是基于IBM informix源代码、编译和测试体系自主研发的交易型数据库产品。 南大通用安全数据库管理系统&#xff08;简称 GBase 8s&#xff…...

Jetpack之Lifecycle应用与源码分析

Build lifecycle-aware components that can adjust behavior based on the current lifecycle state of an activity or fragment. 上面是源于官网的定义&#xff0c;简单翻译就是说Lifecycle的作用就是基于当前的Activity或者Fragment的生命周期当前状态构建可感知生命周期的…...

Python序列类型之集合

&#x1f490;&#x1f490;&#x1f490;欢迎来到小十一的博客&#xff01;&#xff01;&#xff01; &#x1f3af;博客主页&#xff1a;&#x1f3af;程序员小十一的博客 &#x1f680;博客专栏&#xff1a;&#x1f680;Python入门基础语法 &#x1f337;欢迎关注&#xff…...

java 自定义json解析注解 复杂json解析

java 自定义json解析注解 复杂json解析 工具类 目录java 自定义json解析注解 复杂json解析 工具类1.背景2、需求-各式各样的json一、一星难度json【json对象中不分层】二、二星难度json【json对象中出现层级】三、三星难度json【json对象中存在数组】四、四星难度json【json对象…...

Vue3配置路由(vue-router)

文章目录前言一、配置路由&#xff08;vue-router&#xff09;1、安装路由2、新建页面3、创建路由配置文件4.特殊报错&#xff01;前言 紧接上篇文章&#xff0c;vue3的配置与vue2是有所差别的&#xff0c;本文就讲述了如何配置&#xff0c;如果本文对你有所帮助请三连支持博主…...

【代码随想录二刷】Day9-字符串-C++

代码随想录二刷Day9 今日任务 28.找出字符串中第一个匹配项的下标 459.重复的子字符串 字符串总结 双指针总结 语言&#xff1a;C KMP 链接&#xff1a;https://programmercarl.com/0459.重复的子字符串.html#kmp 用处&#xff1a;当出现字符串不匹配时&#xff0c;可以利…...

google colab上如何下载bert相关模型

首先要知道模型的地址 tensorflow版本的模型&#xff1a; https://storage.googleapis.com/bert_models/2018_10_18/cased_L-12_H-768_A-12.zip https://storage.googleapis.com/bert_models/2018_11_03/chinese_L-12_H-768_A-12.zip pytorch版本的模型 ‘bert-base-cased’: …...

Vue2.0页面缓存机制联合页面标签的交互(keep-alive + router)

预期效果&#xff1a;&#xff08;借助iview-ui的在线体验页面示意一下&#xff09; 项目中只有一部分页面需要缓存&#xff0c;且存在多级路由的页面。每打开一个菜单&#xff0c;就会新增一个 Tab标签&#xff0c;只要 Tab标签不关闭&#xff0c;对应的页面就会被缓存&#x…...

C++STL剖析(四)—— stack和queue的概念和使用

文章目录1. stack的介绍2. stack的构造3. stack的使用&#x1f351; push&#x1f351; top&#x1f351; pop&#x1f351; empty&#x1f351; size&#x1f351; swap&#x1f351; emplace4. queue的介绍5. queue的构造6. queue的使用&#x1f351; push&#x1f351; size…...

流浪地球 | 建筑人是如何看待小破球里的黑科技的?

大家好&#xff0c;这里是建模助手。 想问问大家今年贺岁档&#xff0c;都跟上没有&#xff0c;今天请允许我蹭一下热点表达一下作为一个科幻迷的爱国之情。 抛开大刘的想象力、各种硬核科技&以及大国情怀不提&#xff0c;破球2中的传承还是让小编很受感动&#xff0c;无…...

软中断在bottom-half中调用

https://www.bilibili.com/read/cv20785285/简介软中断可以在两个位置得到机会执行&#xff1a;硬中断返回前 irq_exit中断下半部 Bottom-half Enable后情景分析情景1spin_unlock_bh__raw_spin_unlock_bh__local_bh_enable_ip 打开Bottom-half&#xff0c;并让softirq有机会…...

GEE遥感云大数据在林业中的应用

近年来遥感技术得到了突飞猛进的发展&#xff0c;航天、航空、临近空间等多遥感平台不断增加&#xff0c;数据的空间、时间、光谱分辨率不断提高&#xff0c;数据量猛增&#xff0c;遥感数据已经越来越具有大数据特征。遥感大数据的出现为相关研究提供了前所未有的机遇&#xf…...

Apollo架构篇 - 客户端架构

前言 本文基于 Apollo 1.8.0 版本展开分析。 客户端 使用 Apollo 支持 API 方式和 Spring 整合两种方式。 API 方式 API 方式是最简单、高效使用使用 Apollo 配置的方式&#xff0c;不依赖 Spring 框架即可使用。 获取命名空间的配置 // 1、获取默认的命名空间的配置 C…...

JVM调优最全面的成长 :参数详解+垃圾算法+示例展示+类文件到源码+面试问题

目录1.优秀的Java开发者1.1 什么是Java&#xff1f;1.2 编程语言1.3 计算机[硬件]能够懂的语言1.3.1 计算机发展史1.3.2 计算机体系结构1.3.3 计算机处理数据过程1.3.4 机器语言1.3.5 不同厂商的CPU1.3.6 操作系统1.3.7 汇编语言1.3.8 高级语言1.3.9 编译型和解释型1.3.9.1 编译…...

linux驱动常用函数

以下为一些常见用户态函数在内核中的替代&#xff0c;包括头文件和函数声明&#xff1a;1、动态申请内存&#xff1a;linux/vmalloc.hvoid *vmalloc(unsigned long size);void vfree(const void *addr);2、字符串操作&#xff1a;linux/string.hvoid * memset(void *,int,__ker…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...