删除节点不理解

Question

这个图片中描述的问题 有点不理解 求老师指点

Answer 1

liuyubobobo 2019-09-17 01:08:37

rightNode = node.right 暂存了右节点，在你的例子里， rightNode 就是 D

之后，node.right = null，其实是让 B 节点和原来的二分搜索树“脱离”

之后的关键是 return 了 rightNode，即返回了 D 节点。这句话使得 D 节点和原来的二分搜索树连在了一起。因为在上一层，会赋值给上一层的node.left，即 node.left = removeMin(node.left)这句话，也就是，让A.left = D。

整体而言，这个运行逻辑，和我在第五章介绍的链表的递归删除，是完全一致的。只不过对于二叉树，要根据值的大小，区别一下左右而已。可以再仔细回顾一下第五章链表的递归删除，尤其是微观解读，理解一下，这个递归删除的结果，为什么一定要返回去：）

继续加油！：）

• 提问者 371425 #1

  非常感谢！

• happyczg #2

  老师问一下为什么不直接return node.right ;//就是把要删除结点的右孩子直接返回到上一层   而一定要用rightnode来暂存一下呢？感觉这步有一点点多余= =

• liuyubobobo 回复 happyczg #3

  可以的，没有问题，课程这样写是为了做 node.right = null，但之前课程介绍过，在 Java 语言中，这一步不做也没有关系：）继续加油！：）

Answer 2

提问者 371425 2019-09-17 10:27:19

// 删除掉以node为根的二分搜索树中的最小节点                     A

        // 返回删除节点后新的二分搜索树的根                         /  \

        private Node removeMin(Node node){               //   B   C

            if(node.left == null){                                      //    \

                Node rightNode = node.right;                    //     D

                //B节点的right连接为null删除B节点：说明与D脱节了

                node.right = null;

                size --;//节点数量减1

                return rightNode;//返回D节点

            }

            //如图：首先传入A这个节点，判断A的左节点为B 不为空，运行这里面的语句

            //然后递归调用removeMin 传入A的左节点为B 返回的是节点D 赋值给 节点A的左节点

            node.left = removeMin(node.left);

            return node;//最后返回的是赋值后的D节点。

        }

老师  我的理解对吗？

• liuyubobobo #1

  其他注释都对，我觉得你已经理解了。就是对于你的用例，最后一个 return 走到的时候，其实返回的是删除掉了 B 节点的 A 节点。