算法 017：树：二叉搜索树(BST)

BST 的定义

二叉查找树（Binary Search Tree，又译二叉搜索树、二叉排序树）或者是一棵空树，或者是具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
任意节点的左、右子树也分别为二叉查找树；
没有键值相等的节点。

原文此处配有一棵 BST 示例（图片丢失，据文字与中序有序性重绘）：

flowchart TD
    n8((8)) --> n3((3))
    n8 --> n10((10))
    n3 --> n1((1))
    n3 --> n6((6))
    n10 --> n14((14))
    n6 --> n4((4))
    n6 --> n7((7))
    n14 --> n13((13))

动画效果可参考 Data Structure Visualizations 中的 BST。

在平衡状态下，BST 的查找、插入、删除均为 O(logn)；但插入顺序可能使树退化成斜树（链表），此时退化为 O(n)——这正是后续 AVL 树和红黑树要解决的问题：

操作	平均复杂度	最坏复杂度（退化为链表）
查找	O(logn)	O(n)
插入	O(logn)	O(n)
删除	O(logn)	O(n)

BST 的实现

节点

BSTree 是二叉树，它保存了二叉树的根节点 mRoot；mRoot 是 BSTNode 类型，而 BSTNode 是二叉查找树的节点，它是 BSTree 的内部类。BSTNode 包含二叉查找树的几个基本信息：

key——它是关键字，是用来对二叉查找树的节点进行排序的；
left——它指向当前节点的左孩子；
right——它指向当前节点的右孩子；
parent——它指向当前节点的父结点。

public class BSTree<T extends Comparable<T>> {

    private BSTNode<T> mRoot;    // 根结点

    public class BSTNode<T extends Comparable<T>> {
        T key;                // 关键字(键值)
        BSTNode<T> left;      // 左孩子
        BSTNode<T> right;     // 右孩子
        BSTNode<T> parent;    // 父结点

        public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
            this.key = key;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }
    }
    ......
}

遍历

这里讲解前序遍历、中序遍历、后序遍历 3 种方式。

前序遍历——若二叉树非空，则执行以下操作：

访问根结点；
先序遍历左子树；
先序遍历右子树。

private void preOrder(BSTNode<T> tree) {
    if(tree != null) {
        System.out.print(tree.key+" ");
        preOrder(tree.left);
        preOrder(tree.right);
    }
}

public void preOrder() {
    preOrder(mRoot);
}

中序遍历——若二叉树非空，则执行以下操作：

中序遍历左子树；
访问根结点；
中序遍历右子树。

private void inOrder(BSTNode<T> tree) {
    if(tree != null) {
        inOrder(tree.left);
        System.out.print(tree.key+" ");
        inOrder(tree.right);
    }
}

public void inOrder() {
    inOrder(mRoot);
}

后序遍历——若二叉树非空，则执行以下操作：

后序遍历左子树；
后序遍历右子树；
访问根结点。

private void postOrder(BSTNode<T> tree) {
    if(tree != null)
    {
        postOrder(tree.left);
        postOrder(tree.right);
        System.out.print(tree.key+" ");
    }
}

public void postOrder() {
    postOrder(mRoot);
}

对于上面的示例二叉树而言：

前序遍历结果：8 3 1 6 4 7 10 14 13
中序遍历结果：1 3 4 6 7 8 10 13 14
后序遍历结果：1 4 7 6 3 13 14 10 8

注意中序遍历结果恰好是有序的，这是 BST 的一个重要性质。

查找

递归版本的代码：

/*
 * (递归实现)查找"二叉树x"中键值为key的节点
 */
private BSTNode<T> search(BSTNode<T> x, T key) {
    if (x==null)
        return x;

    int cmp = key.compareTo(x.key);
    if (cmp < 0)
        return search(x.left, key);
    else if (cmp > 0)
        return search(x.right, key);
    else
        return x;
}

public BSTNode<T> search(T key) {
    return search(mRoot, key);
}

非递归版本的代码：

/*
 * (非递归实现)查找"二叉树x"中键值为key的节点
 */
private BSTNode<T> iterativeSearch(BSTNode<T> x, T key) {
    while (x!=null) {
        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            x = x.left;
        else if (cmp > 0)
            x = x.right;
        else
            return x;
    }

    return x;
}

public BSTNode<T> iterativeSearch(T key) {
    return iterativeSearch(mRoot, key);
}

最大值和最小值

查找最大结点：一路向右，返回 tree 为根结点的二叉树的最大结点：

private BSTNode<T> maximum(BSTNode<T> tree) {
    if (tree == null)
        return null;

    while(tree.right != null)
        tree = tree.right;
    return tree;
}

public T maximum() {
    BSTNode<T> p = maximum(mRoot);
    if (p != null)
        return p.key;

    return null;
}

查找最小结点：一路向左，返回 tree 为根结点的二叉树的最小结点：

private BSTNode<T> minimum(BSTNode<T> tree) {
    if (tree == null)
        return null;

    while(tree.left != null)
        tree = tree.left;
    return tree;
}

public T minimum() {
    BSTNode<T> p = minimum(mRoot);
    if (p != null)
        return p.key;

    return null;
}

前驱和后继

节点的前驱是该节点的左子树中的最大节点；节点的后继是该节点的右子树中的最小节点。

查找前驱节点——即查找”二叉树中数据值小于该结点”的”最大结点”：

public BSTNode<T> predecessor(BSTNode<T> x) {
    // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
    if (x.left != null)
        return maximum(x.left);

    // 如果x没有左孩子。则x有以下两种可能:
    // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
    // (02) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，
    //      找到的这个"最低的父结点"就是"x的前驱结点"。
    BSTNode<T> y = x.parent;
    while ((y!=null) && (x==y.left)) {
        x = y;
        y = y.parent;
    }

    return y;
}

查找后继节点——即查找”二叉树中数据值大于该结点”的”最小结点”：

public BSTNode<T> successor(BSTNode<T> x) {
    // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
    if (x.right != null)
        return minimum(x.right);

    // 如果x没有右孩子。则x有以下两种可能:
    // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
    // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，
    //      找到的这个"最低的父结点"就是"x的后继结点"。
    BSTNode<T> y = x.parent;
    while ((y!=null) && (x==y.right)) {
        x = y;
        y = y.parent;
    }

    return y;
}

插入

将结点插入到二叉树中：先像查找一样定位插入位置，再把新节点挂到父结点上：

/*
 * 将结点插入到二叉树中
 *
 * 参数说明:
 *     tree 二叉树的
 *     z 插入的结点
 */
private void insert(BSTree<T> bst, BSTNode<T> z) {
    int cmp;
    BSTNode<T> y = null;
    BSTNode<T> x = bst.mRoot;

    // 查找z的插入位置
    while (x != null) {
        y = x;
        cmp = z.key.compareTo(x.key);
        if (cmp < 0)
            x = x.left;
        else
            x = x.right;
    }

    z.parent = y;
    if (y==null)
        bst.mRoot = z;
    else {
        cmp = z.key.compareTo(y.key);
        if (cmp < 0)
            y.left = z;
        else
            y.right = z;
    }
}

/*
 * 新建结点(key)，并将其插入到二叉树中
 *
 * 参数说明:
 *     tree 二叉树的根结点
 *     key 插入结点的键值
 */
public void insert(T key) {
    BSTNode<T> z=new BSTNode<T>(key,null,null,null);

    // 如果新建结点失败，则返回。
    if (z != null)
        insert(this, z);
}

删除

删除结点 z 的思路：若 z 的左右子树均非空，则找到 z 的后继 y，用 y 的键值替换 z，转而删除 y；否则直接用 z 的非空孩子（或 null）顶替 z：

/*
 * 删除结点(z)，并返回被删除的结点
 *
 * 参数说明:
 *     bst 二叉树
 *     z 删除的结点
 */
private BSTNode<T> remove(BSTree<T> bst, BSTNode<T> z) {
    BSTNode<T> x=null;
    BSTNode<T> y=null;

    if ((z.left == null) || (z.right == null) )
        y = z;
    else
        y = successor(z);

    if (y.left != null)
        x = y.left;
    else
        x = y.right;

    if (x != null)
        x.parent = y.parent;

    if (y.parent == null)
        bst.mRoot = x;
    else if (y == y.parent.left)
        y.parent.left = x;
    else
        y.parent.right = x;

    if (y != z)
        z.key = y.key;

    return y;
}

/*
 * 删除结点(z)，并返回被删除的结点
 *
 * 参数说明:
 *     tree 二叉树的根结点
 *     z 删除的结点
 */
public void remove(T key) {
    BSTNode<T> z, node;

    if ((z = search(mRoot, key)) != null)
        if ( (node = remove(this, z)) != null)
            node = null;
}

打印

打印二叉查找树的结构，direction 为 0 表示根节点、-1 表示左孩子、1 表示右孩子：

private void print(BSTNode<T> tree, T key, int direction) {
    if(tree != null) {
        if(direction==0)    // tree是根节点
            System.out.printf("%2d is root\n", tree.key);
        else                // tree是分支节点
            System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1?"right" : "left");

        print(tree.left, tree.key, -1);
        print(tree.right,tree.key,  1);
    }
}

public void print() {
    if (mRoot != null)
        print(mRoot, mRoot.key, 0);
}

销毁

后序递归销毁整棵树：

/*
 * 销毁二叉树
 */
private void destroy(BSTNode<T> tree) {
    if (tree==null)
        return ;

    if (tree.left != null)
        destroy(tree.left);
    if (tree.right != null)
        destroy(tree.right);

    tree=null;
}

public void clear() {
    destroy(mRoot);
    mRoot = null;
}

测试程序

下面对测试程序的流程进行分析：

新建”二叉查找树” root；
向二叉查找树中依次插入 1, 5, 4, 3, 2, 6，插入过程与最终结构如下（原文图片丢失，据插入顺序重绘）：

flowchart TD
    n1((1)) -->|right| n5((5))
    n5 -->|left| n4((4))
    n5 -->|right| n6((6))
    n4 -->|left| n3((3))
    n3 -->|left| n2((2))

遍历和查找，结果为：前序遍历 1 5 4 3 2 6、中序遍历 1 2 3 4 5 6、后序遍历 2 3 4 6 5 1，最小值是 1，而最大值是 6；
删除节点 3（arr[3]），删除后 3 的左孩子 2 直接顶替其位置，重新中序遍历该二叉查找树，结果为 1 2 4 5 6。

测试代码：

/**
 * Java 语言: 二叉查找树
 *
 * @author skywang
 * @date 2013/11/07
 */
public class BSTreeTest {

    private static final int arr[] = {1,5,4,3,2,6};

    public static void main(String[] args) {
        int i, ilen;
        BSTree<Integer> tree=new BSTree<Integer>();

        System.out.print("== 依次添加: ");
        ilen = arr.length;
        for(i=0; i<ilen; i++) {
            System.out.print(arr[i]+" ");
            tree.insert(arr[i]);
        }

        System.out.print("\n== 前序遍历: ");
        tree.preOrder();

        System.out.print("\n== 中序遍历: ");
        tree.inOrder();

        System.out.print("\n== 后序遍历: ");
        tree.postOrder();
        System.out.println();

        System.out.println("== 最小值: "+ tree.minimum());
        System.out.println("== 最大值: "+ tree.maximum());
        System.out.println("== 树的详细信息: ");
        tree.print();

        System.out.print("\n== 删除根节点: "+ arr[3]);
        tree.remove(arr[3]);
        System.out.print("\n== 中序遍历: ");
        tree.inOrder();
        System.out.println();

        // 销毁二叉树
        tree.clear();
    }
}

测试结果：

== 依次添加: 1 5 4 3 2 6
== 前序遍历: 1 5 4 3 2 6
== 中序遍历: 1 2 3 4 5 6
== 后序遍历: 2 3 4 6 5 1
== 最小值: 1
== 最大值: 6
== 树的详细信息:
 1 is root
 5 is  1's  right child
 4 is  5's   left child
 3 is  4's   left child
 2 is  3's   left child
 6 is  5's  right child
== 删除根节点: 3
== 中序遍历: 1 2 4 5 6

BST 相关题目

二叉查找树（BST）：根节点大于等于左子树所有节点，小于等于右子树所有节点；二叉查找树中序遍历有序。这两条性质是解决下列题目的关键。

修剪二叉查找树

Trim a Binary Search Tree (Easy)

题目描述：只保留值在 L ~ R 之间的节点。

Input:
    3
   / \
  0   4
   \
    2
   /
  1
L = 1, R = 3

Output:
  3
 /
2
/
1

public TreeNode trimBST(TreeNode root, int L, int R) {
    if (root == null) return null;
    if (root.val > R) return trimBST(root.left, L, R);
    if (root.val < L) return trimBST(root.right, L, R);
    root.left = trimBST(root.left, L, R);
    root.right = trimBST(root.right, L, R);
    return root;
}

寻找二叉查找树的第 k 个元素

Kth Smallest Element in a BST (Medium)

中序遍历解法：

private int cnt = 0;
private int val;

public int kthSmallest(TreeNode root, int k) {
    inOrder(root, k);
    return val;
}

private void inOrder(TreeNode node, int k) {
    if (node == null) return;
    inOrder(node.left, k);
    cnt++;
    if (cnt == k) {
        val = node.val;
        return;
    }
    inOrder(node.right, k);
}

递归解法：先统计左子树节点个数，判断第 k 小的元素在哪一侧：

public int kthSmallest(TreeNode root, int k) {
    int leftCnt = count(root.left);

    if (leftCnt == k - 1) return root.val;
    if (leftCnt > k - 1) return kthSmallest(root.left, k);
    return kthSmallest(root.right, k - leftCnt - 1);
}

private int count(TreeNode node) {
    if (node == null) return 0;
    return 1 + count(node.left) + count(node.right);
}

把二叉查找树每个节点的值都加上比它大的节点的值

Convert BST to Greater Tree (Easy)

先遍历右子树（即先访问最大的值），用一个累加器 sum 依次回填节点值：

Input: The root of a Binary Search Tree like this:
      5
     / \
    2   13

Output: The root of a Greater Tree like this:
     18
    / \
   20  13

private int sum = 0;

public TreeNode convertBST(TreeNode root) {
    traver(root);
    return root;
}

private void traver(TreeNode node) {
    if (node == null) return;
    traver(node.right);
    sum += node.val;
    node.val = sum;
    traver(node.left);
}

二叉查找树的最近公共祖先

Lowest Common Ancestor of a Binary Search Tree (Easy)

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
  0       4       7       9
         / \
        3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6.

利用 BST 的有序性：p、q 都小于当前节点则往左，都大于则往右，分居两侧时当前节点就是 LCA：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
    if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
    return root;
}

二叉树的最近公共祖先

Lowest Common Ancestor of a Binary Tree (Medium)

普通二叉树没有有序性可以利用，需要在左右子树中递归查找 p 和 q：

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
  6        2      0       8
          / \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    return left == null ? right : right == null ? left : root;
}

从有序数组中构造二叉查找树

Convert Sorted Array to Binary Search Tree (Easy)

取中点为根，两侧递归构造：

public TreeNode sortedArrayToBST(int[] nums) {
    return toBST(nums, 0, nums.length - 1);
}

private TreeNode toBST(int[] nums, int sIdx, int eIdx){
    if (sIdx > eIdx) return null;
    int mIdx = (sIdx + eIdx) / 2;
    TreeNode root = new TreeNode(nums[mIdx]);
    root.left = toBST(nums, sIdx, mIdx - 1);
    root.right = toBST(nums, mIdx + 1, eIdx);
    return root;
}

根据有序链表构造平衡的二叉查找树

Convert Sorted List to Binary Search Tree (Medium)

Given the sorted linked list: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
      0
     / \
   -3   9
   /   /
 -10  5

用快慢指针找到链表中点作为根，断开链表后两侧递归：

public TreeNode sortedListToBST(ListNode head) {
    if (head == null) return null;
    if (head.next == null) return new TreeNode(head.val);
    ListNode preMid = preMid(head);
    ListNode mid = preMid.next;
    preMid.next = null;  // 断开链表
    TreeNode t = new TreeNode(mid.val);
    t.left = sortedListToBST(head);
    t.right = sortedListToBST(mid.next);
    return t;
}

private ListNode preMid(ListNode head) {
    ListNode slow = head, fast = head.next;
    ListNode pre = head;
    while (fast != null && fast.next != null) {
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    return pre;
}

在二叉查找树中寻找两个节点，使它们的和为一个给定值

Two Sum IV - Input is a BST (Easy)

Input:
    5
   / \
  3   6
 / \   \
2   4   7
Target = 9

Output: True

使用中序遍历得到有序数组之后，再利用双指针对数组进行查找。应该注意到，这一题不能分别在左右子树两部分来处理这种思想，因为两个待求的节点可能分别在左右子树中：

public boolean findTarget(TreeNode root, int k) {
    List<Integer> nums = new ArrayList<>();
    inOrder(root, nums);
    int i = 0, j = nums.size() - 1;
    while (i < j) {
        int sum = nums.get(i) + nums.get(j);
        if (sum == k) return true;
        if (sum < k) i++;
        else j--;
    }
    return false;
}

private void inOrder(TreeNode root, List<Integer> nums) {
    if (root == null) return;
    inOrder(root.left, nums);
    nums.add(root.val);
    inOrder(root.right, nums);
}

在二叉查找树中查找两个节点之差的最小绝对值

Minimum Absolute Difference in BST (Easy)

利用二叉查找树的中序遍历为有序的性质，计算中序遍历中临近的两个节点之差的绝对值，取最小值：

Input:
   1
    \
     3
    /
   2

Output:
1

private int minDiff = Integer.MAX_VALUE;
private TreeNode preNode = null;

public int getMinimumDifference(TreeNode root) {
    inOrder(root);
    return minDiff;
}

private void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);
    if (preNode != null) minDiff = Math.min(minDiff, node.val - preNode.val);
    preNode = node;
    inOrder(node.right);
}

寻找二叉查找树中出现次数最多的值

Find Mode in Binary Search Tree (Easy)

答案可能不止一个，也就是有多个值出现的次数一样多。同样利用中序遍历有序的性质，统计连续相同值的长度：

Input:
  1
   \
    2
   /
  2

Output: [2].

private int curCnt = 1;
private int maxCnt = 1;
private TreeNode preNode = null;

public int[] findMode(TreeNode root) {
    List<Integer> maxCntNums = new ArrayList<>();
    inOrder(root, maxCntNums);
    int[] ret = new int[maxCntNums.size()];
    int idx = 0;
    for (int num : maxCntNums) {
        ret[idx++] = num;
    }
    return ret;
}

private void inOrder(TreeNode node, List<Integer> nums) {
    if (node == null) return;
    inOrder(node.left, nums);
    if (preNode != null) {
        if (preNode.val == node.val) curCnt++;
        else curCnt = 1;
    }
    if (curCnt > maxCnt) {
        maxCnt = curCnt;
        nums.clear();
        nums.add(node.val);
    } else if (curCnt == maxCnt) {
        nums.add(node.val);
    }
    preNode = node;
    inOrder(node.right, nums);
}

参考文章

本文主要来源于 @skywang12345 的 https://www.cnblogs.com/skywang12345/p/3576452.html ，在此基础上重新组织和增加了内容。

系列导航

上一篇：树：基础和 Overview
下一篇：树：平衡二叉树（AVL）
相关篇：平衡二叉树 AVL、红黑树（解决 BST 退化问题的两步演进）、TreeMap 源码解析

CHARLIE SAYS