java-二叉查找树（BST）算法的示例代码分享

二叉查找树（Binary Search Tree）是一种能将链表插入的灵活性和有序数组查找的高效性结合起来的算法。下面是实现BST各种方法的干货纯代码。

二叉查找树（BST）定义

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

1. 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值

2. 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值

3. 左、右子树也分别为二叉排序树

基本结点实现

public class BST<K extends Comparable<K>, V> {

    private Node root;

    private class Node {

        private K key;
        private V value;
        private Node left;
        private Node right;
        private int N;

        public Node(K key, V value, int N) {
            this.key = key;
            this.value = value;
            this.N = N;
        }
    }

    public int size() {
        return size(root);
    }

    private int size(Node x) {
        if (x == null)
            return 0;
        else
            return x.N;
    }
}

查找键获取值——get

public V get(K key) {
    return get(root, key);
}

private V get(Node root, K key) {

    if (root == null)
        return null;

    int comp = key.compareTo(root.key);

    if (comp == 0)
        return root.value;
    else if (comp < 0)
        return get(root.left, key);
    else
        return get(root.right, key);

}

修改值/插入新值——put

  public void put(K key, V value) {
        root = put(root, key, value);
    }

    private Node put(Node root, K key, V value) {

        if (root == null)
            return new Node(key, value, 1);

        int comp = key.compareTo(root.key);
        if (comp == 0)
            root.value = value;
        else if (comp < 0)
            root.left = put(root.left, key, value);
        else
            root.right = put(root.right, key, value);

        root.N = size(root.left) + size(root.right) + 1;

        return root;
    }

最大值/最小值——min/max

  public K min() {
        return min(root).key;
    }

    private Node min(Node root) {

        if (root.left == null)
            return root;

        return min(root.left);

    }

    public K max() {
        return max(root).key;
    }

    private Node max(Node root2) {

        if (root.right == null)
            return root;

        return max(root.right);

    }

向上/向下取整——floor/ceiling

  public K floor(K key) {
        Node x = floor(root, key);
        if (x == null)
            return null;
        return x.key;
    }

    private Node floor(Node root, K key) {

        if (root == null)
            return null;

        int comp = key.compareTo(root.key);

        if (comp < 0)
            return floor(root.left, key);
        else if (comp > 0 && root.right != null
                && key.compareTo(min(root.right).key) >= 0)
            return floor(root.right, key);
        else
            return root;

    }

    public K ceiling(K key) {
        Node x = ceiling(root, key);
        if (x == null)
            return null;
        return x.key;
    }

    private Node ceiling(Node root, K key) {

        if (root == null)
            return null;

        int comp = key.compareTo(root.key);

        if (comp > 0)
            return ceiling(root.right, key);
        else if (comp < 0 && root.left != null
                && key.compareTo(max(root.left).key) >= 0)
            return ceiling(root.left, key);
        else
            return root;

    }

选择——select

  public K select(int k) {
        //找出BST中序号为k的键
        return select(root, k);
    }

    private K select(Node root, int k) {

        if (root == null)
            return null;

        int comp = k - size(root.left);

        if (comp < 0)
            return select(root.left, k);
        else if (comp > 0)
            return select(root.right, k - (size(root.left) + 1));
        else
            return root.key;

    }

排名——rank

  public int rank(K key) {
        //找出BST中键为key的序号是多少
        return rank(root, key);
    }

    private int rank(Node root, K key) {

        if (root == null)
            return 0;

        int comp = key.compareTo(root.key);

        if (comp == 0)
            return size(root.left);
        else if (comp < 0)
            return rank(root.left, key);
        else
            return 1 + size(root.left) + rank(root.right, key);

    }

删除最小/最大键——deleteMin/deleteMax

  public void deleteMin() {
        root = deleteMin(root);
    }

    private Node deleteMin(Node root) {

        if (root.left == null)
            return root.right;

        root.left = deleteMin(root.left);
        root.N = size(root.left) + size(root.right) + 1;
        return root;

    }

    public void deleteMax() {
        root = deleteMax(root);
    }

    private Node deleteMax(Node root) {

        if (root.right == null)
            return root.left;

        root.right = deleteMax(root.right);
        root.N = size(root.left) + size(root.right) + 1;
        return root;

    }

删除任意键——delete

  public void delete(K key) {
        root = delete(root, key);
    }

    private Node delete(Node root, K key) {

        if (root == null)
            return null;

        int comp = key.compareTo(root.key);

        if (comp == 0) {

            if (root.right == null)
                return root = root.left;
            if (root.left == null)
                return root = root.right;

            Node t = root;
            root = min(t.right);

            root.left = t.left;
            root.right = deleteMin(t.right);

        } else if (comp < 0)
            root.left = delete(root.left, key);
        else
            root.right = delete(root.right, key);

        root.N = size(root.left) + size(root.right) + 1;
        return root;

    }

中序打印树——print

  public void print() {
        print(root);
    }

    private void print(Node root) {

        if (root == null)
            return;
        print(root.left);
        System.out.println(root.key);
        print(root.right);

    }

以上是java-二叉查找树（BST）算法的示例代码分享的详细内容。更多信息请关注PHP中文网其他相关文章！