有一个问题不知道我想的是不是对的，这个删除的过程是不是就相当于在重新绘制了这颗二叉树

Question

写代码的时候一直想不明白这个successor是怎么挂回二叉树的，因为好像没有直接挂上去的指向动作。后来纸笔模拟了下调用栈，是不是相当于我们从待删除节点的地方，开始反向重新绘制二叉树，一层一层吧子节点返回给上层，直至本颗树的根节点。重新绘制了部分二叉树。

Answer 1

liuyubobobo 2018-07-24 08:52:20

关键还是对递归过程的理解。在这里，使用宏观语意理解，应该更为清晰。

以下阐述基于我的课程代码：https://github.com/liuyubobobo/Play-with-Data-Structures/blob/master/06-Binary-Search-Tree/12-Remove-Elements-in-BST/src/BST.java 

对于我们整个remove(node, e)这个方法，他的语意就是：删除掉以node为根的二分搜索树中值为e的节点, 返回删除这个节点后，新的二分搜索树的根节点。其实，这个定义，和我们在之前实现的removeMin和removeMax的定义是一样的。如果你能理解removeMin和removeMax，那么在这里，这个remove，其实就是，当我们当前要删除的节点，进入第268行的条件以后，我们经过一系列操作，得到了在删除这个节点以后，新的二分搜索树的根为这个successor节点。

具体什么时候挂回这个二分搜索树的，是在243行或者248行的时候。在递归返回的时候，挂回去的。挂给上一层递归调用node节点的node.left或者node.right。

这个删除过程是怎么“挂回去”的，确实理解起来有难度，正是因为这个原因，我在这个课程讲解链表的时候，特意对于递归的微观语意分析，详细阐述了从链表中删除一个节点的递归过程，到底是怎么“挂回去的”，再回顾一下那个小节的内容，然后再回过头看二分搜索树，看看是不是能理解的更清晰？

传送门：5-5小节：https://coding.imooc.com/lesson/207.html#mid=13441

加油！

• 提问者 不务正业的码农 #1

  非常感谢！