Java超详细讲解排序二叉树
作者:洛语言 发布时间:2022-12-22 22:55:17
排序二叉树概念
二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。是数据结构中的一类。
对于二叉排序树的任何一个非叶子节点, 要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大。
对二叉排序树进行中序遍历,结果就是按从小到大排序的。
排序二叉树类的定义
public class binarySortTree {
class Node{
int value;
Node left;
Node right;
public Node(int value){
this.value = value;
}
public void display(){
System.out.print(this.value + " ");
}
}
Node root;
}
添加节点
排序二叉树添加节点的十分简单,无论使用递归还是循环,思路都一样,这里我用递归的方式讲解。
每次添加一个节点时,判断value(添加节点的值)与root的值的大小关系: 若
root.value < value
, 说明该节点应该添加在root的右子树上。如果右子树为空,直接添加:root.right = new Node(value)
;如果右子树不为空,那么递归进右子树(令root.right为root)。若
root.value >= value
, 说明该节点应该添加在root的左子树上。如果左子树为空,直接添加:root.left = new Node(value)
;如果左子树不为空,那么递归进右子树(令root.left为root)。
代码如下:
//添加节点
//此方法可以类内部方法的调用
private void add(Node root,int value){
//添加节点的值大于根节点的值,该节点添加到根节点的右子树上
if(value > root.value){
//根节点的右子树为空,直接添加
if(root.right == null){
root.right = new Node(value);
}
//根节点右子树不为空,递归往右子树插
else{
add(root.right,value);
}
}
//添加节点的值小于或者等于根节点的值,该节点应该添加到左子树
else{
//左子树为空,直接添加
if(root.left == null){
root.left = new Node(value);
}
//左子树不为空,递归往左子树添加
else{
add(root.left, value);
}
}
}
//此方法在类内部和类外部都可以调用
public void add(int value){
//当前树为空树
if(root == null){
root = new Node(value);
return;
}
add(root, value);
}
中序遍历
因为二叉排序树中序遍历的结果就是排序好的,所以这里只提供中序遍历。
代码如下:
//中序遍历树
private void inPrevOrder(Node root){
if(root == null) return;
inPrevOrder(root.left);
root.display();
inPrevOrder(root.right);
}
public void inPrevOrder(){
System.out.print("中序遍历:");
inPrevOrder(root);
}
查找节点
该方法是查找value
在二叉树中对应的位置,是为删除节点提供的方法。
/**
* 通过value查找二叉树中的节点
* @param root 被查找树的根节点
* @param value 要查找的值
* @return 返回查找到的节点
*/
private Node searchNode(Node root, int value){
//被查找树为null,要查找节点不存在
if(root == null)
return null;
//找到了,返回节点
else if(root.value == value){
return root;
}
//该节点不是要查找节点,继续查找
else{
//该节点的值大于value,往该节点的左子树递归查找
if(root.value > value){
return searchNode(root.left, value);
}
//该节点的值小于value,往该节点的右子树递归查找
else{
return searchNode(root.right, value);
}
}
}
查找某一节点的父节点
该方法是查找二叉树中一个节点的父节点,也是为删除节点提供的方法。
/**
* 查找某节点的父节点,并返回
* @param root 被查找树的根节点
* @param node 要查找的节点
* @return 返回被查找节点的父节点
*/
private Node searchParentNode(Node root, Node node){
//被查找树为null或者根节点就是要查找的节点,那么要查找节点的父节点不存在
if(root == null || root == node){
return null;
}
else if(root.left != null && root.left == node || root.right != null && root.right == node){
return root;
}
else{
if(root.value > node.value){
return searchParentNode(root.left, node);
}
else{
return searchParentNode(root.right, node);
}
}
}
删除节点
删除节点是排序二叉树中最麻烦的方法,因为它有很多种情况。
方法如下:
第一种情况:删除的节点是叶子节点
(1)需求先去找到要删除的结点targetNode(2)找到targetNode的父结点parent
(3)确定targetNode是parent的左子结点还是右子结点
3.1如果targetNode是parent的左子结点:parent.left = null;
3.2如果targetNode是parent的右子结点:parent.right = null;
第二种情况:删除只有一颗子树的节点
(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
第三种情况:删除的节点有左右两个子树
(1)需求先去找到要删除的结点targetNode(2)在右子树找到最小的节点,用一个temp保存这个节点的值,然后删除这个最小节点(该最小节点一定是满足第一种情况的)
(3)targetNode.value = temp
除了以上情况,还要考虑要删除的节点就是根节点的情况(此时它的父节点为null),下面会在代码中展示,代码如下:
public void remove(int vlaue){
//找到要删除的节点
Node targetNode = searchNode(root,vlaue);
//要删除节点不存在
if(targetNode == null) return;
//找到要删除节点的父节点
Node targetNodeParent = searchParentNode(root,targetNode);
//要删除节点为叶子节点
if(targetNode.left == null && targetNode.right == null){
//要删除的节点就是根节点
if(targetNodeParent == null){
root = null;
}
else{
//要删除节点是其父节点的左节点
if(targetNodeParent.left == targetNode){
targetNodeParent.left = null;
}
else{
targetNodeParent.right = null;
}
}
}
//要删除节点只有一个左子树
else if(targetNode.left != null && targetNode.right == null){
//要删除的节点就是根节点
if(targetNodeParent == null) {
root = root.left;
}
//要删除节点是其父节点的左节点
else if(targetNodeParent.left != null && targetNodeParent.left.value == targetNode.value){
targetNodeParent.left = targetNode.left;
}
//要删除节点是其父节点的右节点
else{
targetNodeParent.right = targetNode.left;
}
}
//要删除节点只有一个右子树
else if(targetNode.right != null && targetNode.left == null){
//要删除的节点就是根节点
if(targetNodeParent == null) {
root = root.right;
return;
}
//要删除节点是其父节点的左节点
else if(targetNodeParent.left != null && targetNodeParent.left.value == targetNode.value){
targetNodeParent.left = targetNode.right;
}
//要删除节点是其父节点的右节点
else{
targetNodeParent.right = targetNode.right;
}
}
//要删除节点右左右都有节点
else{
//找到右子树最小的节点
Node minNode = targetNode.right;
while(minNode.left != null){
minNode = minNode.left;
}
int temp = minNode.value;
//找到右子树上最小节点的父节点
Node minNodeParent = searchParentNode(targetNode.right,minNode);
//右子树根节点就是最小节点
if(minNodeParent == null){
targetNode.right = minNode.right;
}
else{
//要删除节点是其父节点的左节点
minNodeParent.left = minNode.right;
}
targetNode.value = temp;
}
}
来源:https://blog.csdn.net/m0_62969222/article/details/124972134
猜你喜欢
- Lucene从今天开始,我们要开始介绍Lucene中索引构建的流程。因为索引构建的逻辑涉及到的东西非常多,如果从构建入口IndexWrite
- 前面一篇文章已经写了如何搭建一个单机版Redis服务, 那么我们应该怎么在现有的系统中集成进来呢? 由于笔者使用的编程语言是Java, 所以
- 安装jdk(介绍三种方法)查看java版本:java -version方法一:利用yum源来安装jdk(此方法不需要配置环境变量)查看yum
- 本文实例为大家分享了javafx实现时钟效果的具体代码,供大家参考,具体内容如下核心为三个函数:第一个为 public void dials
- 同步日志的业务流程处理和日志打印是在同一个线程,日志打印的过程实际上是写文件IO的过程,这个过程是相对耗时的,并且会阻塞主线程的执行,只有日
- 本文实例为大家分享了C语言实现贪吃蛇游戏的具体代码,供大家参考,具体内容如下IDE用的是 VS2019先看效果 代码全览game.
- 本文实例为大家分享了Android实现拼图小游戏的具体代码,供大家参考,具体内容如下目标效果: 1.activity_main.x
- 对 Excel 进行读写操作是生产环境下常见的业务,网上搜索的实现方式都是基于POI和JXL第三方框架,但都不是很全面。小编由于这两天刚好需
- @Autowired注解和静态方法及new关系一、@autowired 与new new出来的对象无法调用@Autowired注入
- 本文实例为大家分享了Android实现支付宝支付密码输入界面的具体代码,供大家参考,具体内容如下效果图:主要代码:import java.u
- 1.<constant name="struts.i18n.encoding" value="UTF-8
- 1 概念和原理一般的字符串匹配算法都是匹配一个子串,例如KMP、Trie,那么如果同时匹配多个子串呢?此时就需要用到AC自动机了。AC自动机
- jedis是redis的java客户端,spring将redis连接池作为一个bean配置。redis连接池分为两种,一种是“redis.c
- 相信做 Java 开发的朋友,大多都是学习过或至少了解过 Java GUI 编程的,其中有大量的事件和控件的绑定,当我们需要在点击某个按钮实
- 直接用英文逗号分隔就可以了,比如:inerface IHello { String sayHello(String name);
- SpringBoot集成Redis 1.添加redis依赖<dependency> <groupId
- 约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;
- 这篇文章主要介绍了Spring如何在一个事务中开启另一个事务,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需
- 我在Eclipse/MyEclipse环境下都测试过了,都好使。需要2个组件,分别是: ext-4.0.2a.jsb2 spke
- 1. dip: device independent pixels(设备独立像素). 不同设备有不同的显示效果,这个和设备硬件有关,一般我们