删除二叉搜索树中的节点附图详解

二叉搜索树的删除较为繁琐，但是静下心来相信很快就能吸收！主要分为两步：首先是查找待删除节点，然后针对这个节点进行删除。

我们用cur变量搜索，用parent变量表示curr的双亲结点

搜索待删除节点

搜索不是这篇文章的重点，我们直接上代码

public boolean delete(int key) {
    
        // wirte code here,主要分为三种情况
        Node parent = null;
        Node cur = root;//cur负责找到需要删除的节点
        while (cur != null) {
    
            if (cur.key < key) {
    
                parent = cur;
                cur = cur.right;
            } else if (cur.key > key) {
    
                parent = cur;
                cur = cur.left;
            } else {
    
            	//△到这里，我们就找到了待删除节点，即cur
                deleteNode(parent, cur);
                //deleteNode方法就是删除cur节点
                return true;
            }
        }
        return false;
    }

注意：到上面代码的三角形处，我们就找到了待删除节点cur

正文(删除cur节点)

我们分为三种情况：(cur节点就是待删除节点，parent是cur的双亲结点，下文不赘述)

1. cur.left = null;
2. cur.right = null;
3. cur.left != null && cur.right != null;

情况1：cur.left = null

这次情况又分为3种情况

1. cur 是 根节点
2. cur 是 parent 的左孩子
3. cur 是 parent 的右孩子

① cur 为根节点

这种情况下，我们直接让root = root.right即可

② cur 为 parent 的左孩子

如图，我们让parent.left = cur.right即可

③ cur 为 parent 的右孩子

如图，我们让parent.right = cur.right即可

情况2：cur.right = null

• 情况 2 和情况 1 思路基本上是一样的，我们再重复一次巩固一下

1. cur 是 根节点
2. cur 是 parent 的左孩子
3. cur 是 parent 的右孩子

① cur 为根节点

同理，只需root = root.left即可

② cur 为 parent 的左孩子

如图，我们让parent.left = cur.left

③ cur 为 parent 的右孩子

如图，我们让parent.right = cur.left

情况3：cur.left != null && cur.right != null

核心思想：在 cur 的右子树中找到值最小的节点，然后将该节点值赋给 cur ，再将该最小节点删除

• 所以就一共有两个步骤：① 找 cur 右子树最小节点，并将该最小值赋给cur ② 删除这个最小节点

步骤①

先定义 target = cur.right，再让 targetParent 为 target 的双亲结点
最终：让 target 指向 cur 右子树的最小节点，让 targetParent 指向 target的双亲

以下 ↓ 代码是让 target 指向 cur 右子树的最小节点

	Node target = cur.right;//找到cur右子树中的最小节点，替换cur节点，并且删除这个最小节点
	Node targetParent = cur; //target节点的双亲结点
	while (target.left != null) {
      //找到右子树的最小节点
	    targetParent = target;
	    target = target.left;
	}

然后再赋值：cur.key = target.key;，如图

步骤②

到了这一步，我们的任务就只剩删除 target 节点了，这时再分为两种情况，也比较好理解了

1. target == targetParent.left
2. tartget == targetParent.right

情况1 ：仅需targetParent.left = target.right

情况2：仅需targetParent.right = target.right

完成！

删除 cur 节点代码

private void deleteNode(Node parent, Node cur) {
    
        //至此，cur指向待删除的节点
        if (cur.left == null) {
      //情况1，如果左孩子为空
            if (cur == root) {
    
                root = cur.right;
            } else if (parent.left == cur) {
    
                parent.left = cur.right;
            } else {
    
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
      //情况2，如果右孩子为空
            if (cur == root) {
    
                root = cur.left;
            } else if (parent.left == cur) {
    
                parent.left = cur.left;
            } else {
    
                parent.right = cur.left;
            }
        } else {
      //情况3，如果左右孩子都不为空
            Node target = cur.right;//找到cur右子树中的最小节点，替换cur节点值，并且删除这个最小节点
            Node targetParent = cur; //target节点的双亲结点
            while (target.left != null) {
      //找到右子树的最小节点
                targetParent = target;
                target = target.left;
            }
            cur.key = target.key; //覆盖cur值

            if (target == targetParent.left) {
    
                targetParent.left = target.right;
            } else {
    
                targetParent.right = target.right;
            }
        }
    }

全代码

public boolean delete(int key) {
    
        // wirte code here,主要分为三种情况
        Node parent = null;
        Node cur = root;//cur负责找到需要删除的节点
        while (cur != null) {
    
            if (cur.key < key) {
    
                parent = cur;
                cur = cur.right;
            } else if (cur.key > key) {
    
                parent = cur;
                cur = cur.left;
            } else {
    
                deleteNode(parent, cur);
                return true;
            }
        }
        return false;
    }

    private void deleteNode(Node parent, Node cur) {
    
        //至此，cur指向待删除的节点
        if (cur.left == null) {
      //如果左孩子为空
            if (cur == root) {
    
                root = cur.right;
            } else if (parent.left == cur) {
    
                parent.left = cur.right;
            } else {
    
                parent.right = cur.right;
            }
        } 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 {
      //如果左右孩子都不为空
            Node target = cur.right;//找到cur右子树中的最小节点，替换cur节点，并且删除这个最小节点
            Node targetParent = cur; //target节点的双亲结点
            while (target.left != null) {
      //找到右子树的最小节点
                targetParent = target;
                target = target.left;
            }
            cur.key = target.key; //覆盖

            if (target == targetParent.left) {
    
                targetParent.left = target.right;
            } else {
    
                targetParent.right = target.right;
            }
        }
    }