class BinarySearchTree {
    static class BSNode {
        public int val;
        public BSNode left;
        public BSNode right;
        public BSNode(int val) {
            this.val = val;
        }
    }
    public BSNode root = null;
    public BSNode search(int val) {
        if (root == null) {
            return null;
        }
        BSNode cur = root;
        while (cur != null) {
            if (cur.val == val) {
                return cur;
            } else if (cur.val < val) {
                cur = cur.right;
            } else {
                cur = cur.left;
            }
        }
        return null;
    }
    public boolean insert(int val) {
        BSNode bsNode = new BSNode(val);
        if (root == null) {
            root = bsNode;
            return true;
        }
        BSNode cur = root;
        BSNode parent = null;
        while (cur != null) {
            //注意我们在二叉搜索树中插入的元素不能与已知二叉树的元素相同.
            if (cur.val == val) {
                return false;
            } else if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
        //这块是当cur为null的时候，此时就要插入我们的元素了
        if (parent.val < val) {
            parent.right = bsNode;
        } else {
            parent.left = bsNode;
        }
        return true;
    }
    public void remove(int val) {
        //假设整棵二叉搜索树都为空的话，直接结束
        if (root == null) {
            return;
        }
        //使用cur来遍历寻找我们所要删除的节点
        BSNode cur = root;
        //父亲节点parent
        BSNode parent = null;
        while (cur != null) {
            if (cur.val == val) {
                //此时我们使用removeNode方法来进行删除操作，这样的模块化设计代码看起来更加清晰，并且二叉搜索树的删除操作比较繁琐，需要一个单独的方法
                removeNode(parent, cur, val);
                //删除完成直接return走人
                return;
            } else if (cur.val < val) {
                //让parent去记录每个节点的父节点
                parent = cur;
                //小于val就说明我们所要删除的值在我们当前节点的右边
                cur = cur.right;
            } else {
                //让parent去记录每个节点的父节点
                parent = cur;
                大于val就说明我们所要删除的值在我们当前节点的左边
                cur = cur.left;
            }
        }
    }
    /**
     * 这个方法中的参数第一个代表当前所有需要删除节点的父类，第二个是需要删除的节点，第三个是要删除的节点的值
     *
     * @param parent
     * @param cur
     * @param val
     */
    private void removeNode(BSNode parent, BSNode cur, int val) {
        //第一种大情况：cur.left = null
        if (cur.left == null) {
            if (cur == root) {
                root = cur.right;
            } else if (parent.left == cur) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
            //第二种大情况:cur.right = null
        } else if (cur.right == null) {
            if (cur == root) {
                root = cur.left;
            } else if (parent.left == cur) {
                parent.left = cur.left;
            } else {
                parent.right = cur.left;
            }
        } else {
            //这块的else就是第三种情况了:cur.left != null && cur.right != null
            //首先让我们替罪羊的父亲指向cur
            BSNode targetParent = cur;
            //因为我们想让即将被删除的节点的右子树中的最小值作为替罪羊，所以此处我们就让替罪羊先指向右子树
            BSNode target = cur.right;
            //开始让下遍历寻找右子树中的最小值
            while (target.left != null) {
                //每走一步之前想让父亲节点指向我们target所在的位置
                targetParent = target;
                //然后让target一直往左下走
                target = target.left;
            }
            //走到这里就代表target.left = null了，说明target此时指向的节点就是 右边的最小值
            //然后将target所指向的值赋给我们的cur，也就是替换掉当前要删除掉的值
            cur.val = target.val;
            //下面就是分的那两种情况
            //第一种情况是我们要删除节点的右子树含有左子树
            if (target == targetParent.left) {
                targetParent.left = target.right;
                //下面的是我们所删除的节点的右子树不含有左子树的时候
            } else {
                targetParent.right = target.right;
            }
        }
    }
}
public class TestDemo {
    //注意这里的传参方式
    public static void preOrder(BinarySearchTree.BSNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    public static void inOrder(BinarySearchTree.BSNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    public static void main(String[] args) {
        /*
        以下代码是对我们二叉搜索树的插入，删除，搜索操作进行测试的
         */
        System.out.println("插入操作测试....................................");
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(4);
        binarySearchTree.insert(3);
        binarySearchTree.insert(1);
        binarySearchTree.insert(15);
        binarySearchTree.insert(11);
        //对我们的二叉搜索树进行前序遍历
        System.out.println("前序遍历结果为:");
        preOrder(binarySearchTree.root);
        System.out.println();
        //对我们的二叉搜索树进行中序遍历
        System.out.println("中序遍历结果为:");
        inOrder(binarySearchTree.root);
        System.out.println();
        System.out.println("查找操作测试......................................");
        try {
            BinarySearchTree.BSNode ret = binarySearchTree.search(4);
            //如果搜索到了当前的4这个节点，就直接输出
            System.out.println("找到"+ret.val+"这个节点啦");
        } catch (NullPointerException e) {
            //如果没有找到这个节点，就输出没有找到的话
            System.out.println("没有找到当前的节点............");
            e.printStackTrace();
        }
        System.out.println("删除操作测试....................................");
        binarySearchTree.remove(15);
        //对我们的二叉搜索树进行前序遍历
        System.out.println("前序遍历结果为:");
        preOrder(binarySearchTree.root);
        System.out.println();
        //对我们的二叉搜索树进行中序遍历
        System.out.println("中序遍历结果为:");
        inOrder(binarySearchTree.root);
        System.out.println();
    }
}