当前位置:首页>Java>Java 高级教程>Java二叉搜索树数据结构和算法

Java二叉搜索树数据结构和算法

作者:githubofrico发布时间:2019-09-14 21:10:30地址:https://dwz.cn/AMenD9kw

二叉搜索树概念

什么是二叉搜索树

二叉搜索树又称之为二叉排序树,它不为空树时,它左子树上所有的元素都小于根节点的元素,而根节点右子树上所有的元素都大于根节点的元素。

二叉搜索树是一种综合效率比较好的一种数据结构,搜索、插入、删除的复杂度等于树高, 平均空间复杂度为O(n),时间复杂度为O(log n),最坏时间复杂度为O(n),(当插入的数列有序,导致二叉树退化为线性表),故一些其他的树,在二叉搜索树基础上进行改良的平衡树,如AVL树、红黑树等,可以使得树的高度总是得到平衡,从而使得最坏的情况下,时间复杂度也能达到O(log n)。

在没有二叉搜索树这种结构出现的时候,我们如果想对一个有序的序列,进行快速的检索,使用数组是可以做到的,但数组的弊端在于,如果我想向这个序列里面插入或者删除一个新的元素,使用数组就可能捉襟见肘了,而链表则对插入,删除非常友好,但检索性能比较低,故才出现了二叉搜索树这种结够,使得查询和更新能够达到不错的一个O(log n)性能权衡。

二叉搜索树的特点

(1)每个节点包含一个key,也称data的数据域

(2)左子树不为空的情况下,左子树的每个节点值都小于根节点的值,即:L < P

(3)右子树不为空的情况下,右子树的每个节点值都大于根节点的值,即:P < R

(4)节点的值不允许出现重复

(5)任意节点的左,右子树,均符合上面的规则

Java实现二叉搜索树

构建TreeNode节点

public class TreeNode {

    public int data;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int data){
        this.data = data;
    }

    @Override
    public String toString() {
        return "TreeNode [data=" + data + "]";
    }
}

构建BinarySearchTree核心数据结构

public class BinarySearchTree {

    private TreeNode root;

    /**
     * @description 根据已知序列构建二叉搜索树
     * @param input
     */
    public BinarySearchTree(int[] input) {
        createBinarySearchTree(input);
    }

    /**
     * @description 根据已知序列构建二叉搜索树
     * @param input
     */
    public void createBinarySearchTree(int[] input) {
        if (input != null) {
            for (int i = 0; i < input.length; i++) {
                root = insert(input[i], root);
            }
        }
    }
}

二叉搜索树的搜索算法,递归算法

/**
 * @param target 目标值
 * @param root 二叉搜索树的根结点
 * @return
 */
public TreeNode search(int target, TreeNode root) {
    TreeNode result = null;
    if (root != null) { // 递归终止条件
        if (target == root.data) { // 递归终止条件
            result = root;
            return result;
        } else if (target < root.data) { // 目标值小于根结点值,从左子树查找
            result = search(target, root.left);
        } else { // 目标值大于根结点值,从右子树查找
            result = search(target, root.right);
        }
    }
    return result;
}

二叉搜索树的插入操作

/**
 * @param target
 * @param node
 * @return
 */
public TreeNode insert(int target, TreeNode node) {
    if (search(target, node) == null) {
        if (node == null) {
            return new TreeNode(target);
        } else {
            if (target < node.data) {
                node.left = insert(target, node.left);
            } else {
                node.right = insert(target, node.right);
            }
        }
    }
    return node;
}

删除搜索二叉树的制定结点

/**
 * @description 删除搜索二叉树的制定结点
 * @param target
 * @param node
 * @return
 */
public TreeNode remove(int target, TreeNode node) {
    TreeNode tmp = null;
    if (node != null) {
        if (target < node.data) { // 从左子树删除
            node.left = remove(target, node.left);
        } else if (target > node.data) { // 从右子树删除
            node.right = remove(target, node.right);
        } else if (node.left != null && node.right != null) { // 找到待删除结点,且其左右子树不为空
            // 找到以待删除结点右子树的中序遍历第一个结点(最小结点)
            tmp = node.right;
            while (tmp.left != null) {
                tmp = tmp.left;
            }

            // 用最小结点补位待删除结点
            node.data = tmp.data;

            // 删除待删除结点右子树上补位结点
            node.right = remove(node.data, node.right);
        } else {
            if (node.left == null) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
    }
    return node;
}

中序遍历二叉搜索树,递归算法,升序排序

/**
 * @param root
 */
public void inOrder(TreeNode node) {
    if (node != null) {
        inOrder(node.left);
        System.out.print(root.data + " ");
        inOrder(node.right);
    }
}

打印二叉搜索树

/**
 * @param node
 */
public void printTree(TreeNode node) {
    if (node != null) {
        System.out.print(node.data);
        if (node.left != null || node.right != null) {
            System.out.print("(");
            printTree(node.left);
            System.out.print(",");
            printTree(node.right);
            System.out.print(")");
        }
    }
}

访问二叉搜索树的根结点

public TreeNode getRoot() {
    return root;
}

Java二叉搜索树测试代码

public class BinarySearchTreeTest {
    public static void main(String[] args) {
        int[] input = {53,78,65,17,87,9,81,45,23};
        BinarySearchTree tree = new BinarySearchTree(input);

        System.out.println("中序遍历二叉搜索树:");
        tree.inOrder(tree.getRoot());
        System.out.println();
        System.out.println("\n------------------------\n");
        System.out.println("打印二叉搜索树:");
        tree.printTree(tree.getRoot());
        System.out.println();
        System.out.println("\n------------------------\n");

        System.out.println("二叉搜索树搜索目标值:");
        System.out.println(tree.search(23, tree.getRoot()));
        System.out.println("\n------------------------\n");

        System.out.println("向二叉搜索树插入目标值:");
        tree.insert(10, tree.getRoot());
        tree.printTree(tree.getRoot());
        System.out.println();
        System.out.println("\n------------------------\n");

        System.out.println("向二叉搜索树删除目标值:");
        tree.remove(78, tree.getRoot());
        tree.printTree(tree.getRoot());
        System.out.println();
        System.out.println("\n------------------------\n");
    }
}