🌼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左子树的最大值 } } }
🔎结尾
欢迎各位点赞留言，如果有不懂可以在评论区探讨或者私信，希望和大家一起进步
