【数据结构与算法】二叉排序树(BST)

二叉排序树(BST)

需求

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

解决方案分析

  • 使用数组
    • 数组未排序,优点:直接在数组尾添加,速度快。缺点:查找速度慢。
    • 数组排序,优点:可以使用二分查找,查找速度快,缺点:为保证数组有序,在添加新数据时,找到插入位置后,后面的数据需整体移动,速度慢。
  • 使用链式存储 - 链表
    • 不管链表是否有序,查找速度都慢,添加数据速度比数组快,不需要数据整体移动。
  • 使用二叉排序树

基本介绍

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

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

比如针对前面的数据{7,3,10,12,5,1,9},对应的二叉排序树为:
在这里插入图片描述

二叉排序树的创建和遍历

一个大户组常见成对应的二叉排序树,并使用中序遍历二叉排序树

代码实现

public class BinarySortTreeDemo {public static void main(String[] args) {int[] arr = {7, 3, 10, 12, 5, 1, 9};BinarySortTree binarySortTree = new BinarySortTree();// 循环添加节点到二叉排序树for (int i = 0; i < arr.length; i++) {binarySortTree.add(new Node(arr[i]));}// 中序遍历System.out.println("中序遍历二叉排序树");binarySortTree.infixOrder();}
}// 创建二叉排序树
class BinarySortTree {private Node root;// 添加节点的方法public void add(Node node) {// 如果 root 为空,则直接让 root 指向 nodeif (root == null) {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) {this.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 {// 如果当前节点的右子节点为 nullif (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();}}@Overridepublic String toString() {return "Node{" +"value=" + value +'}';}
}

二叉排序树的删除

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

  1. 删除叶子结点
  2. 删除只有一棵子树的的节点
  3. 删除有两棵子树的节点

第一种情况

删除叶子结点

思路:

  1. 先去找到要删除的节点 targeNode
  2. 找到 targeNode 的父节点 parent
  3. 确定 targeNode 是 parent 的左子节点还是右子节点
  4. 根据前面的情况来对应删除
    1. 左子节点:parent.left = null;
    2. 右子节点:parent.right = null;

第二种情况

删除只有一棵子树的的节点

思路:

  1. 先去找到要删除的节点 targeNode

  2. 找到 targeNode 的父节点 parent

  3. 确定 targeNode 的子节点是左子节点还是右子节点

  4. 确定 targeNode 是parent 的左子节点还是右子节点

  5. 如果 targeNode 有左子节点

    1. 如果 targeNode 是 parent 的左子节点:parent.left = targeNode.left;
    2. 如果 targeNode 是 parent 的右子节点:parent.right = targeNode.left;
  6. 如果 targeNode 有右子节点

    1. 如果 targeNode 是 parent 的左子节点:parent.left = targeNode.right;
    2. 如果 targeNode 是 parent 的右子节点:parent.left = targeNode.right;

第三种情况

删除有两棵子树的节点

思路:

  1. 先去找到要删除的节点 targeNode
  2. 找到 targeNode 的父节点 parent
  3. 从 targeNode 的右子树找到最小的节点
  4. 用一个临时变量,将最小的节点的值保存 temp = min
  5. 删除该最小节点
  6. targeNode.value = temp

代码实现:

/*** 得到以 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;
}/*** 得到以 node 为节点的最大节点的值,并删除该值** @param node 传入的节点* @return 返回的是以 node 为根节点的二叉排序树的最大节点的值*/
public int delLiftTreeMax(Node node) {Node target = node;// 循环查找右节点,就会找到最小值while (target.right != null) {target = target.right;}// 这时 target 就指向了最大节点// 删除最大节点delNode(target.value);return target.value;
}/*** 删除节点** @param value 要删除节点的值*/
public void delNode(int value) {if (root == null) {return;} else {// 1. 需要先去找到要删除的节点Node targetNode = search(value);// 如果没有找到要删除的节点if (targetNode == null) {return;}// 如果我们发现当前这棵二叉排序树只有一个节点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) {// 第三种情况// 如果要删除的节点是有两棵子树的节点// 向右子树找最小值
//                targetNode.value = delRightTreeMin(targetNode.right);// 向左子树找最大值targetNode.value = delLiftTreeMax(targetNode.left);} else {// 第二种情况// 如果要删除的节点是只有一棵子树的的节点// 如果要删除的节点有左子节点if (targetNode.left != null) {if (parent != null) {// 如果 targetNode 是 parent 的左子节点if (parent.left.value == value) {parent.left = targetNode.left;} else { // 如果 targetNode 是 parent 的右子节点parent.right = targetNode.left;}} else {root = targetNode.left;}} else { // 如果要删除的节点有右子节点if (parent != null) {// 如果 targetNode 是 parent 的左子节点if (parent.left.value == value) {parent.left = targetNode.right;} else { // 如果 targetNode 是 parent 的右子节点parent.right = targetNode.right;}} else {root = targetNode.right;}}}}
}/*** 查找要删除节点的父节点** @param value 要删除节点的值* @return 如果找到,放回父节点,否则,返回 null*/
public Node searchParent(int value) {if (root == null) {return null;} else {return root.searchParent(value);}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

[C++项目] Boost文档 站内搜索引擎(3): 建立文档及其关键字的正排 倒排索引、jieba库的安装与使用...

之前的两篇文章: 第一篇文章介绍了本项目的背景, 获取了Boost库文档 &#x1fae6;[C项目] Boost文档 站内搜索引擎(1): 项目背景介绍、相关技术栈、相关概念介绍…第二篇文章 分析实现了parser模块. 此模块的作用是 对所有文档html文件, 进行清理并汇总 &#x1fae6;[C项目] …

Spring Boot整合ES的两种方式

使用Spring Data Elasticsearch Starter 在Spring Boot中整合Elasticsearch的方式之一是使用Elasticsearch的官方Spring Data Elasticsearch Starter。该Starter提供了对Elasticsearch的高级集成&#xff0c;简化了配置和管理Elasticsearch客户端。 下面是使用Spring Data E…

【C++】智能指针

一、为什么要智能指针 下面我们先分析下面这段程序有没有什么内存方面的问题&#xff1f; int Div(int a, int b) {if (b 0)throw invalid_argument("除0错误");elsereturn a / b; } void Func() {// 1、如果 p1 这里 new 抛异常会如何&#xff1f;// 2、如果 p2 …

【C++从0到王者】第十六站:stack和queue的使用

文章目录 一、stack的使用1.stack的介绍2.stack的使用 二、queue的使用1.queue的护额晒2.queue的使用 三、stack和queue相关算法题1.最小栈2.栈的压入、弹出序列3.逆波兰表达式4.两个栈实现一个队列5.用两个队列实现栈6.二叉树的层序遍历1.双队列2.用一个变量levelSize去控制 7…

K8S系列文章 之 编写自动化部署K8S脚本

介绍 通过ansible脚本shell实现自动化部署k8s基础集群(v1.25.0) 部署结构 1. 通过二进制部署包镜像安装k8s集群、目录etcd节点只支持1-3个节点、最多三个etcd节点 2. 因k8s版本相对较新、需要升级内核来支持后台程序、当前版本只支持Cento7&#xff0c;内核版本(5.19.4-1.el7…

ffmpeg+nginx实现rtsp协议摄像头web端播放

ffmpegnginx实现rtsp协议摄像头web端播放 环境准备准备nginx环境添加rtmp模块添加hls转发 使用ffmpeg&#xff0c;将摄像头rtsp转为rtmp并推送到nginxVLC播放验证 环境准备 nginx&#xff08;需要安装rtmp模块&#xff09;ffmpeg 6.0vlc播放器&#xff08;本地播放验证&#x…

大数据课程H2——TELECOM的电信流量项目实现

文章作者邮箱&#xff1a;yugongshiyesina.cn 地址&#xff1a;广东惠州 ▲ 本章节目的 ⚪ 了解TELECOM项目的数据收集&#xff1b; ⚪ 了解TELECOM项目的数据清洗&#xff1b; ⚪ 了解TELECOM项目的数据导出&#xff1b; ⚪ 了解TELECOM项目的数据可视化&…

观察者模式(C++)

定义 定义对象间的一种一对多(变化)的依赖关系&#xff0c;以便当一个对象(Subject)的状态发生改变时&#xff0c;所有依赖于它的对象都得到通知并自动更新。 ——《设计模式》GoF 使用场景 一个对象&#xff08;目标对象&#xff09;的状态发生改变&#xff0c;所有的依赖对…

SpringBoot第33讲:SpringBoot集成ShardingJDBC - 基于JPA的读写分离

SpringBoot第33讲&#xff1a;SpringBoot集成ShardingJDBC - 基于JPA的读写分离 本文是SpringBoot第33讲&#xff0c;主要介绍分表分库&#xff0c;以及SpringBoot集成基于 ShardingJDBC 的读写分离实践 文章目录 SpringBoot第33讲&#xff1a;SpringBoot集成ShardingJDBC - 基…

uni-app:实现点击按钮出现底部弹窗(uni.showActionSheet+自定义)

一、通过uni.showActionSheet实现底部选择 效果 代码 <template><view><button click"showActionsheet">点击打开弹窗</button></view> </template><script> export default {methods: {showActionsheet() {uni.showAct…

消息队列项目(2)

我们使用 SQLite 来进行对 Exchange, Queue, Binding 的硬盘保存 对 Message 就保存在硬盘的文本中 SQLite 封装 这里是在 application.yaml 中来引进对 SQLite 的封装 spring:datasource:url: jdbc:sqlite:./data/meta.dbusername:password:driver-class-name: org.sqlite.…

Python 中的机器学习简介:多项式回归

一、说明 多项式回归可以识别自变量和因变量之间的非线性关系。本文是关于回归、梯度下降和 MSE 系列文章的第三篇。前面的文章介绍了简单线性回归、回归的正态方程和多元线性回归。 二、多项式回归 多项式回归用于最适合曲线拟合的复杂数据。它可以被视为多元线性回归的子集。…

APP外包开发的学习流程

学习iOS App的开发是一项有趣和富有挑战性的任务&#xff0c;是一个不断学习和不断进步的过程。掌握基础知识后&#xff0c;不断实践和尝试新的项目将使您的技能不断提升。下面和大家分享一些建议&#xff0c;可以帮助您开始学习iOS App的开发。北京木奇移动技术有限公司&#…

DAY02_Spring—第三方资源配置管理Spring容器Spring注解开发Spring整合Mybatis和Junit

目录 一 第三方资源配置管理1 管理DataSource连接池对象问题导入1.1 管理Druid连接池1.2 管理c3p0连接池 2 加载properties属性文件问题导入2.1 基本用法2.2 配置不加载系统属性2.3 加载properties文件写法 二 Spring容器1 Spring核心容器介绍问题导入1.1 创建容器1.2 获取bean…

软件架构师思维塑造

一、软件系统设计的六项原则 1、单一职责原则&#xff08;Single Responsibility Principle&#xff09; 2、开闭原则&#xff08;Open Closed Principle&#xff09; 3、里氏替换原则&#xff08;Liskov Substitution Principle&#xff09; 4、迪米特法则&#xff08;Law of …

微服务 云原生:基于 Gogs + Drone 进行项目 CI/CD

传统构建部署 以一个简单的前后端项目来说&#xff0c;分别编写前后端的 Dockerfile 文件并构建镜像&#xff0c;然后编写 docker-compose.yml 构建部署&#xff0c;启动运行。 一个简单的例子&#xff1a; 前端&#xff1a; 项目名&#xff1a;kubemanagement-web技术栈&am…

Java中Date方法详解

先进行专栏介绍 本专栏是自己学Java的旅途&#xff0c;纯手敲的代码&#xff0c;自己跟着黑马课程学习的&#xff0c;并加入一些自己的理解&#xff0c;对代码和笔记 进行适当修改。希望能对大家能有所帮助&#xff0c;同时也是请大家对我进行监督&#xff0c;对我写的代码进行…

eeglab(自用)

目录 1.加载、显示数据 2.绘制脑电头皮图 3.绘制通道光谱图 4.预处理工具 5.ICA去除伪迹 5. 提取数据epoch 1.加载、显示数据 观察事件值(Event values)&#xff1a;该数据集中包含2400个事件&#xff0c;每个事件指定了EEG.event结构的字段Type(类型)、position(位置)和…

【Linux命令详解 | cat命令】Linux系统中用于显示或连接文件的命令

文章标题 简介一&#xff0c;参数列表二&#xff0c;使用介绍1. 显示文件内容2. 创建文件3. 连接文件4. 显示行号5. 压缩空行6. 显示特殊字符7. 显示行号和特殊字符8. 从标准输入读取9. 显示文件开头或结尾10. 备份文件11. 显示文件内容至多屏幕大小12. 转义正则表达式13. 显示…

java文件

一.File类 二.扫描指定目录&#xff0c;并找到名称中包含指定字符的所有普通文件&#xff08;不包含目录&#xff09;&#xff0c;并且后续询问用户是否要删除该文件 我的代码: import java.io.File; import java.io.IOException; import java.util.Scanner;public class Tes…