TreeNode successor = findMin(root.right);
successor.right = removeMin(root.right);
successor.left = root.left;

import java.util.NoSuchElementException;
 
/**
 * 基于整型的
 * 普通的二分搜索樹
 */
public class BST {
 
    private class TreeNode{
        private int val;
        private TreeNode left;
        private TreeNode right;
 
        public TreeNode(int val) {
            this.val = val;
        }
    }
 
    private int size;
    private TreeNode root;
 
    /**
     * 向以root為根的BST中插入一個(gè)新的結(jié)點(diǎn)val
     * @param val
     */
    public void add(int val){
        root = add(root,val);
    }
 
    private TreeNode add(TreeNode root, int val) {
        if(root == null){
            //創(chuàng)建一個(gè)新節(jié)點(diǎn)
            TreeNode newNode = new TreeNode(val);
            size++;
            return newNode;
        }
        //左子樹插入
        if(val < root.val){
            root.left = add(root.left,val);
        }
        //右子樹插入
        if(val > root.val){
            root.right = add(root.right,val);
        }
        return root;
    }
 
    /**
     * 判斷當(dāng)前以root為根的BST中是否包含了val
     * @param val
     * @return
     */
    public boolean contains(int val){
        return contains(root,val);
    }
 
    private boolean contains(TreeNode root, int val) {
        if(root == null){
            return false;
        }
        if(val == root.val){
            //找到了
            return true;
        }else if(val < root.val){
            //遞歸左子樹查找
            return contains(root.left,val);
        }else{
            //遞歸右子樹查找
            return contains(root.right,val);
        }
    }
 
    /**
     * 找到最小值
     * @return
     */
    public int findMin(){
        //判空
        if(root == null){
            //拋出一個(gè)空指針異常
            throw new NoSuchElementException("root is empty! cannot find min");
        }
        TreeNode minNode = findMin(root);
        return minNode.val;
    }
 
    private TreeNode findMin(TreeNode root) {
        //當(dāng)此節(jié)點(diǎn)左子樹為空，說明此節(jié)點(diǎn)是最小值
        if(root.left == null){
            return root;
        }
        //遞歸訪問左子樹
        return findMin(root.left);
    }
 
    /**
     * 找到最大值
     * @return
     */
    public int findMax(){
        //判空
        if(root == null){
            throw new NoSuchElementException("root is empty! cannot find max");
        }
        TreeNode maxNode = findMax(root);
        return maxNode.val;
    }
 
    private TreeNode findMax(TreeNode root) {
        //當(dāng)此節(jié)點(diǎn)右子樹為空，說明此節(jié)點(diǎn)是最大值
        if(root.right == null){
            return root;
        }
        //遞歸訪問右子樹
        return findMax(root.right);
    }
 
    /**
     * 在當(dāng)前BST中刪除最小值節(jié)點(diǎn)，返回刪除的最小值
     * @return
     */
    public int removeMin(){
        int min =findMin();
        root = removeMin(root);
        return min;
    }
 
    private TreeNode removeMin(TreeNode root) {
        if(root.left == null){
            TreeNode right = root.right;
            //找到最小值，刪除節(jié)點(diǎn)
            root = root.left = null;
            size--;
            return right;
        }
        root.left = removeMin(root.left);
        return root;
    }
 
    /**
     * 在當(dāng)前BST中刪除最大值節(jié)點(diǎn)，返回刪除的最大值
     * @return
     */
    public int removeMax(){
        int max = findMax();
        root = removeMax(root);
        return max;
    }
 
    //在當(dāng)前以root為根的BST中刪除最小值所在的節(jié)點(diǎn)，返回刪除后的樹根
    private TreeNode removeMax(TreeNode root) {
        if(root.right == null){
            TreeNode right = root.right;
            //找到最大值，刪除節(jié)點(diǎn)
            root = root.right = null;
            size--;
            return right;
        }
        root.right = findMax(root.right);
        return root;
    }
 
    /**
     * 在當(dāng)前以root為根節(jié)點(diǎn)的BST中刪除值為val的節(jié)點(diǎn)
     * 返回刪除后的新的根節(jié)點(diǎn)
     * @return
     */
    public void removeValue(int value){
        root = removeValue(root,value);
    }
 
    private TreeNode removeValue(TreeNode root, int value) {
        if(root == null){
            throw new NoSuchElementException("root is empty! cannot find remove");
        }else if(value < root.val){
            root.left = removeValue(root.left,value);
            return root;
        }else if(value > root.val){
            root.right = removeValue(root.right,value);
            return root;
        }else {
            //此時(shí)value == root.value
            if(root.left == null){
                //刪除最小數(shù)
                TreeNode right = root.right;
                root = root.right = null;
                size--;
                return right;
            }
            if(root.right == null){
                //刪除最大數(shù)
                TreeNode left = root.left;
                root = root.left =null;
                size--;
                return left;
            }
            //找到當(dāng)前該刪除節(jié)點(diǎn)的前驅(qū)或者后繼節(jié)點(diǎn)作為刪除后的新節(jié)點(diǎn)
            //當(dāng)我們使用后繼節(jié)點(diǎn)時(shí)，先連removeMin(root.right),在連root.left
            TreeNode successor = findMin(root.right);
            successor.right = removeMin(root.right);
            successor.left = root.left;
            return successor;
        }
    }
 
 
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        generateBSTString(root,0,sb);
        return sb.toString();
    }
 
    //直觀打印，可以看到樹的深度
    private void generateBSTString(TreeNode root, int height, StringBuilder sb) {
        if(root == null){
            sb.append(generateHeightString(height)).append("NULL\n");
            return;
        }
        sb.append(generateHeightString(height)).append(root.val).append("\n");
        generateBSTString(root.left,height+1,sb);
        generateBSTString(root.right,height+1,sb);
    }
 
    private String generateHeightString(int height) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < height; i++) {
            sb.append("--");
        }
        return sb.toString();
    }
}