[Java数据结构与算法] 二叉搜索树（BinarySearchTree）

public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

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

// 查找
public TreeNode search (int val) {
    TreeNode cur = root;

    while (cur != null) {
        if (cur.val < val) {
            // 往右子树查找
            cur = cur.right;
        } else if (cur.val > val) {
            // 往左子树查找
            cur = cur.left;
        } else {
            return cur;
        }
    }
    return null;
}

// 插入
public void insert (int val) {
    TreeNode node = new TreeNode(val);

    if (root == null) {
        root = node;
        return;
    }

    TreeNode prev = null;
    TreeNode cur = root;

    // 遍历搜索树
    while (cur != null) {
        if (cur.val < val) {
            // 插入右子树
            prev = cur;
            cur = cur.right;
        } else if (cur.val > val) {
            // 插入左子树
            prev = cur;
            cur = cur.left;
        } else {
            // 二叉搜索树不可以插入两个相同的元素
            return;
        }
    }

    // 当cur为空时，就可以插入node了
    if (prev.val < val) {
        prev.right = node;
    } else {
        prev.left = node;
    }
}

// 删除
public void remove (int val) {
    // 找到要删除的结点
    TreeNode prev = null;
    TreeNode cur = root;

    while (cur != null) {
        if (cur.val < val) {
            prev = cur;
            cur = cur.right;
        } else if (cur.val > val) {
            prev = cur;
            cur = cur.left;
        } else {
            // 找到了，执行删除操作
            removeNode(prev,cur);
            return;
        }
    }
}
private void removeNode(TreeNode prev, TreeNode cur) {
    if (cur.left == null) {    // cur的左子树为空、右子树不为空
        if (cur == prev.left) {    // cur是prev的左子树
            prev.left = cur.right;
        } else if (cur == prev.right) {    // cur是prev的右子树
            prev.right = cur.right;
        } else {    // cur是根节点
            root = cur.right;
        }
    } else if (cur.right == null) {    // cur的右子树为空、左子树不为空
        if (cur == parent.left) {    // cur是prev的左子树
            prev.left = cur.left;
        } else if (cur == prev.right) {    // cur是prev的右子树
            prev.right = cur.left;
        } else {    // cur是根节点
            root = cur.left;
        }
    } else {    // cur的左右子树都不为空
        // 替换删除
        TreeNode targetPrev = cur;
        TreeNode target = cur.right;

        // 找到右子树最左边的结点
        while (target.left != null) {
            targetPrev = target;
            target = target.left;
        }

        // 替换
        cur.val = target.val;

        // 删除
        if (target == targetPrev.left) {
            targetPrev.left = target.right;
        } else {
            targetPrev.right = target.right;
        }
    }
}