java学习之数据结构:四、树(代码补充)

这部分主要是用代码实现有序二叉树、树遍历、删除节点

目录

1.构建有序二叉树

1.1原理

 1.2插入实现

2.广度优先遍历--队列实现

3.深度优先遍历--递归实现

3.1先序遍历

3.2中序遍历

3.3后序遍历

4.删除

4.1删除叶子节点

4.2删除有一棵子树的节点

4.3删除有两棵子树的节点

5.整体代码


1.构建有序二叉树

1.1原理

左边节点值小于父节点,右边节点值大于父节点,看下图

 1.2插入实现

当传入value值时,判断root节点是否为空:空的话建立新节点做root;不空,建立一个中间节点index,然后循环按照插入原理判断插到哪,代码如下:

 public void insert(int value){Node node = new Node(value);if(root==null){root = node;return;}Node index = root;while(true) {if(index.value>value) {//要插入的节点值小if(index.left==null) {//插入index.left=node;return;}index=index.left;}else{//要插入的节点值大if(index.right==null){index.right=node;return;}index=index.right;}}

2.广度优先遍历--队列实现

广度优先遍历就是层次遍历,使用队列实现。当队列中进入一个新节点,输出后就找这个节点的左右孩子入队。

代码如下:

    public void levelOrder() {Queue<Node> queue = new LinkedList<Node>();if(root!=null) {queue.add(root);}Node index;while (!queue.isEmpty()){index = queue.poll();System.out.print(index.value+Messages.getString("BinaryTree.0")); //$NON-NLS-1$if(index.left!=null){queue.add(index.left);}if(index.right!=null) {queue.add(index.right);}}System.out.println();}

3.深度优先遍历--递归实现

3.1先序遍历

就是根-左-右的顺序,使用递归实现,代码如下:

    /** 先序遍历*/public void beforeOrder(Node node){if(node==null) {return;}System.out.print(node.value+Messages.getString("BinaryTree.1"));beforeOrder(node.left);beforeOrder(node.right);}

3.2中序遍历

使用左-根-右顺序

    /** 中序遍历*/public void inOrder(Node node){if(node==null){return;}inOrder(node.left);System.out.print(node.value+Messages.getString("BinaryTree.2")); //$NON-NLS-1$inOrder(node.right);}

3.3后序遍历

使用左-右-根顺序,代码如下:

    /** 后序遍历*/public void afterOrder(Node node) {if(node==null) {return;}afterOrder(node.left);afterOrder(node.right);System.out.print(node.value+Messages.getString("BinaryTree.3")); }

4.删除

删除比较复杂,要分三种情况:

4.1删除叶子节点

  1. 找到目标节点:在二叉搜索树中定位要删除的目标节点target 。
  2. 找到父节点:确定target节点的父节点parent 。
  3. 判断父节点情况
    • 若无父节点,意味着target是根节点,直接将根节点置为null 。
    • 若有父节点,判断targetparent的左子还是右子:是左子就执行parent.left = null ;是右子就执行parent.right = null 。

需要额外写一个函数来寻找父节点,代码如下:

    /*** 找目标值的父节点*/public Node searchParent(int value) {if(root==null) {return null;}Node index = root;while (index!=null) {if((index.left!=null&&index.left.value==value)||(index.right!=null&&index.right.value==value)) {return index;}else if (index.value>value) {index=index.left;}else {index = index.right;}}return null;}

这部分代码如下:

		if(target.left==null&&target.right==null) {//叶子节点//没有父节点if(parent==null) {root=null;return;}//有父节点if(parent.left!=null&&parent.left.value==value) {parent.left=null;}else {parent.right=null;}}

4.2删除有一棵子树的节点

  1. 找到目标节点:确定要删除的节点target 。
  2. 找到父节点:找到target节点的父节点parent 。
  3. 判断父节点和子树情况
    • 若无父节点,即target是根节点,若target有左子树,让根节点指向其左子树(root = root.left );若有右子树,让根节点指向其右子树(root = root.right )。
    • 若有父节点,先确定targetparent的左子还是右子,再根据target自身有左子树还是右子树,调整parent相应子树指针(如parent.left = target.left 或parent.right = target.right )。

代码如下:

			//有一棵子树的节点//没有父节点if(parent==null) {//目标节点有左子树还是右子树if(target.left!=null) {root = root.left;}else {root=root.right;}return;}//有父节点//判断目标节点是父节点的左孩子还是右孩子if(parent.left!=null&&parent.left.value==value) {//左孩子//目标节点有左子树还是右子树if(target.left!=null) {parent.left = target.left;}else {parent.left = target.right;}}else {//右孩子//目标节点有左子树还是右子树if(target.left!=null) {parent.right = target.left;}else {parent.right = target.right;}}

4.3删除有两棵子树的节点

  1. 找到目标节点:定位要删除的节点target 。
  2. 替换节点选择:获取target左子树的最大值节点或者右子树的最小值节点作为替换节点。
  3. 删除目标节点:用选定的替换节点替代target节点的位置 ,并处理好相关子树连接关系(如parent.left = target.right 或parent.right = target.left 等)。

需要额外写一个判断最小值的函数:

	/*** 找树当中的最小值*/public int min(Node node) {Node index = node;while(index.left!=null) {index=index.left;}return index.value;}

 

代码如下:

 if(target.left!=null&&target.right!=null) {//有两棵子树的节点int minVal = min(target.right);delete(minVal);target.value = minVal;}

5.整体代码

代码如下:

package com.qcby.树;import java.util.LinkedList;
import java.util.Queue;public class BinaryTree {Node root;/*** 插入*/public void insert(int value){Node node = new Node(value);if(root==null){root = node;return;}Node index = root;while(true) {if(index.value>value) {//要插入的节点值小if(index.left==null) {//插入index.left=node;return;}index=index.left;}else{//要插入的节点值大if(index.right==null){index.right=node;return;}index=index.right;}}}/** 广度优先遍历*/public void levelOrder() {Queue<Node> queue = new LinkedList<Node>();if(root!=null) {queue.add(root);}Node index;while (!queue.isEmpty()){index = queue.poll();System.out.print(index.value+Messages.getString("BinaryTree.0")); //$NON-NLS-1$if(index.left!=null){queue.add(index.left);}if(index.right!=null) {queue.add(index.right);}}System.out.println();}/** 先序遍历*/public void beforeOrder(Node node){if(node==null) {return;}System.out.print(node.value+Messages.getString("BinaryTree.1")); //$NON-NLS-1$beforeOrder(node.left);beforeOrder(node.right);}/** 中序遍历*/public void inOrder(Node node){if(node==null){return;}inOrder(node.left);System.out.print(node.value+Messages.getString("BinaryTree.2")); //$NON-NLS-1$inOrder(node.right);}/** 后序遍历*/public void afterOrder(Node node) {if(node==null) {return;}afterOrder(node.left);afterOrder(node.right);System.out.print(node.value+Messages.getString("BinaryTree.3")); //$NON-NLS-1$}/** 查找*/public Node search(int value) {if(root==null) {return null;}Node index = root;while (index!=null) {if(index.value==value){return index;}else if(index.value>value) {index = index.left;}else {index=index.right;}}return null;}/*** 找目标值的父节点*/public Node searchParent(int value) {if(root==null) {return null;}Node index = root;while (index!=null) {if((index.left!=null&&index.left.value==value)||(index.right!=null&&index.right.value==value)) {return index;}else if (index.value>value) {index=index.left;}else {index = index.right;}}return null;}/*** 找树当中的最小值*/public int min(Node node) {Node index = node;while(index.left!=null) {index=index.left;}return index.value;}/*** 删除*/public void delete(int value){if(root==null) {System.out.println(Messages.getString("BinaryTree.4")); return;}//找目标节点Node target = search(value);if(target==null) {System.out.println(Messages.getString("BinaryTree.5")); return;}//找目标节点的父节点Node parent = searchParent(value);//三种情况,分情况讨论if(target.left==null&&target.right==null) {//叶子节点//没有父节点if(parent==null) {root=null;return;}//有父节点if(parent.left!=null&&parent.left.value==value) {parent.left=null;}else {parent.right=null;}}else if(target.left!=null&&target.right!=null) {//有两棵子树的节点int minVal = min(target.right);delete(minVal);target.value = minVal;}else {//有一棵子树的节点//没有父节点if(parent==null) {//目标节点有左子树还是右子树if(target.left!=null) {root = root.left;}else {root=root.right;}return;}//有父节点//判断目标节点是父节点的左孩子还是右孩子if(parent.left!=null&&parent.left.value==value) {//左孩子//目标节点有左子树还是右子树if(target.left!=null) {parent.left = target.left;}else {parent.left = target.right;}}else {//右孩子//目标节点有左子树还是右子树if(target.left!=null) {parent.right = target.left;}else {parent.right = target.right;}}}}@Overridepublic String toString() {return "BinaryTree [root=" + root + "]";}}

 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于 HTML 和 CSS 实现的 3D 翻转卡片效果

一、引言 在网页设计中&#xff0c;为了增加用户的交互体验和视觉吸引力&#xff0c;常常会运用一些独特的效果。本文将详细介绍一个基于 HTML 和 CSS 实现的 3D 翻转卡片效果&#xff0c;通过对代码的剖析&#xff0c;让你了解如何创建一个具有立体感的卡片&#xff0c;在鼠标…

PHP数组排序深度解析:sort()、rsort()、asort()、arsort()、ksort()、krsort() 的适用场景与性能对比

在PHP开发中&#xff0c;数组排序是日常操作的核心技能之一。无论是处理用户数据、产品列表&#xff0c;还是分析日志信息&#xff0c;合理的排序方法能显著提升代码的效率和可维护性。PHP提供了多种数组排序函数&#xff08;如 sort()、rsort()、asort() 等&#xff09;&#…

C++ 中二级指针的正确释放方法

C 中二级指针的正确释放 一、什么是二级指针&#xff1f; 简单说&#xff0c;二级指针就是指向指针的指针。 即&#xff1a; int** p;它可以指向一个 int*&#xff0c;而 int* 又指向一个 int 类型的变量。 常见应用场景 动态二维数组&#xff08;例如 int** matrix&#x…

Linux 进程基础(二):操作系统

目录 一、什么是操作系统&#xff1a;用户和电脑之间的「翻译官」&#x1f310; OS 的层状结构&#x1f9e9; 案例解析&#xff1a;双击鼠标的「跨层之旅」 二、操作系统的必要性探究&#xff1a;缺乏操作系统的环境面临的挑战剖析&#x1f511; OS 的「管理者」属性&#xff1…

SpringMVC详解

一&#xff1a;Maven 1.1 概述 &#xff08;1&#xff09;项目结构 所有IDE使用Maven创建的项目结构完全一样&#xff0c;maven项目可通用 &#xff08;2&#xff09;构建流程&#xff08;编译、测试、打包、发布&#xff09; &#xff08;3&#xff09;依赖管理 定义&#xff…

深入解析Linux进程间通信(IPC):机制、应用与最佳实践

引言 在多任务操作系统中&#xff0c;进程间通信&#xff08;Inter-Process Communication, IPC&#xff09;是协同工作的核心机制。Linux作为现代操作系统的典范&#xff0c;提供了8种主要IPC方式&#xff0c;从传统的管道到面向网络的套接字&#xff0c;每种方法都暗藏独特的…

linux 使用nginx部署ssl证书,将http升级为https

前言 本文基于&#xff1a;操作系统 CentOS Stream 8 使用工具&#xff1a;Xshell8、Xftp8 服务器基础环境&#xff1a; nginx - 请查看 linux 使用nginx部署vue、react项目 所需服务器基础环境&#xff0c;请根据提示进行下载、安装。 1.下载证书 以腾讯云为例&#xff…

深入了解Linux系统—— 环境变量

命令行参数 我们知道&#xff0c;我们使用的指令它本质上也是一个程序&#xff0c;我们要执行这个指令&#xff0c;输入指令名然后回车即可执行&#xff1b;但是对于指令带选项&#xff0c;又是如何实现的呢&#xff1f; 问题&#xff1a;main函数有没有参数&#xff1f; 在我…

Oracle OCP认证考试考点详解083系列07

题记&#xff1a; 本系列主要讲解Oracle OCP认证考试考点&#xff08;题目&#xff09;&#xff0c;适用于19C/21C,跟着学OCP考试必过。 31. 第31题&#xff1a; 题目 解析及答案&#xff1a; 从 Oracle 19c 开始&#xff0c;数据库配置助手&#xff08;DBCA&#xff09;在克…

word批量转pdf工具

word批量转pdf工具 图片 说到了办公&#xff0c;怎能不提PDF转换哦&#xff1f; 这是一款一键就可以批量word转换为PDF的小工具&#xff0c;简直是VB界的一股清流。 图片 操作简单到不行&#xff0c;只要把需要转换的word文件和这个工具放在同一个文件夹里&#xff0c;双击…

【网络原理】深入理解HTTPS协议

本篇博客给大家带来的是网络原理的知识点, 由于时间有限, 分三天来写, 本篇为线程第三篇,也是最后一篇. &#x1f40e;文章专栏: JavaEE初阶 &#x1f680;若有问题 评论区见 ❤ 欢迎大家点赞 评论 收藏 分享 如果你不知道分享给谁,那就分享给薯条. 你们的支持是我不断创作的动…

解决Maven项目中报错“java不支持版本6即更高的版本 7”

错误背景 当Maven项目编译或运行时出现错误提示 Java不支持版本6即更高的版本7&#xff0c;通常是由于项目配置的JDK版本与当前环境或编译器设置不一致导致的。例如&#xff1a; 项目配置的Java版本为6或7&#xff0c;但实际使用的是JDK 17。Maven或IDE的编译器未正确指定目标…