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

二叉排序树的增删改查(java版)

文章目录

  • 1. 基本节点
  • 2. 二叉排序树
    • 2.1 增加节点
    • 2.2 查找(就是遍历)就一起写了吧
    • 2.3 广度优先遍历
    • 2.4 删除(这个有点意思)
    • 2.5 测试样例

最后的删除,目前我测试的是正确的

1. 基本节点

TreeNode:

class TreeNode{private int val;TreeNode left;TreeNode right;public void setLeft(TreeNode left){this.left = left;}public void setRight(TreeNode right){this.right = right;}TreeNode(){}TreeNode(int val){this.val = val;}public int getVal(){return this.val;}public String toStringNode(){String ans = "[ val = " + this.val;if(this.left != null){ans += "->left = " + this.left.toStringNode();}if(this.right != null){ans += "->right = " + this.right.toStringNode() + "]";}return ans;}public void setVal(int val){this.val = val;}
}

2. 二叉排序树

class BinaryTree{public TreeNode root;
}

里面写一些方法吧!!!

2.1 增加节点

其实就是插入:

public void insert(int val){TreeNode newNode = new TreeNode(val);if(root == null){root = newNode;return;}TreeNode curNode = root;TreeNode preNode;while(true){preNode = curNode;if(newNode.getVal() > curNode.getVal()){curNode = curNode.right;if(curNode == null){preNode.setRight(newNode);return;}}else{curNode = curNode.left;if(curNode == null){preNode.setLeft(newNode);return;}}}}

2.2 查找(就是遍历)就一起写了吧

跟修改一样

public void inOrder(TreeNode root){if(root == null)return;inOrder(root.left);System.out.print(root.getVal() + " ");inOrder(root.right);}public void preOrder(TreeNode root){if(root == null)return;System.out.print(root.getVal() + " ");preOrder(root.left);preOrder(root.right);}public void HOrder(TreeNode root){if(root == null)return;HOrder(root.left);HOrder(root.right);System.out.print(root.getVal() + " ");}

2.3 广度优先遍历

利用队列

// 广度优先搜索void BFS(){if(this.root == null){System.out.println("BFS: null");return;}System.out.print("BFS: ");Queue<TreeNode> queue = new LinkedList<>();queue.add(this.root);while(!queue.isEmpty()){TreeNode cur = queue.poll();System.out.print(cur.getVal() + " ");if(cur.left != null)queue.add(cur.left);if(cur.right != null)queue.add(cur.right);}}

2.4 删除(这个有点意思)

分了六类情况:

  • 目标节点是叶子节点(直接删了)
  • 目标节点只有一个孩子(直接连接上)
  • 目标节点有俩孩子
    • 左孩子没有右孩子(把目标右子树连在左孩子的右孩子上,然后目标父亲那条指向左孩子)
    • 右孩子没有左孩子(把目标左子树连在右孩子的左孩子上,然后目标父亲那条指向右孩子)
    • 最坏情况了,找目标节点的左孩子最右或者左孩子最左(交换值,删了那个被交换的孩子)
// 删除节点// 获取最左最右节点public TreeNode getLR(TreeNode root){if(root == null || (root.left == null && root.right == null))return null;TreeNode ans;if(root.left != null){if(root.left.right == null)return root.left;ans = root.left.right;while(ans.right != null){ans = ans.right;}// System.out.println("获取最右");return ans;}if(root.right != null){if(root.right.left == null)return root.right;ans = root.right.left;while(ans.left != null){ans = ans.left;}// System.out.println("获取最左");return ans;}return null;}// 获取父节点public TreeNode getParent(TreeNode root, int val){if(root == null || (root.left == null && root.right == null) || root.getVal() == val)return null;// 左孩子不等if(root.getVal() > val){if(root.left != null){if(root.left.getVal() == val)return root;elsereturn getParent(root.left, val);}elsereturn null;}else{if(root.right != null){if(root.right.getVal() == val)return root;elsereturn getParent(root.right, val);}elsereturn null;}}public void delNode(int val){TreeNode parent = new TreeNode(Integer.MAX_VALUE);parent.left = root;delNode(val, parent, null);this.root = parent.left;}public void delNode(int val, TreeNode root, TreeNode parent){if(root == null)return;if(root.getVal() < val){delNode(val, root.right, root);}else if(root.getVal() > val){delNode(val, root.left, root);}else{  // 相等if(root.left != null && root.right == null){    // 没有左孩子if(parent.left == root){parent.left = root.left;}else{parent.right = root.left;}}else if(root.left == null && root.right != null){  // 没有右孩子if(parent.left == root){parent.left = root.right;}else{parent.right = root.right;}}else if(root.left == null && root.right == null){  // 都是nullif(parent.left == root){parent.left = null;}else{parent.right = null;} }else{ // 进行交换if(root.left.right == null){root.left.right = root.right;if(parent.left == root){parent.left = root.left;}else{parent.right = root.left;}}else if(root.right.left == null){root.right.left = root.left;if(parent.left == root){parent.left = root.left;}else{parent.right = root.left;}}else{TreeNode cur = getLR(root); // 获取最左最右节点// 删除那个节点TreeNode curParent = getParent(root, cur.getVal()); // 获取父节点if(curParent.getVal() > cur.getVal())curParent.left = null;else{curParent.right = null;}root.setVal(cur.getVal());  // 设置值}}}}

2.5 测试样例

public class Test2{public static void main(String[] args) {TreeNode node1 = new TreeNode(1);TreeNode node2 = new TreeNode(2);TreeNode node3 = new TreeNode(3);TreeNode node4 = new TreeNode(4);TreeNode node5 = new TreeNode(5);TreeNode node6 = new TreeNode(6);// 进行构建node1.setRight(node2);node1.setLeft(node3);node3.setLeft(node4);node4.setLeft(node5);node4.setRight(node6);// System.out.println(node1.toStringNode());BinaryTree b = new BinaryTree();b.insert(5);b.insert(7);b.insert(4);b.insert(2);b.insert(0);b.insert(3);b.insert(8);b.insert(6);b.insert(1);// System.out.println(b.root.toStringNode());// System.out.println(b.getParent(b.root, 3).getVal());for(int i = 8; i >= 0; i--){System.out.println("删除了:" + i);b.delNode(i);b.BFS();System.out.println();}// // 中序// System.out.println("中序:");// // 先序// System.out.println();// System.out.println("先序:");// b.preOrder(b.root);// // 后序// System.out.println();// System.out.println("后序:");// b.HOrder(b.root);// // 深度System.out.println();b.BFS();}
}

相关文章:

二叉排序树的增删改查(java版)

文章目录 1. 基本节点2. 二叉排序树2.1 增加节点2.2 查找&#xff08;就是遍历&#xff09;就一起写了吧2.3 广度优先遍历2.4 删除&#xff08;这个有点意思&#xff09;2.5 测试样例 最后的删除&#xff0c;目前我测试的是正确的 1. 基本节点 TreeNode: class TreeNode{pri…...

linux下coredump问题的定位分析方法

(Owed by: 春夜喜雨 http://blog.csdn.net/chunyexiyu) 参考&#xff1a;https://blog.csdn.net/m0_73698480/article/details/130077852 最近定位了一段时间linux下的崩溃问题&#xff0c;又收集了一些思路&#xff0c;特整理记录一下。 常见coredump定位方法是&#xff1a…...

第十届蓝桥杯省赛真题(C/C++大学B组)

目录 试题 A: 组队 试题 B: 年号字串 试题 C: 数列求值 试题 D: 数的分解 试题 E: 迷宫 试题 F: 特别数的和 试题 G&#xff1a;完全二叉树的权值 试题 H&#xff1a;等差数列 试题 I&#xff1a;后缀表达式&#xff08;不一定对&#xff09; 试题 J&#xff1a;灵能…...

Scrapy 爬取m3u8视频

Scrapy 爬取m3u8视频 【一】效果展示 爬取ts文件样式 合成的MP4文件 【二】分析m3u8文件路径 视频地址&#xff1a;[在线播放我独自升级 第03集 - 高清资源](https://www.physkan.com/ph/175552-8-3.html) 【1】找到m3u8文件 这里任务目标很明确 就是找m3u8文件 打开浏览器…...

LVGL简单记录

1、 vs中代码旁边有个小锁删除git 2、Visual Studio 试图编译已删除的文件&#xff0c; 如果这个文件也是你不再需要编译的文件&#xff0c;且已经从文件系统中删除&#xff0c;你需要从 .vcxproj 文件中移除或者注释掉这一行&#xff0c;以停止Visual Studio尝试去编译一个不…...

计算机网络——ARP协议

前言 本博客是博主用于复习计算机网络的博客&#xff0c;如果疏忽出现错误&#xff0c;还望各位指正。 这篇博客是在B站掌芝士zzs这个UP主的视频的总结&#xff0c;讲的非常好。 可以先去看一篇视频&#xff0c;再来参考这篇笔记&#xff08;或者说直接偷走&#xff09;。 …...

【C++]C/C++的内存管理

这篇博客将会带着大家解决以下几个问题 1. C/C内存分布 2. C语言中动态内存管理方式 3. C中动态内存管理 4. operator new与operator delete函数 5. new和delete的实现原理 6. 定位new表达式(placement-new) 1. C/C内存分布 我们先来看下面的一段代码和相关问题 int global…...

深入理解计算机网络分层结构

一、 为什么要分层&#xff1f; 计算机网络分层的主要目的是将复杂的网络通信过程分解为多个相互独立的层次&#xff0c;每个层次负责特定的功能。这样做有以下几个好处&#xff1a; 模块化设计&#xff1a;每个层次都有清晰定义的功能和接口&#xff0c;使得网络系统更易于设…...

亚马逊云科技CTO带你学习云计算降本增效秘诀

2023亚马逊云科技一年一度的重磅春晚--Re:invent上有诸多不同话题的主题Keynote&#xff0c;这次小李哥带大家复盘来自亚马逊CTO: Wener博士的主题演讲: 云架构节俭之道1️⃣节俭对于云计算为什么重要&#xff1f; ▶️企业基础设施投入大&#xff0c;利用好降本策略可以减少巨…...

快速上手Vue

目录 概念 创建实例 插值表达式 Vue响应式特性 概念 Vue是一个用于 构建用户界面 的 渐进式 框架 构建用户界面&#xff1a;基于数据渲染出用户看到的页面 渐进式&#xff1a;Vue相关生态&#xff1a;声明式渲染<组件系统<客户端路由<大规模状态管理<构建工具 V…...

java 目录整理

Java知识相关目录主要参考黑马程序员 风清扬老师的视屏,参考链接为 Java_黑马刘意(风清扬)2019最新版_Java入门视频_Java入门_Java编程_Java入门教程_黑马教程_黑马程序员_idea版_哔哩哔哩_bilibili 1、java 基础 java基本认识?java跨平台原理?jdk、jre、jvm的联系? 链接:…...

使用Python的Pillow库进行图像处理书法参赛作品

介绍&#xff1a; 在计算机视觉和图像处理领域&#xff0c;Python是一种强大而流行的编程语言。它提供了许多优秀的库和工具&#xff0c;使得图像处理任务变得轻松和高效。本文将介绍如何使用Python的wxPython和Pillow库来选择JPEG图像文件&#xff0c;并对选中的图像进行调整和…...

docker 容器指定utf-8编码

在运行 Docker 容器的时候&#xff0c;如果容器内应用需要使用 UTF-8 编码来正常处理中文&#xff0c;你可以通过设置环境变量来指定编码。 可以使用 -e 或者 --env 标志来设置环境变量。比如&#xff0c;设置 LANG 和 LC_ALL 环境变量为 C.UTF-8 或者 en_US.UTF-8&#xff1a…...

单例模式以及常见的两种实现模式

单例模式是校招中最常考的设计模式之一. 设计模式其实就是类似于“规章制度”&#xff0c;按照这个套路来进行操作。 单例模式能保证某个类在程序中只存在唯一 一份实例。而不会创建出多个实例&#xff0c;如果创建出了多个实例&#xff0c;就会编译报错。而不会创建出多个实…...

Java hashCode() 和 equals()的若干问题解答

Java hashCode() 和 equals()的若干问题解答 本章的内容主要解决下面几个问题&#xff1a; 1 equals() 的作用是什么&#xff1f; 2 equals() 与 的区别是什么&#xff1f; 3 hashCode() 的作用是什么&#xff1f; 4 hashCode() 和 equals() 之间有什么联系&#xff1f; …...

高级IO——React服务器简单实现

3.4Reactor服务器实现 1.connect封装 ​ 每一个连接都要有一个文件描述符和输入输出缓冲区&#xff0c;还有读、写、异常处理的回调方法&#xff1b; ​ 还包括指向服务器的回指指针&#xff1b; class connection; class tcpserver;using func_t std::function<void(s…...

Qt使用插件QPluginLoader 机制开发

简介&#xff1a; 插件(Plug-in,又称addin、add-in、addon或add-on,又译外挂)是一种遵循一定规范的应用程序接口编写出来的程序。 Qt 提供了2种APIs来创建插件&#xff1a; 一种高级API&#xff0c;用于为Qt本身编写插件&#xff1a;自定义数据库驱动程序&#xff0c;图像格…...

双子座 Gemini1.5和谷歌的本质

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...

二百三十、MySQL——MySQL表的索引

1 目的 梳理一下目前MySQL维度表的索引情况&#xff0c;当然网上也有其他博客专门讲MySQL索引的&#xff0c;我这边只是梳理一下目前的索引状况而已 2单列索引 2.1 索引截图 2.2 建表语句 3 联合索引 3.1 索引截图 3.2 建表语句 4 参考的优秀博客 http://t.csdnimg.cn/ZF7…...

并发编程之ThreadLocal使用及原理

ThreadLocal主要是为了解决线程安全性问题的 非线程安全举例 public class ThreadLocalDemo {// 非线程安全的private static final SimpleDateFormat sdf new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");public static Date parse(String strDate) throws ParseExc…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

MySQL:分区的基本使用

目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区&#xff08;Partitioning&#xff09;是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分&#xff08;分区&#xff09;可以独立存储、管理和优化&#xff0c;…...

Java 与 MySQL 性能优化:MySQL 慢 SQL 诊断与分析方法详解

文章目录 一、开启慢查询日志&#xff0c;定位耗时SQL1.1 查看慢查询日志是否开启1.2 临时开启慢查询日志1.3 永久开启慢查询日志1.4 分析慢查询日志 二、使用EXPLAIN分析SQL执行计划2.1 EXPLAIN的基本使用2.2 EXPLAIN分析案例2.3 根据EXPLAIN结果优化SQL 三、使用SHOW PROFILE…...

路由基础-路由表

本篇将会向读者介绍路由的基本概念。 前言 在一个典型的数据通信网络中&#xff0c;往往存在多个不同的IP网段&#xff0c;数据在不同的IP网段之间交互是需要借助三层设备的&#xff0c;这些设备具备路由能力&#xff0c;能够实现数据的跨网段转发。 路由是数据通信网络中最基…...