二叉搜索树总结

二叉搜索树（BST）是二叉树的一种特殊表示形式，它满足如下特性：

1. 每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
2. 每个节点中的值必须小于（或等于）存储在其右子树中的任何值。

下面是一个二叉搜索树的例子：

kthLargest方法

该方法的作用是返回二叉搜索树第k大的节点

在每个节点中放置一个计数器，以表示以此节点为根的子树中有多少个节点。

对于二叉搜索树的每个节点来说，它的左子树上所有结点的值均小于它的根结点的值，右子树上所有结点的值均大于它的根结点的值。

换言之，对于二叉搜索树的每个节点来说，若其左子树共有n个节点，那么该节点是组成二叉搜索树的有序数组中第n + 1个值。若其右子树有m个节点，那么该节点是二叉搜索树的第m+1大的节点。

具体操作如动图

kthSmallest的思路与其类似。

前驱(predecessor)/后继(successor)

以后继为例：

1. 若一个节点有右子树，那么该节点的后继节点是其右子树中val值最小的节点

2. 若一个节点没有右子树，那么判断该节点和其父节点的关系：

   2.1 若该节点是其父节点的左孩子，那么该节点的后继结点即为其父节点

   2.2 若该节点是其父节点的右孩子，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的左孩子，那么Q就是该节点的后继节点

相关代码

public class BinaryTree {

    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        int cnt = 1; //计数器

        public TreeNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    '}';
        }
    }

    private TreeNode root;


    private TreeNode add(TreeNode node, int v) {
        if (node == null) {
            return new TreeNode(v);
        }
        if (v > node.val) {
            node.right = add(node.right, v);
            node.cnt++;
        } else {
            node.cnt++;
            node.left = add(node.left, v);
        }
        return node;
    }

    public void add(int v) {
        root = add(root, v);
    }

    private TreeNode getMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    public int getMin() {
        if (root == null) {
            return -1;
        }
        TreeNode minNode = getMin(root);
        return minNode.val;
    }

    private TreeNode getMax(TreeNode node) {
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    public int getMax() {
        if (root == null) {
            return -1;
        }
        TreeNode maxNode = getMax(root);
        return maxNode.val;
    }

    public void delMin() {
        if (root != null) {
            root = delMin(root);
        }
    }

    // 删除最小节点
    private TreeNode delMin(TreeNode node) {

        if (node.left == null) {
            return node.right;
        }
        node.cnt--;
        node.left = delMin(node.left);
        return node;
    }

    public void delMax() {
        if (root != null) {
            root = delMax(root);
        }
    }

    // 删除最大节点
    private TreeNode delMax(TreeNode node) {
        if (node.right == null) {
            return node.left;
        }
        node.cnt--;
        node.right = delMax(node.right);
        return node;
    }


    public void remove(int v) {
        root = remove(root, v);
    }

    // 在以node为根的二叉搜索树中，删除任意一个节点 (Hibbard deletion)
    private TreeNode remove(TreeNode node, int v) {
        if (node == null) {
            return null;
        }
        if (node.val > v) {
            node.cnt--;
            node.left = remove(node.left, v);
            return node;
        }else if (node.val < v) {
            node.cnt--;
            node.right = remove(node.right, v);
            return node;
        } else {
            // node.val == v
            if (node.left == null) {
                return node.right;
            }
            if (node.right == null) {
                return node.left;
            }
            TreeNode s = getMin(node.right);
            s.right = delMin(node.right);
            s.left = node.left;
            int lsons = (s.left != null)? s.left.cnt :0;
            int rsons = (s.right != null)? s.right.cnt :0;
            s.cnt = lsons + rsons + 1;
            return s;
        }
    }

    // 在以node为根的二叉搜索树中, 查找值为n的节点
    public TreeNode find(TreeNode node, int n) {
        if (node == null){
            return null;
        }
        if (n == node.val) {
            return node;
        } else if(n > node.val) {
            return find(node.right, n);
        } else {
            return find(node.left, n);
        }
    }


    // 在以node为根的二叉搜索树中，求值为n的节点的排名
    private int rank(TreeNode node, int n) {
        if (n == node.val) {
            if (node.left != null) {
                return node.left.cnt + 1;
            } else {
                return 1;
            }
        } else if (n > node.val) {
            return rank(node.right, n) + rank(node, node.val);
        } else {
            return rank(node.left, n);
        }
    }
  
		public int rank(int n) {
        return rank(root, n);
    }
    
  	// 在以node为根的二叉搜索树中，返回二叉搜索树第k小的节点
    private TreeNode kthSmallest(TreeNode node, int k) {
        if (node == null) {
            return null;
        }
        int pivot = (node.left != null)?node.left.cnt+1:1;
        if (pivot == k) {
            return node;
        } else if (pivot > k) {
            return kthSmallest(node.left, k);
        } else {
            return kthSmallest(node.right, k-pivot);

        }
    }

    // 在以node为根的二叉搜索树中，返回二叉搜索树第k大的节点
    private TreeNode kthLargest(TreeNode node, int k) {
        if (node == null) {
            return null;
        }
        int pivot = (node.right != null)?node.right.cnt+1:1;
        if (pivot == k) {
            return node;
        } else if (pivot < k) {
            return kthLargest(node.left, k-pivot);
        } else {
            return kthLargest(node.right, k);

        }
    }

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

    public TreeNode kthLargest(int k) {
        return kthLargest(root, k);
    }

    // 查找key的前驱
    // 如果不存在key的前驱(key不存在, 或者key是整棵二叉树中的最小值), 则返回-1
    public int predecessor(int key){

        TreeNode node = find(root, key);
        // 如果key所在的节点不存在, 则key没有前驱, 返回-1
        if(node == null)
            return -1;

        // 如果key所在的节点左子树不为空,则其左子树的最大值为key的前驱
        if(node.left != null)
            return getMax(node.left).val;

        // 否则, key的前驱在从根节点到key的路径上, 在这个路径上寻找到比key小的最大值, 即为key的前驱
        TreeNode preNode = predecessorFromAncestor(root, key);
        return preNode == null ? -1 : preNode.val;
    }

    // 查找key的后继
    // 如果不存在key的后继(key不存在, 或者key是整棵二叉树中的最大值), 则返回-1
    public int successor(int key){

        TreeNode node = find(root, key);
        // 如果key所在的节点不存在, 则key没有前驱, 返回-1
        if(node == null)
            return -1;

        // 如果key所在的节点右子树不为空,则其右子树的最小值为key的后继
        if(node.right != null)
            return getMin(node.right).val;

        // 否则, key的后继在从根节点到key的路径上, 在这个路径上寻找到比key大的最小值, 即为key的后继
        TreeNode sucNode = successorFromAncestor(root, key);
        return sucNode == null ? -1 : sucNode.val;
    }

    // 在以node为根的二叉搜索树中, 寻找key的祖先中,比key小的最大值所在节点, 递归算法
    // 算法调用前已保证key存在在以node为根的二叉树中
    private TreeNode predecessorFromAncestor(TreeNode node, int key){

        if(node.val == key)
            return null;

        if(node.val > key)
            // 如果当前节点大于key, 则当前节点不可能是比key小的最大值
            // 向下搜索到的结果直接返回
            return predecessorFromAncestor(node.left, key);
        else{
            assert node.val < key;
            // 如果当前节点小于key, 则当前节点有可能是比key小的最大值
            // 向右继续搜索, 将结果存储到tempNode中
            TreeNode tempNode = predecessorFromAncestor(node.right, key);
            if(tempNode != null)
                return tempNode;
            else
                // 如果tempNode为空, 则当前节点即为结果
                return node;
        }
    }

    // 在以node为根的二叉搜索树中, 寻找key的祖先中,比key大的最小值所在节点, 递归算法
    // 算法调用前已保证key存在在以node为根的二叉树中
    private TreeNode successorFromAncestor(TreeNode node, int key){

        if(node.val == key)
            return null;

        if(node.val < key)
            // 如果当前节点小于key, 则当前节点不可能是比key大的最小值
            // 向下搜索到的结果直接返回
            return successorFromAncestor(node.right, key);
        else{
            assert(key < node.val);
            // 如果当前节点大于key, 则当前节点有可能是比key大的最小值
            // 向左继续搜索, 将结果存储到tempNode中
            TreeNode tempNode = successorFromAncestor(node.left, key);
            if(tempNode != null)
                return tempNode;
            else
                // 如果tempNode为空, 则当前节点即为结果
                return node;
        }
    }
}