6-11中关于删除BST中最大最小元素的问题

Question

波波老师，这是6-11中删除二分树中最小元素的code。对于红框中的code，我的理解是我们会一直查看node的left child，当最左边的这个node 没有left child时，我们创建一个新的node指针来存储当前这个node的右子树。然后把当前node指向右边的指针设为null；由于我们要删除一个node，所以对于整个tree来说，size–；然后我们return 这个我们需要删除的node的右子树，并把这个值赋给一个我们的新root。我的疑问是，在这几步操作中我并没有看到删除这个node的操作，并且我们最后return的是指向右子树的一个指针，并赋值给新root，那么我们现在得到的树不是只有这个右子树了吗？可是我们希望的是把这个右子树，和原有的树（删除掉最小node）连起来，root应该还是原来那个roo。我不知道我的理解错在哪里，期待您的解答，谢谢。

Answer 1

liuyubobobo 2018-10-02 10:26:13

我们最后return的是指向右子树的一个指针，没有错。而return这个node的右子树，就已经将node删除了！因为，我们不再管node了。要注意，你的描述的错误时：这个结果，我们没有赋值给root！而是赋值给上层调用的node的left，也就是你截取屏幕的225行：）删除实际发生在这里，这将导致node被忽略了：）

在我们实现的这个二叉树的递归删除的过程中，删除实际发生的方式，和我们在5-3至5-5所介绍的链表删除操作的递归算法中删除发生的方式是一模一样的。尤其是我们在5-5所介绍的递归过程的微观运行机制。强烈建议再看一遍，之后再回过头，思考一下这一小节的代码中，我们的二叉树的删除发生在什么时候？发生的时机是完全一致的！

加油！：）

• 提问者 聪明的土拨鼠 #1

  明白了，还是递归这一部分不太好理解，特别容易绕晕

• 慕粉3869017 #2

  我这这里也是想了很久才明白过来，现在看到老师的这个解释竟然和我想的一样终于不用再纠结更久了~