二分搜索树详解

原创

大发明家

发布于 2021-12-18 11:35:51

7650

文章被收录于专栏：技术博客文章技术博客文章

二分搜索树基础

在介绍二分搜索树之前我们先来看二叉树，二叉树是最基本的树形结构，二叉树由一个根节点和多个子节点组成，包括根节点在内的每个节点最多拥有左右两个子节点，俗称左孩子和右孩子。树和链表一样也是动态的数据结构：

image.png

二分搜索树在二叉树的基础上增加了一些规则：

image.png

我们先来编写二分搜索树节点的结构以及二分搜索树基础的属性和方法，代码如下：

/**

 * @author 01
 * @program Data-Structure
 * @description 二分搜索树-存储的数据需具有可比较性，所以泛型需继承Comparable接口
 * @create 2018-11-13 17:02
 * @since 1.0
 **/
public class BinarySearchTree<E extends Comparable<E>> {
    /**
     * 二分搜索树节点的结构
     */
    private class Node {
        E e;
        Node left;
        Node right;

        public Node() {

            this(null, null, null);

        public Node(E e) {

            this(e, null, null);

        public Node(E e, Node left, Node right) {

            this.e = e;

            this.left = left;

            this.right = right;

/**

     * 根节点
     */
    private Node root;

/**

     * 表示树里存储的元素个数
     */
    private int size;

/**

     * 获取树里的元素个数
     *
     * @return 元素个数
     */
    public int size() {
        return size;
    }

/**

     * 树是否为空
     *
     * @return 为空返回true，否则返回false
     */
    public boolean isEmpty() {
        return size == 0;
    }
}

向二分搜索树中添加元素

我们的二分搜索树不包含重复元素，如果想让树包含重复元素的话，也很简单，只需要改变定义为：左子树小于等于节点；或者右子树大于等于节点。

二分搜索树添加元素的非递归写法，和链表很像，只不过链表中不需要与节点进行比较，而树则需要比较后决定是添加到左子树还是右子树。

具体的实现代码如下：

/**

 * 向二分搜索树中添加一个新元素e
 *
 * @param e 新元素
 */
public void add(E e) {
    if (root == null) {
        // 根节点为空的处理
        root = new Node(e);
        size++;
    } else {
        add(root, e);
    }
}

/**

 * 向以node为根的二分搜索树中插入元素e，递归实现
 *
 * @param node
 * @param e
 */
private void add(Node node, E e) {
    // 递归的终止条件
    if (e.equals(node.e)) {
        // 不存储重复元素
        return;
    } else if (e.compareTo(node.e) < 0 && node.left == null) {
        // 元素e小于node节点的元素，并且node节点的左孩子为空，所以成为node节点的左孩子
        node.left = new Node(e);
        size++;
        return;
    } else if (e.compareTo(node.e) > 0 && node.right == null) {
        // 元素e大于node节点的元素，并且node节点的右孩子为空，所以成为node节点的右孩子
        node.right = new Node(e);
        size++;
        return;
    }

    if (e.compareTo(node.e) < 0) {

        // 元素e小于node节点的元素，往左子树走

        add(node.left, e);

    } else {

        // 元素e大于node节点的元素，往右子树走

        add(node.right, e);

改进添加操作：深入理解递归终止条件

上面所实现的往二叉树里添加元素的代码虽然是没问题的，但是还有优化的空间。一是在`add(E

e)方法中对根节点做了判空处理，与后面的方法在逻辑上有些不统一，实际上可以放在后面的方法中统一处理；二是add(Node node, E

e)`方法中递归的终止条件比较臃肿，可以简化。

优化后的实现代码如下：

/**

 * 向二分搜索树中添加一个新元素e
 *
 * @param e 新元素
 */
public void add2(E e) {
    root = add2(root, e);
}

/**

 * 向以node为根的二分搜索树中插入元素e，精简后的递归实现
 *
 * @param node
 * @param e
 * @return 返回插入新节点后二分搜索树的根节点
 */
private Node add2(Node node, E e) {
    // 递归的终止条件
    if (node == null) {
        // node为空时必然是可以插入新节点的
        size++;
        return new Node(e);
    }

    if (e.compareTo(node.e) < 0) {

        // 元素e小于node节点的元素，往左子树走

        node.left = add2(node.left, e);

    } else if (e.compareTo(node.e) > 0) {

        // 元素e大于node节点的元素，往右子树走

        node.right = add2(node.right, e);

    // 相等什么也不做

    return node;

修改递归的终止条件后，我们只需要在节点为空时，统一插入新节点，不需要再判断左右子节点是否为空。这样选择合适的终止条件后，多递归了一层但减少很多不必要的代码

二分搜索树的查询操作

有了前面的基础后，通过递归实现二分搜索树的查询操作就很简单了，只需要比较元素的大小，不断地递归就能找到指定的元素。代码如下：

/**

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

/**

 * 查看以node为根节点的二分搜索树中是否包含元素e，递归实现
 */
private boolean contains(Node node, E e) {
    if (node == null) {
        return false;
    }

    if (e.compareTo(node.e) == 0) {

        return true;

    } else if (e.compareTo(node.e) < 0) {

        // 找左子树

        return contains(node.left, e);

    // 找右子树

    return contains(node.right, e);

二分搜索树的前序遍历

什么是遍历操作：

遍历操作就是把所有节点都访问一遍，使得可以对所有节点元素进行操作。在线性结构下，遍历是极其容易的，一个循环就解决了。但是在树结构下就稍微有些麻烦了，因为对于树的遍历操作，两棵子树都要顾及

二叉树的遍历方式主要有这么几种：前序遍历、中序遍历、后序遍历以及层序遍历。本小节将要演示的是前序遍历，所谓前序遍历就是先遍历根节点，然后再遍历左子树和右子树。前序遍历是最自然、最常用的遍历方式。

前序遍历使用递归实现起来非常的简单，代码如下：

/**

 * 二分搜索树的前序遍历
 */
public void preOrder() {
    preOrder(root);
}

/**

 * 前序遍历以node为根的二分搜索树，递归实现
 */
private void preOrder(Node node) {
    if (node == null) {
        return;
    }

    // 先遍历根节点

    System.out.println(node.e);

    // 然后遍历左子树和右子树

    preOrder(node.left);

    preOrder(node.right);

二分搜索树的中序遍历和后序遍历

了解了前序遍历后，中序遍历和后序遍历就很简单了，无非就是换了个顺序。其中中序遍历就是先遍历左子树，然后遍历根节点，再遍历右子树。所以中序遍历的这个“中序”就体现在了根节点是在左右子树的中间进行遍历的。具体的实现代码如下：

/**

 * 二分搜索树的中序遍历
 */
public void inOrder() {
    inOrder(root);
}

/**

 * 中序遍历以node为根的二分搜索树，递归实现
 */
private void inOrder(Node node) {
    if (node == null) {
        return;
    }

    // 先遍历左子树

    inOrder(node.left);

    // 然后遍历根节点

    System.out.println(node.e);

    // 最后遍历右子树

    inOrder(node.right);

二分搜索树的中序遍历的特性是可以按照元素从小到大的顺序访问节点，将遍历过程输出就可以看到是有序的

同样的，后序遍历也是换了个顺序，是先遍历左子树，然后遍历右子树，再遍历根节点。具体的实现代码如下：

/**

 * 二分搜索树的后序遍历
 */
public void postOrder() {
    postOrder(root);
}

/**

 * 后序遍历以node为根的二分搜索树，递归实现
 */
private void postOrder(Node node) {
    if (node == null) {
        return;
    }

    // 先遍历左子树

    postOrder(node.left);

    // 然后遍历右子树

    postOrder(node.right);

    // 最后遍历根节点

    System.out.println(node.e);

后序遍历通常用于需要先处理左右子树，最后再处理根节点的场景，例如为二分搜索树释放内存（C++）

二分搜索树前序遍历的非递归实现

虽然使用递归实现对树的遍历会比较简单，但通常在实际开发中并不会太多的去使用递归，一是怕数据量大时递归深度太深导致栈溢出，二是为了减少递归函数调用的开销。中序遍历和后序遍历的非递归实现，实际应用不广，所以本小节主要演示一下前序遍历的非递归实现。

前序遍历的非递归实现思路有好几种，这里主要介绍一种递归算法转非递归实现的比较通用的思路。理解这种思路后我们也可以将其应用到其他的递归转非递归实现的场景上，这种方法就是自己用额外的容器模拟一下系统栈。具体的代码实现如下：

/**

 * 二分搜索树的非递归前序遍历实现
 */
public void preOrderNR() {
    // 使用 java.util.Stack 来模拟系统栈
    Stack<Node> stack = new Stack<>();
    // 前序遍历所以先将根节点压入栈
    stack.push(root);
    while (!stack.isEmpty()) {
        // 将当前要访问的节点出栈
        Node cur = stack.pop();
        System.out.println(cur.e);

        if (cur.right != null) {

            // 由于栈的特性是后入先出，所以这里是右子树先入栈

            stack.push(cur.right);

        if (cur.left != null) {

            stack.push(cur.left);

以这样一颗树为例，简单描述下以上代码的执行过程：

image.png

首先根节点入栈
进入循环，栈顶元素出栈，输出28
当前出栈元素的右节点不为空，将右节点30压入栈中
当前出栈元素的左节点不为空，将左节点16压入栈中
此时栈不为空，继续循环，栈顶元素出栈，输出16（后进先出）
当前出栈元素的右节点不为空，将右节点22压入栈中
当前出栈元素的左节点不为空，将左节点13压入栈中
继续循环，栈顶元素出栈，输出13
当前出栈元素的右节点为空，什么都不做
当前出栈元素的左节点为空，什么都不做
继续循环，栈顶元素出栈，输出22
重复第9、10步
继续循环，栈顶元素出栈，输出30
当前出栈元素的右节点不为空，将右节点42压入栈中
当前出栈元素的左节点不为空，将左节点29压入栈中
继续循环，栈顶元素出栈，输出29
重复第9、10步
继续循环，栈顶元素出栈，输出42
重复第9、10步
此时栈中没有元素了，为空，跳出循环
最终的输出为：28 16 13 22 30 29 42

二分搜索树的层序遍历

了解了前中后序遍历，接下来我们看看二分搜索树的层序遍历。所谓层序遍历就是按照树的层级自根节点开始从上往下遍历，通常根节点所在的层级称为第0层或第1层，我这里习惯称之为第1层。如下图所示：

image.png

当遍历第1层时，访问到的是28这个根节点；遍历第2层时，访问到的是16以及30这个两个节点；遍历第3层时，则访问到的是13、22、29及42这四个节点

可以看出层序遍历与前中后序遍历不太一样，前中后序遍历都是先将其中一颗子树遍历到底，然后再返回来遍历另一颗子树，其实这也就是所谓的深度优先遍历，而层序遍历也就是所谓的广度优先遍历了。

通常层序遍历会使用非递归的实现，并且会使用一个队列容器作为辅助，所以代码写起来与之前的非递归实现前序遍历非常类似，只不过容器由栈换成了队列。具体的代码实现如下：

/**

 * 二分搜索树的层序遍历实现
 */
public void levelOrder() {
    Queue<Node> queue = new LinkedList<>();
    // 根节点入队
    queue.add(root);
    while (!queue.isEmpty()) {
        // 将当前要访问的节点出队
        Node cur = queue.remove();
        System.out.println(cur.e);

        // 左右节点入队

        if (cur.left != null) {

            queue.add(cur.left);

        if (cur.right != null) {

            queue.add(cur.right);

以上面的那棵树为例，我们也来分析下层序遍历代码的执行过程：

首先根节点入队
进入循环，队头元素出队，输出28
当前出队元素的左节点不为空，将左节点16入队
当前出队元素的右节点不为空，将右节点30入队
此时队列不为空，继续循环，队头元素出队，输出16（先进先出）
当前出队元素的左节点不为空，将左节点13入队
当前出队元素的右节点不为空，将右节点22入队
继续循环，队头元素出队，输出30
当前出队元素的左节点不为空，将左节点29入队
当前出队元素的右节点不为空，将右节点42入队
继续循环，队头元素出队，输出13
当前出队元素的左节点为空，什么都不做
当前出队元素的右节点为空，什么都不做
继续循环，队头元素出队，输出22
重复第12、13步
继续循环，队头元素出队，输出29
重复第12、13步
继续循环，队头元素出队，输出42
重复第12、13步
此时栈中没有元素了，为空，跳出循环
最终的输出为：28 16 30 13 22 29 42

广度优先遍历的意义：

更快的找到问题的解
常用于算法设计中：最短路径

删除二分搜索树的最大元素和最小元素

二分搜索树的删除操作是相对比较复杂的，所以我们先来解决一个相对简单的任务，就是删除二分搜索树中的最大元素和最小元素。由于二分搜索树的特性，其最小值就是最左边的那个节点，而最大元素则是最右边的那个节点。

以下面这棵二分搜索树为例，看其最左和最右的两个节点，就能知道最小元素是13，最大元素是42：

image.png

再来看一种情况，以下这棵二分搜索树，往最左边走只能走到16这个节点，往最右边走只能走到30这个节点，所以最大最小元素不一定会是叶子节点：

image.png

在这种情况下，删除最大最小元素时，由于还有子树，所以需要将其子树挂载到被删除的节点上

我们先来看看如何找到二分搜索树的最大元素和最小元素。代码如下：

/**

 * 获取二分搜索树的最小元素
 */
public E minimum() {
    if (size == 0) {
        throw new IllegalArgumentException("BST is empty!");
    }

    return minimum(root).e;

/**

 * 返回以node为根的二分搜索树的最小元素所在节点
 */
private Node minimum(Node node) {
    if (node.left == null) {
        return node;
    }

    return minimum(node.left);

/**

 * 获取二分搜索树的最大元素
 */
public E maximum() {
    if (size == 0) {
        throw new IllegalArgumentException("BST is empty!");
    }

    return maximum(root).e;

/**

 * 返回以node为根的二分搜索树的最大元素所在节点
 */
private Node maximum(Node node) {
    if (node.right == null) {
        return node;
    }

    return maximum(node.right);

然后再来实现删除操作，代码如下：

/**

 * 删除二分搜索树中的最大元素所在节点，并返回该元素
 */
public E removeMax() {
    E ret = maximum();
    root = removeMax(root);
    return ret;
}

/**

 * 删除以node为根的二分搜索树中的最大节点
 * 返回删除节点后新的二分搜索树的根
 */
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;

/**

 * 删除二分搜索树中的最小元素所在节点，并返回该元素
 */
public E removeMin() {
    E ret = minimum();
    root = removeMin(root);
    return ret;
}

/**

 * 删除以node为根的二分搜索树中的最小节点
 * 返回删除节点后新的二分搜索树的根
 */
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;

删除二分搜索树的任意元素

有了上面的基础后，就应该对实现删除二分搜索树的任意元素有一定的思路了。首先，我们来看看在实现过程中会遇到的一些情况，第一种情况就是要删除的目标节点只有一个左子树，例如删除下图中的58：

在这种情况下，只需要将左子树挂到被删除的目标节点上即可，与删除最大元素的基本逻辑类似

第二种情况与第一种情况相反，就是要删除的目标节点只有一个右子树：

同样的，把右子树挂到被删除的目标节点上即可，与删除最小元素的基本逻辑类似

第三种情况是要删除的目标节点是一个叶子节点，这种情况直接复用以上任意一种情况的处理逻辑即可，因为我们也可以将叶子节点视为有左子树或右子树，只不过为空而已。

比较复杂的是第四种情况，也就是要删除的目标节点有左右两个子节点，如下图所示：

具体的实现代码如下：

/**

 * 从二分搜索树中删除元素为e的节点
 */
public void remove(E e) {
    root = remove(root, e);
}

/**

 * 删除以node为根的二分搜索树中值为e的节点，递归实现
 * 返回删除节点后新的二分搜索树的根
 */
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;

    // 找到了要删除的节点

    // 待删除的节点左子树为空的情况

    if (node.left == null) {

        // 如果有右子树，需要将其挂到被删除的节点上

        Node rightNode = node.right;

        node.right = null;

        size--;

        return rightNode;

    // 待删除的节点右子树为空的情况

    if (node.right == null) {

        // 如果有左子树，需要将其挂到被删除的节点上

        Node leftNode = node.left;

        node.left = null;

        size--;

        return leftNode;

    // 待删除的节点左右子树均不为空的情况

    // 找到比待删除节点大的最小节点，即待删除节点右子树的最小节点

    Node successor = minimum(node.right);

    // 用这个节点替换待删除节点的位置

    // 由于removeMin里已经维护过一次size了，所以这里就不需要维护一次了

    successor.right = removeMin(node.right);

    successor.left = node.left;

    return successor;

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法