Java 实现二叉排序树（BST）

2024-04-24 17

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Java 实现二叉排序树（BST）

介绍

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

它具有以下特点：

左子树的值小于根节点的值，右子树的值大于根节点的值；
左子树和右子树也是二叉排序树；
二叉排序树的中序遍历结果是一个有序序列。

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

查找操作：由于二叉排序树的特性，可以通过比较节点的值快速进行查找操作。平均时间复杂度为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();
    }
}