Java 实现二叉排序树(BST)

简介: Java 实现二叉排序树(BST)

介绍


二叉排序树(Binary Search Tree,简称BST)是一种特殊的二叉树,其中每个节点的值都大于其左子树的任意节点值,而小于其右子树的任意节点值。


它具有以下特点:


  1. 左子树的值小于根节点的值,右子树的值大于根节点的值;
  2. 左子树和右子树也是二叉排序树;
  3. 二叉排序树的中序遍历结果是一个有序序列。


二叉排序树的应用非常广泛,以下是一些示例:


  • 查找操作:由于二叉排序树的特性,可以通过比较节点的值快速进行查找操作。平均时间复杂度为O(log n)。
  • 插入操作:将一个新节点插入到二叉排序树的合适位置,保持树的有序性。平均时间复杂度为O(log n)。
  • 删除操作:删除二叉排序树中的某个节点,需要保持树的有序性。平均时间复杂度为O(log n)。
  • 排序操作:利用二叉排序树的中序遍历结果是有序的特点,可以对一组数据进行排序。
  • 范围查询:通过在二叉排序树上进行中序遍历,可以方便地获取某个范围内的节点。
  • 数据统计:二叉排序树可用于统计某个节点的左子树节点数或右子树节点数,也可以统计整个树的节点数。


实现


先定义一个节点


/**
 * @description: 节点
 * @author: Snow
 * @date: 2024/1/22
 * **************************************************
 * 修改记录(时间--修改人--修改说明):
 */
public class Node {

    int value;

    Node left;

    Node right;

    public Node(int value) {
        this.value = value;
    }

    /** 添加节点 */
    public void add(Node root, Node node){
        if( node.value <= root.value ){
            if( root.left == null ){
                root.left = node;
                return;
            }else{
                add(root.left, node);
            }
        }else{
            if( root.right == null ){
                root.right = node;
                return;
            }else{
                add(root.right, node);
            }
        }
    }

    /** 中序遍历 */
    public void inOrder(Node root){
        if( root.left != null ){
            inOrder( root.left );
        }

        System.out.print(root.value + " ");

        if( root.right != null ){
            inOrder( root.right );
        }
    }

}


/**
 * @description: 二叉排序树
 *  对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当
 *  前节点的值小,右子节点的值比当前节点的值大。
 * @author: Snow
 * @date: 2024/1/22
 * **************************************************
 * 修改记录(时间--修改人--修改说明):
 */
public class BinarySortTree {

    //  根节点
    private Node root;

    /** 添加节点 */
    public void add(Node node){
        if( node == null ){
            return;
        }
        if( root == null ){
            root = node;
            return;
        }
        root.add(root, node);
    }

    /** 中序遍历 */
    public void inOrder(){
        if( root == null ){
            return;
        }
        root.inOrder(root);
    }
}


测试

public class BinarySortTreeTest {

    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9};
        BinarySortTree binarySortTree = new BinarySortTree();
        for (int i : arr) {
            binarySortTree.add(new Node(i));
        }

        binarySortTree.inOrder();
    }
}


总结


需要注意的是,二叉排序树对于具有相同值的节点处理会有一定问题,因为它要求每个节点的值都不相同。因此,在实际应用中,可以针对这个问题进行优化或改进,如在节点上增加一个计数器,来记录具有相同值的节点个数。

相关文章
|
10天前
|
C++ Python Java
Java每日一练(20230503) 外观数列、有序数组转BST、翻转字符串里的单词
Java每日一练(20230503) 外观数列、有序数组转BST、翻转字符串里的单词
38 0
Java每日一练(20230503) 外观数列、有序数组转BST、翻转字符串里的单词
|
10天前
|
Java Go 人工智能
Java每日一练(20230502) BST公共祖先、随机分组、K个一组翻转链表
Java每日一练(20230502) BST公共祖先、随机分组、K个一组翻转链表
27 0
Java每日一练(20230502) BST公共祖先、随机分组、K个一组翻转链表
|
10月前
|
Java C语言
面试整理 - 二叉排序树 c语言 及java 例子
面试整理 - 二叉排序树 c语言 及java 例子
|
10月前
|
Java
二叉搜索树(二叉排序树)—Java(下)
二叉搜索树(二叉排序树)—Java(下)
|
10月前
|
Java
二叉搜索树(二叉排序树)—Java(上)
二叉搜索树(二叉排序树)—Java(上)
|
11月前
|
算法 Java
Java数据结构与算法分析(八)二叉查找树(BST)
二叉查找树又叫二叉排序树(Binary Sort Tree),或叫二叉搜索树,简称BST。BST是一种节点值之间有次序的二叉树。
62 0
|
算法 Java
编写算法求给定结点在二叉排序树中所在的层数(Java语言)
编写算法求给定结点在二叉排序树中所在的层数(Java语言)
61 0
|
Java
二叉排序树的查找性能(Java语言)
二叉排序树的查找性能(Java语言)
73 0
|
算法 Java
Java开发 - 树(二叉树,二叉排序树,红黑树)(三)
Java开发 - 树(二叉树,二叉排序树,红黑树)
84 0
 Java开发 - 树(二叉树,二叉排序树,红黑树)(三)
|
Java
Java开发 - 树(二叉树,二叉排序树,红黑树)(二)
Java开发 - 树(二叉树,二叉排序树,红黑树)
76 0
 Java开发 - 树(二叉树,二叉排序树,红黑树)(二)