当前位置: 首页 > 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…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

Java后端检查空条件查询

通过抛出运行异常&#xff1a;throw new RuntimeException("请输入查询条件&#xff01;");BranchWarehouseServiceImpl.java // 查询试剂交易&#xff08;入库/出库&#xff09;记录Overridepublic List<BranchWarehouseTransactions> queryForReagent(Branch…...

鸿蒙Navigation路由导航-基本使用介绍

1. Navigation介绍 Navigation组件是路由导航的根视图容器&#xff0c;一般作为Page页面的根容器使用&#xff0c;其内部默认包含了标题栏、内容区和工具栏&#xff0c;其中内容区默认首页显示导航内容&#xff08;Navigation的子组件&#xff09;或非首页显示&#xff08;Nav…...