Java实现二叉查找树的增删查详解

目录
  • 定义
  • 增加节点
  • 查询节点
  • 删除节点

定义

二叉查找树(ADT)是一个具有对于树种的某个节点X,它的左节点都比X小,它的右节点都比X大的二叉树。如下就是一个符合

要求的二叉查找树:

增加节点

1.定义节点类:

class Node{
    int val;
    Node left;
    Node right;
    public Node(int val){
        this.val=val;
    }
}

2.插入元素

我们采用递归的方法:

1.判断与根节点是否相同,相同无需操作

2.比根元素小往左边查找,左节点不存在的话则作为左节点插入即可

3.比根元素大往右边查找,右节点不存在的话则作为右节点插入即可

代码实现如下:

Node root;

    /**
     * 添加元素
     * @param val
     */
    public void add(int val){
        if(root==null){
            root=new Node(val);
            return;
        }
        addNode(val,root);
    }
    private void addNode(int val,Node root){
        if(root==null || root.val==val){
            return;
        }
        if(root.val>val){
            if(root.left==null){
                root.left=new Node(val);
            }else {
                addNode(val,root.left);
            }
        }else {
            if(root.right==null){
                root.right=new Node(val);
            }else {
                addNode(val,root.right);
            }
        }
    }

查询节点

我们采用递归的方法:

1.判断与根节点是否相同,相同则返回true

2.比根元素小往左边查找,左节点为null则返回false表示不存在

3.比根元素大往右边查找,右节点为null则返回false表示不存在

代码实现如下:

/**
     * 判断指定值是否存在
     * @param val 指定值
     * @return true--存在   false--不存在
     */
    public boolean findVale(int val){
        return isExit(root,val);
    }

    private boolean isExit(Node node,int val){
        if(node==null){
            return false;
        }
        if(node.val==val){
            return true;
        }else if(node.val>val){
            return isExit(node.left,val);
        }else {
            return isExit(node.right,val);
        }
    }

删除节点

删除元素时要判断元素的情况:

1.删除的元素没有叶子节点,直接删除,如删除值为1的节点,虽然平衡性不是太好,但是还是符合二叉查找树的特性

2.删除的元素只有一个节点,删除元素并将指针指向其子节点 ,如删除值为4的节点:

3.删除的元素有左右两个节点,从右节点中找出大于该节点的最小节点,作为新的节点A,如删除节点值为2的节点:

代码实现如下:

/**
     * 删除元素
     * 1.删除的元素没有叶子节点,直接删除
     * 2.删除的元素只有一个节点,删除元素并将指针指向其子节点
     * 3.删除的元素有两个节点,从右节点中找出大于该元素的最小值,作为新的节点
     * @param val
     */
    public void deleteElement(int val){
        deleteElement(null,root,val,true);
    }

    /**
     * 删除元素
     * @param prev 父节点
     * @param root 当前节点
     * @param val  删除值
     * @param isright  是否是右节点
     */
    private void deleteElement(Node prev,Node root,int val,boolean isright){
        if(root.val==val){
            //删除的元素没有叶子节点,直接删除
            if(root.left==null &&  root.right==null){
                changeValue(prev,null,isright);
            }else if(root.left!=null &&  root.right!=null){
                //3.删除的元素有两个节点,从右节点中找出大于该元素的最小值,作为新的节点
                changeValue(prev,new Node(findMinGt(root,root.right,true)),isright);
                if(prev==null){
                    //对于头结点的删除特殊处理
                    prev=this.root;
                    prev.left=root.left;
                    prev.right=root.right;
                    return;
                }
                if(isright){
                    prev.right.right=root.right;
                    prev.right.left=root.left;
                }else {
                    prev.left.right=root.right;
                    prev.left.left=root.left;
                }
            }//删除的元素只有一个节点,删除元素并将指针指向其子节点
            else if(root.left!=null){
                changeValue(prev,root.left,isright);
            }else {
                changeValue(prev,root.right,isright);
            }
            return;
        }
        if(root.val>val){
            deleteElement(root,root.left,val,false);
        }else{
            deleteElement(root,root.right,val,true);
        }
    }
    //改变元素值
    private void changeValue(Node prev,Node value,boolean isright){
        if(prev==null){
            root=value;
            return;
        }
        if(isright){
            prev.right=value;
        }else {
            prev.left=value;
        }
    }
    //寻找大于根节点的最小值
    private int findMinGt(Node prev,Node root,boolean isRight){
        if(root.left==null && root.right==null){
            changeValue(prev,null,isRight);
            return root.val;
        }
        if(root.left==null){
            changeValue(prev,null,isRight);
            return root.val;
        }
        return findMinGt(root,root.left,false);
    }

到此这篇关于Java实现二叉查找树的增删查详解的文章就介绍到这了,更多相关Java二叉查找树增删查内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • java 二叉查找树实例代码

    java 二叉查找树实例代码 1.左边<中间<右边 2.前序遍历 左中右 3.中序遍历 中左右 4.后序遍历 左右中 public class BinaryTree { // 二叉树的根节点 public TreeNode rootNode ; // 记录搜索深度 public int count; /** * 利用传入一个数组来建立二叉树 */ public BinaryTree(int[] data) { for (int i = 0; i < data. length; i++)

  • Java数据结构之二叉查找树的实现

    目录 定义 节点结构 查找算法 插入算法 删除算法 完整代码 定义 二叉查找树(亦称二叉搜索树.二叉排序树)是一棵二叉树,且各结点关键词互异,其中根序列按其关键词递增排列. 等价描述:二叉查找树中任一结点 P,其左子树中结点的关键词都小于 P 的关键词,右子树中结点的关键词都大于 P 的关键词,且结点 P 的左右子树也都是二叉查找树 节点结构 :one: key:关键字的值 :two: value:关键字的存储信息 :three: left:左节点的引用 :four: right:右节点的引用

  • java二叉查找树的实现代码

    本文实例为大家分享了java二叉查找树的具体代码,供大家参考,具体内容如下 package 查找; import edu.princeton.cs.algs4.Queue; import edu.princeton.cs.algs4.StdOut; public class BST<Key extends Comparable<Key>, Value> { private class Node { private Key key; // 键 private Value value;

  • Java基于二叉查找树实现排序功能示例

    本文实例讲述了Java基于二叉查找树实现排序功能.分享给大家供大家参考,具体如下: /** * 无论排序的对象是什么,都要实现Comparable接口 * * @param <T> */ public class BinaryNode<T extends Comparable<T>> { private static int index = 0; // 排序下标 private static int len = 0; // 最大数组长度 private T t; //

  • Java实现二叉查找树的增删查详解

    目录 定义 增加节点 查询节点 删除节点 定义 二叉查找树(ADT)是一个具有对于树种的某个节点X,它的左节点都比X小,它的右节点都比X大的二叉树.如下就是一个符合 要求的二叉查找树: 增加节点 1.定义节点类: class Node{ int val; Node left; Node right; public Node(int val){ this.val=val; } } 2.插入元素 我们采用递归的方法: 1.判断与根节点是否相同,相同无需操作 2.比根元素小往左边查找,左节点不存在的话

  • Java实现顺序表的操作详解

    目录 一.顺序表是什么 二.自定义异常 空引用异常 下标越界异常 三.顺序表的方法 顺序表的实现 获取顺序表长度 顺序表是否为空 顺序表是否为满 打印顺序表 末尾新增元素 指定位置新增元素 判断是否包含某元素 查找某个元素对应的位置 获取 pos 位置的元素 给 pos 位置的元素赋值 删除第一次出现的关键字key 清空顺序表 四.自定义顺序表 一.顺序表是什么 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储.在数组上完成数据的增删查改. 数组不就是一个现

  • java操作mongoDB查询的实例详解

    java操作mongo查询的实例详解 前言: MongoDB是一个基于分布式文件存储的数据库.由C++语言编写.旨在为WEB应用提供可扩展的高性能数据存储解决方案. MongoDB是一个介于关系数据库和非关系数据库之间的产品,是非关系数据库当中功能最丰富,最像关系数据库的.他支持的数据结构非常松散,是类似json的bson格式,因此可以存储比较复杂的数据类型.Mongo最大的特点是他支持的查询语言非常强大,其语法有点类似于面向对象的查询语言,几乎可以实现类似关系数据库单表查询的绝大部分功能,而且

  • Java中正则表达式的使用和详解(下)

    在上篇给大家介绍了Java中正则表达式的使用和详解(上),具体内容如下所示: 1.常用正则表达式 规则 正则表达式语法   一个或多个汉字 ^[\u0391-\uFFE5]+$  邮政编码 ^[1-9]\d{5}$ QQ号码 ^[1-9]\d{4,10}$  邮箱 ^[a-zA-Z_]{1,}[0-9]{0,}@(([a-zA-z0-9]-*){1,}\.){1,3}[a-zA-z\-]{1,}$  用户名(字母开头 + 数字/字母/下划线) ^[A-Za-z][A-Za-z1-9_-]+$ 手

  • Java Web请求与响应实例详解

    Servlet最主要作用就是处理客户端请求并作出回应,为此,针对每次请求,Web容器在调用service()之前都会创建两个对象,分别是HttpServletRequest和HttpServletResponse.其中HttpServletRequest封装HTTP请求消息,HttpServletResponse封装HTTP响应消息.需要注意的是,Web服务器运行过程中,每个Servlet都会只创建一个实例对象,不过每次请求都会调用Servlet实例的service(ServletRequest

  • Java连接操作Oracle数据库代码详解

    废话不多说了,直接给大家贴关键代码了,具体代码如下所示: package com.sp.test; import java.sql.*; import java.util.*; public class Text_lianxi extends Thread { public void run() { try { yunxing(); Thread.sleep(10000); } catch (InterruptedException e) { // TODO 自动生成的 catch 块 e.pr

  • Java日志框架之logback使用详解

    为什么使用logback 记得前几年工作的时候,公司使用的日志框架还是log4j,大约从16年中到现在,不管是我参与的别人已经搭建好的项目还是我自己主导的项目,日志框架基本都换成了logback,总结一下,logback大约有以下的一些优点: 内核重写.测试充分.初始化内存加载更小,这一切让logback性能和log4j相比有诸多倍的提升 logback非常自然地直接实现了slf4j,这个严格来说算不上优点,只是这样,再理解slf4j的前提下会很容易理解logback,也同时很容易用其他日志框架

  • Java数据结构之平衡二叉树的实现详解

    目录 定义 结点结构 查找算法 插入算法 LL 型 RR 型 LR 型 RL 型 插入方法 删除算法 概述 实例分析 代码 完整代码 定义 动机:二叉查找树的操作实践复杂度由树高度决定,所以希望控制树高,左右子树尽可能平衡. 平衡二叉树(AVL树):称一棵二叉查找树为高度平衡树,当且仅当或由单一外结点组成,或由两个子树形 Ta 和 Tb 组成,并且满足: |h(Ta) - h(Tb)| <= 1,其中 h(T) 表示树 T 的高度 Ta 和 Tb 都是高度平衡树 即:每个结点的左子树和右子树的高

  • Java中JDBC的使用教程详解

    目录 概念 快速入门 步骤 代码实现 详解各个对象 DriverManager:驱动管理对象 Connection:数据库连接对象 Statement:执行sql的对象 ResultSet:结果集对象,封装查询结果 PreparedStatement:执行sql的对象 抽取JDBC工具类 : JDBCUtils 分析 代码实现 练习 JDBC控制事务 事务 操作 使用Connection对象来管理事务 代码 概念 Java DataBase Connectivity  Java 数据库连接, J

  • Java源码解析之TypeVariable详解

    TypeVariable,类型变量,描述类型,表示泛指任意或相关一类类型,也可以说狭义上的泛型(泛指某一类类型),一般用大写字母作为变量,比如K.V.E等. 源码 public interface TypeVariable<D extends GenericDeclaration> extends Type { //获得泛型的上限,若未明确声明上边界则默认为Object Type[] getBounds(); //获取声明该类型变量实体(即获得类.方法或构造器名) D getGenericDe

随机推荐