详解Java二叉排序树

什么是二叉排序树

二叉排序树是一种特殊的二叉树，它满足如下条件：

1. 左子树上所有节点的值均小于它的根节点的值。
2. 右子树上所有节点的值均大于它的根节点的值。
3. 左、右子树也分别为二叉排序树。

二叉排序树可以使用它的特殊性质进行快速查找、插入、删除等操作。

实现二叉排序树

实现二叉排序树需要定义二叉树节点类以及二叉排序树类：

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

class BST {
    private Node root;
    public BST() {
        root = null;
    }
    // insert a value into the tree
    public void insert(int val) {
        root = insert(root, val);
    }
    private Node insert(Node node, int val) {
        if (node == null) {
            node = new Node(val);
            return node;
        }
        if (val < node.val) {
            node.left = insert(node.left, val);
        } else if (val > node.val) {
            node.right = insert(node.right, val);
        }
        return node;
    }
    // search a value from the tree
    public boolean search(int val) {
        return search(root, val);
    }
    private boolean search(Node node, int val) {
        if (node == null) {
            return false;
        }
        if (val == node.val) {
            return true;
        } else if (val < node.val) {
            return search(node.left, val);
        } else {
            return search(node.right, val);
        }
    }
    // delete a value from the tree
    public void delete(int val) {
        root = delete(root, val);
    }
    private Node delete(Node node, int val) {
        if (node == null) {
            return null;
        }
        if (val < node.val) {
            node.left = delete(node.left, val);
        } else if (val > node.val) {
            node.right = delete(node.right, val);
        } else {
            if (node.left == null) {
                return node.right;
            }
            if (node.right == null) {
                return node.left;
            }
            Node minNode = findMin(node.right);
            node.val = minNode.val;
            node.right = delete(node.right, minNode.val);
        }
        return node;
    }
    private Node findMin(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

示例说明

示例一：插入、查找、删除操作

BST bst = new BST();
bst.insert(5);
bst.insert(3);
bst.insert(7);
System.out.println(bst.search(3)); // true
System.out.println(bst.search(4)); // false
bst.delete(5);
System.out.println(bst.search(5)); // false

运行结果：

true
false
false

示例二：使用二叉排序树实现顺序输出

利用二叉排序树的特性，可以将一组数据按顺序插入二叉排序树，然后中序遍历输出，即可实现顺序输出。

public static void printSorted(int[] arr) {
    BST bst = new BST();
    for (int val : arr) {
        bst.insert(val);
    }
    printSorted(bst.root);
}
private static void printSorted(Node node) {
    if (node == null) {
        return;
    }
    printSorted(node.left);
    System.out.println(node.val);
    printSorted(node.right);
}

调用示例：

int[] arr = {5, 3, 7, 2, 4, 6, 8};
printSorted(arr);

运行结果：

2
3
4
5
6
7
8