1回答

liuyubobobo

2018-07-24

已采纳

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

以下阐述基于我的课程代码：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

1

不务正业的码农

非常感谢！

2018-08-02

共1条回复