二叉搜索树（二叉排序树）—Java（下）

2023-07-29 46

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 二叉搜索树（二叉排序树）—Java（下）

🌼cur.left != null && cur.right != null–>要删除节点的左右均不为空

找cur左子树的右叶子节点–>左子树的最大值–>最大值的右节点一定为null

找cur右子树的左叶子节点–>右子树的最小值–>最小值的左节点一定为null

不可以是左子树的左叶子节点(左子树最小值) or 右子树的右叶子节点（右子树最大值）

🌼代码演示

以cur的右子树的最小值举例

以cur的左子树的最大值举例

🌼完整remove代码

public void remove(int val) {
        TreeNode cur = root;
        TreeNode pre = null;
        while(cur != null) {
            if(cur.val == val) {//找到了值为val的节点
                removeNode(pre,cur);
                return;
            }
            else if(cur.val < val) {
                pre = cur;
                cur = cur.right;
            }else {//cur.val > val
                pre = cur;
                cur = cur.left;
            }
        }
}
//删除值为val的cur节点
private void removeNode(TreeNode pre,TreeNode cur) {
        if(cur.left == null) {
            if(cur == root) {
                root = cur.right;
            }else if(pre.left == cur){//cur在父节点左侧
                pre.left = cur.right;
            }else {//pre.right = cur --> //cur在父节点右侧
                pre.right = cur.right;
            }
        }else if(cur.right == null) {
            if(cur == root) {
                root = cur.left;
            }else if(pre.left == cur) {//cur在父节点左侧
                pre.left = cur.left;
            }else {//pre.right = cur --> //cur在父节点右侧
                pre.right = cur.left;
            }
        }else {//cur.left != null && cur.right != null
            TreeNode targetPre = cur;
            TreeNode target = cur.right;
            while(target.left != null) {//以cur的右子树的最小值举例-->右子树的左叶子节点
                //也可以是cur的左子树的最大值-->左子树的右叶子节点
                targetPre = target;
                target = target.left;
            }
            cur.val = target.val;
            //此时target的左侧一定为null-->target.left == null
            targetPre.left = target.right;//因为是寻找cur右子树的最小值
            //一定是target == targetPre.left
            //target == targetPre.right-->这种情况只会出现在寻找cur左子树的最大值
        }
}

🌻完整模拟代码

public class TestBinarySearch {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root = null;//根节点
    //查找二叉搜索树中指定的val值
    public TreeNode find(int val) {
        TreeNode cur = root;
        while(cur != null) {
            if(cur.val < val) {
                cur = cur.right;
            }else if(cur.val > val) {
                cur = cur.left;
            }else {//cur.val == val-->find!
                return cur;
            }
        }
        //未找到
        return null;
    }
    //插入元素
    public void insert(int val) {
        if(root == null) {
            root = new TreeNode(val);
            return;
        }
        TreeNode pre = null;
        TreeNode cur = root;
        while(cur != null) {
            pre = cur;
            if(cur.val < val) {
                cur = cur.right;
            }else if(cur.val > val){
                cur = cur.left;
            }else {//二叉搜索树中不要插入相同的数据（无意义）
                return;
            }
        }
        if(val < pre.val) {
            pre.left = new TreeNode(val);
        }else {
            pre.right = new TreeNode(val);
        }
    }
    //中序遍历
    public void inOrder(TreeNode root) {
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    //删除
    public void remove(int val) {
        TreeNode cur = root;
        TreeNode pre = null;
        while(cur != null) {//找到了值为val的节点
            if(cur.val == val) {
                removeNode(pre,cur);
                return;
            }
            else if(cur.val < val) {
                pre = cur;
                cur = cur.right;
            }else {//cur.val > val
                pre = cur;
                cur = cur.left;
            }
        }
    }
    //删除值为val的cur节点
    private void removeNode(TreeNode pre,TreeNode cur) {
        if(cur.left == null) {
            if(cur == root) {
                root = cur.right;
            }else if(pre.left == cur){//cur在父节点左侧
                pre.left = cur.right;
            }else {//pre.right = cur --> //cur在父节点右侧
                pre.right = cur.right;
            }
        }else if(cur.right == null) {
            if(cur == root) {
                root = cur.left;
            }else if(pre.left == cur) {//cur在父节点左侧
                pre.left = cur.left;
            }else {//pre.right = cur --> //cur在父节点右侧
                pre.right = cur.left;
            }
        }else {//cur.left != null && cur.right != null
            TreeNode targetPre = cur;
            TreeNode target = cur.right;
            while(target.left != null) {//以cur的右子树的最小值举例-->右子树的左叶子节点
                //也可以是cur的左子树的最大值-->左子树的右叶子节点
                targetPre = target;
                target = target.left;
            }
            cur.val = target.val;
            //此时target的左侧一定为null-->target.left == null
            targetPre.left = target.right;//因为是寻找cur右子树的最小值
            //一定是target == targetPre.left
            //target == targetPre.right-->只会出现在寻找cur左子树的最大值
        }
     }
}