# 二分搜索树BinarySearchTree

阅读量 loading

# 一、定义

# 1、二叉树

二叉树是一种树型结构，是由一个个节点组成，每一个节点除了保存元素值本身之外，还存有一个左子节点和右子节点。

每一个节点最多有两个孩子，每个节点最多有一个父亲，根节点没有父亲节点。
二叉树具有天然的递归结构，每个节点的左子树和右子树也都是一个二叉树。
二叉树不一定都是满的，即不一定每个节点都具有左子节点和右子节点。
只有一个根节点或者只有一个空也是二叉树。

# 2、二分搜索树 BinarySearchTree

二分搜索树也是二叉树。

每个节点的值大于其左子树的所有节点的值。
每个节点的值小于其右子树的所有节点的值。
每一颗子树也都是二分搜索树。
存储的元素必须具有可比较性。

# 二、实现

# 1、基础实现

public class BinarySearchTree<E extends Comparable<E>> {

    private Node root;
    private int size;

    public BinarySearchTree() {
        root = null;
        size = 0;
    }

    public int getSize() {
        return size;
    }

    private class Node {
        private E e;
        private Node left;
        private Node right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

因为二分搜索树里面的元素都必须具有可比性，所以泛型中的类型需要实现 Comparable 接口。

# 2、添加

    /**
     * 添加元素
     *
     * @param e
     */
    public void add(E e) {
        root = add(root, e);
    }

    /**
     * 向以 node 为节点为根节点的二分搜索树中插入元素 e
     *
     * @param node 插入新节点后二分搜索树的跟
     * @param e
     * @return
     */
    private Node add(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        }

        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
        }

        return node;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 3、查找

    /**
     * 二分搜索树中是否包含元素 e
     *
     * @param e
     * @return
     */
    public boolean contains(E e) {
        return contains(root, e);
    }

    /**
     * 以 node 为根的节点是否包含元素 e
     *
     * @param node
     * @param e
     * @return
     */
    private boolean contains(Node node, E e) {
        if (node == null) {
            return false;
        }

        if (e.compareTo(node.e) < 0) {
            return contains(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            return contains(node.right, e);
        } else {
            return true;
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 4、遍历

# (1) 前序遍历

    /**
     * 前序遍历
     */
    public void preOrder() {
        preOrder(root);
    }

    /**
     * 以节点 node 为根节点进行前序遍历
     *
     * @param node
     */
    private void preOrder(Node node) {
        if (node == null) {
            return;
        }

        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

为了方便查看输出，复写了 toString() 方法：

    @Override
    public String toString() {
        StringBuilder result = new StringBuilder();
        generateBinarySearchTreeString(root, 0, result);
        return result.toString();
    }

    /**
     * 生成以 node 为根节点，深度为 depth 的描述二叉树的字符串
     *
     * @param node
     * @param depth
     * @param result
     */
    private void generateBinarySearchTreeString(Node node, int depth, StringBuilder result) {
        if (node == null) {
            result.append(generateDepthString(depth)).append("null\n");
            return;
        }

        result.append(generateDepthString(depth)).append(node.e).append("\n");
        generateBinarySearchTreeString(node.left, depth + 1, result);
        generateBinarySearchTreeString(node.right, depth + 1, result);
    }

    /**
     * 生成深度为 depth 的层级符号
     *
     * @param depth
     */
    private String generateDepthString(int depth) {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            result.append("--");
        }
        return result.toString();
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

测试：

    public static void main(String[] args) {
        BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
        int[] nums = {5, 3, 6, 8, 4, 2};

        for (int i = 0; i < nums.length; i++) {
            binarySearchTree.add(nums[i]);
        }

        System.out.println("前序遍历：");
        binarySearchTree.preOrder();
        System.out.println();

        System.out.println(binarySearchTree);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14

运行结果：

前序遍历：
5
3
2
4
6
8

5
--3
----2
------null
------null
----4
------null
------null
--6
----null
----8
------null
------null

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# (2) 中序遍历

    /**
     * 中序遍历
     */
    public void inOrder() {
        inOrder(root);
    }

    /**
     * 以 node 节点为根节点进行中序遍历
     *
     * @param node
     */
    private void inOrder(Node node) {
        if (node == null) {
            return;
        }

        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

测试：

    public static void main(String[] args) {
        BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
        int[] nums = {5, 3, 6, 8, 4, 2};

        for (int i = 0; i < nums.length; i++) {
            binarySearchTree.add(nums[i]);
        }

        System.out.println("中序遍历：");
        binarySearchTree.inOrder();
    }

1
2
3
4
5
6
7
8
9
10
11

运行结果：

中序遍历：
2
3
4
5
6
8

1
2
3
4
5
6
7

# (3) 后序遍历

    /**
     * 后序遍历
     */
    public void postOrder() {
        postOrder(root);
    }

    /**
     * 以 node 节点为根节点进行后序遍历
     *
     * @param node
     */
    private void postOrder(Node node) {
        if (node == null) {
            return;
        }

        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

测试：

    public static void main(String[] args) {
        BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
        int[] nums = {5, 3, 6, 8, 4, 2};

        for (int i = 0; i < nums.length; i++) {
            binarySearchTree.add(nums[i]);
        }

        System.out.println("后序遍历：");
        binarySearchTree.postOrder();
    }

1
2
3
4
5
6
7
8
9
10
11

运行结果：

后序遍历：
2
4
3
8
6
5

1
2
3
4
5
6
7

# (4) 前序遍历（非递归）

    /**
     * 非递归前序遍历
     */
    public void preOrderNoRecursive() {
        Stack<Node> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node current = stack.pop();
            System.out.println(current.e);
            if (current.right != null) {
                stack.push(current.right);
            }
            if (current.left != null) {
                stack.push(current.left);
            }
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

测试：

    public static void main(String[] args) {
        BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
        int[] nums = {5, 3, 6, 8, 4, 2};

        for (int i = 0; i < nums.length; i++) {
            binarySearchTree.add(nums[i]);
        }

        System.out.println("前序遍历(非递归）：");
        binarySearchTree.preOrderNoRecursive();
    }

1
2
3
4
5
6
7
8
9
10
11

运行结果：

前序遍历(非递归）：
5
3
2
4
6
8

1
2
3
4
5
6
7

# (5) 层序遍历

层序遍历也叫广度优先遍历：

    /**
     * 层序遍历
     */
    public void levelOrder() {
        Queue<Node> stack = new LinkedList<>();
        stack.add(root);

        while (!stack.isEmpty()) {
            Node current = stack.remove();
            System.out.println(current.e);
            if (current.right != null) {
                stack.add(current.right);
            }
            if (current.left != null) {
                stack.add(current.left);
            }
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

层序遍历的意义：

更快的找到问题的解
常用于算法设计中 - 最短路径
图中的深度优先遍历和广度优先遍历

测试：

    public static void main(String[] args) {
        BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
        int[] nums = {5, 3, 6, 8, 4, 2};

        for (int i = 0; i < nums.length; i++) {
            binarySearchTree.add(nums[i]);
        }

        System.out.println("层序遍历：");
        binarySearchTree.levelOrder();
    }

1
2
3
4
5
6
7
8
9
10
11

运行结果：

层序遍历：
5
6
3
8
4
2

1
2
3
4
5
6
7

# 5、删除

# (1) 删除最小值


    /**
     * 寻找最小元素
     *
     * @return
     */
    public E minimum() {
        if (size == 0) {
            throw new IllegalArgumentException("Binary search tree is empty");
        }
        return minimum(root).e;
    }

    /**
     * 获取以 node 为根的最小值所在的节点
     *
     * @param node
     * @return
     */
    private Node minimum(Node node) {
        if (node.left == null) {
            return node;
        }

        return minimum(node.left);
    }

    /**
     * 删除最小值所在节点，返回最小值元素
     *
     * @return
     */
    public E removeMin() {
        E result = minimum();
        root = removeMin(root);
        return result;
    }

    /**
     * 删除以 node 为根的最小节点，返回删除后二分搜索树的跟
     *
     * @param node
     * @return
     */
    private Node removeMin(Node node) {
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }

        node.left = removeMin(node.left);
        return node;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

测试：

    public static void main(String[] args) {
        BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();

        int n = 1000;
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            binarySearchTree.add(random.nextInt(10000));
        }

        List<Integer> nums = new ArrayList<>();
        while (!binarySearchTree.isEmpty()) {
            nums.add(binarySearchTree.removeMin());
        }
        System.out.println(nums);
        for (int i = 1; i < nums.size(); i++) {
            if (nums.get(i - 1) > nums.get(i)) {
                throw new IllegalArgumentException("error");
            }
        }
        System.out.println("removeMin() test completed.");
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

向二分搜索树中插入1000个数字，然后以从小到大的顺序取出来，然后进行大小对比，如果对比正确就说明测试通过。

# (2) 删除最大值

    /**
     * 寻找最大元素
     *
     * @return
     */
    public E maximum() {
        if (size == 0) {
            throw new IllegalArgumentException("Binary search tree is empty");
        }
        return maximum(root).e;
    }

    /**
     * 获取以 node 为根的最大值所在的节点
     *
     * @param node
     * @return
     */
    private Node maximum(Node node) {
        if (node.right == null) {
            return node;
        }

        return maximum(node.right);
    }

    /**
     * 删除最大值所在节点，返回最大值元素
     *
     * @return
     */
    public E removeMax() {
        E result = maxmum();
        root = removeMax(root);
        return result;
    }

    /**
     * 删除以 node 为根的最大节点，返回删除后二分搜索树的跟
     *
     * @param node
     * @return
     */
    private Node removeMax(Node node) {
        if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }

        node.right = removeMax(node.right);
        return node;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

测试：

    public static void main(String[] args) {
        BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();

        int n = 1000;
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            binarySearchTree.add(random.nextInt(10000));
        }

        List<Integer> nums = new ArrayList<>();
        while (!binarySearchTree.isEmpty()) {
            nums.add(binarySearchTree.removeMax());
        }
        System.out.println(nums);
        for (int i = 1; i < nums.size(); i++) {
            if (nums.get(i - 1) < nums.get(i)) {
                throw new IllegalArgumentException("error");
            }
        }
        System.out.println("removeMax() test completed.");
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

向二分搜索树中插入1000个数字，然后以从大到小的顺序取出来，然后进行对比，如果对比正确就说明测试通过。

# (3) 删除任意节点


    /**
     * 删除元素为 e 的节点
     *
     * @param e
     */
    public void remove(E e) {
        root = remove(root, e);
    }

    /**
     * 删除掉以 node 为根的二分搜索树中值为 e 的节点，并返回删除后二分搜索树的根节点
     *
     * @param node
     * @param e
     * @return
     */
    private Node remove(Node node, E e) {
        if (node == null) {
            return null;
        }

        if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            return node;
        } else if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);
            return node;
        } else {
           ht = null;
                size--; // 待删除的节点左子树为空的情况
                                   if (node.left == null) {
                                       Node rightNode = node.right;
                                       node.rig
                return rightNode;
            }

            // 待删除的节点右子树为空的情况
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }

            // 待删除的节点左、右子树都不为空的情况
            // 删除待删除节点右子树中最小的节点，用这个节点顶替待删除的节点
            Node successor = minimum(node.right);
            successor.left = node.left;
            successor.right = removeMin(node.right);
            node.left = null;
            node.right = null;
            return successor;
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

这里实际上是通过寻找待删除节点的 后继节点 ，也就是待删除节点的右子树中最小的元素的节点来作为新节点的。其实也可以通过找待删除节点的 前驱节点 ，即待删除节点的左子树中最大元素的节点作为新节点。

这里值得注意的是第50行代码在进行 removeMin() 的时候，代码中是进行了 size-- 的操作，但实际上这时候这个节点还未删除，因为我们需要将这个节点作为新的根节点，所以这里是暂时多减了1，应当使用 size++ 加回来。但是最后删除掉节点后还需要再进行 size-- 的操作，也就是说给“扯平了”，所以这里就没有相关 size 的操作了。

# 6、floor和ceil

floor 是指获取比给定值小与等于的元素中最大的那个元素。

    /**
     * 查询不大于 e 的元素中最大元素
     *
     * @param e
     * @return
     */
    public E floor(E e) {
        if (size == 0 || minimum().compareTo(e) > 0) {
            return null;
        }

        return floor(root, e).e;
    }

    /**
     * 在以 node 为根节点的二分搜索树中查询不大于 e 的元素中最大元素
     *
     * @param node
     * @param e
     * @return
     */
    private Node floor(Node node, E e) {
        if (node == null) {
            return null;
        }

        // 如果该 node 的 e 和 e 相等，就是本身
        if (node.e.compareTo(e) == 0) {
            return node;
        }

        // 如果该 node 比 e 要大的话
        if (node.e.compareTo(e) > 0) {
            return floor(node.left, e);
        }

        // 如果 node 比 e 小，可能是，也能是不是，需要到 node 的右子树中查询
        Node tempNode = floor(node.right, e);
        // 如果能查询到就返回查询到的，否则就返回上级的 node
        if (tempNode != null) {
            return tempNode;
        }
        return node;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

测试：

    public static void main(String[] args) {
        BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
        int[] nums = {5, 3, 6, 8, 4, 2};

        for (int i = 0; i < nums.length; i++) {
            binarySearchTree.add(nums[i]);
        }

        System.out.println(binarySearchTree.floor(7));
    }

1
2
3
4
5
6
7
8
9
10

运行结果：

ceil 是指获取比给定值大与等于的元素中最小的那个元素。

    /**
     * 查询不小于 e 的元素中最小元素
     *
     * @param e
     * @return
     */
    public E ceil(E e) {
        if (size == 0 || maxmum().compareTo(e) < 0) {
            return null;
        }

        return ceil(root, e).e;
    }

    /**
     * 在以 node 为根节点的二分搜索树中查询不小于 e 的元素中最小元素
     *
     * @param node
     * @param e
     * @return
     */
    private Node ceil(Node node, E e) {
        if (node == null) {
            return null;
        }

        // 如果该 node 的 e 和 e 相等，就是本身
        if (node.e.compareTo(e) == 0) {
            return node;
        }

        // 如果该 node 比 e 要小的话，需要到右子树中查询更大点的
        if (node.e.compareTo(e) < 0) {
            return ceil(node.right, e);
        }

        // 如果 node 比 e 大，可能是，也能是不是，需要到 node 的左子树中查询
        Node tempNode = floor(node.left, e);
        // 如果能查询到就返回查询到的，否则就返回上级的 node
        if (tempNode != null) {
            return tempNode;
        }
        return node;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

测试：

    public static void main(String[] args) {
        BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
        int[] nums = {5, 3, 6, 8, 4, 2};

        for (int i = 0; i < nums.length; i++) {
            binarySearchTree.add(nums[i]);
        }

        System.out.println(binarySearchTree.ceil(7));
    }

1
2
3
4
5
6
7
8
9
10

运行结果：

# 7、rank和select

rank 是指获取给定元素在二分搜索树中排名。

select 是指根据排名获取二分搜索树中的元素。

这两个方法有兴趣的可以实现一下。

← 链表LinkedList 集合Set →