老师你好，有个问题是为什么删除这个节点是把node.right=null,而不是把这个node=null

Question

或者说应该同时把node和node.right都置为null

Answer 1

liuyubobobo 2018-08-17 02:32:39

直接给node赋值为空是错误的，是不能够正确删除节点的（试试看？）。

再回忆一下4-5小节（https://coding.imooc.com/lesson/207.html#mid=13448）第2：55我讲的在链表中删除节点的经典问题。将node设置为空，node只是这个方法中的局部变量（一个引用）而已，这个操作无法影响整个链表，只是让node这个引用指向了null而已。所以，我们在链表中删除一个元素，要找到待删除元素的前一个节点，让其next为空，这样才能改变整个链表。同理，在二分搜索树的删除中，我们其实找的是待删除元素的父亲节点，让其right（或者left）为空。

请一定仔细思考这个问题。这不完全是数据结构实现的问题，也是一个很重要的语言机制问题。想通彻了，会对近乎所有编程语言的理解上一个台阶的：）

加油！

• 提问者 hellocp7 #1

  是的。可能因为我本身对引用和指针还没有完全的理解，老是搞混。谢谢老师。我理解了你说的要找到待删除元素的前一个节点，让其next为空。那是否我们在实现删除最小元素也是有两种递归的实现方式，一种是判断node.left.left==null，因为这样我们才能找到待删除节点的父节点，然后用node.left=node.left.right。还有一种就是老师你在这里说的，定义一个宏观语意是返回以node为根的已经删除最小元素后的左子树头一个节点的递归函数，我们就不需要再找到待删除元素的父节点，这样在发现node.left==null时，此时的node就是我们要删除的节点，然后直接返回他的右孩子就行。

• 提问者 hellocp7 #2

  对于之前我说的把node和node.right赋为null的情况，我的意思是在我们已经决定用第二个递归实现方法实现的时候（也就是老师你课上说的方法），我们已经存下来了这个会返回回去的node.right，并且在之后return回去。如果只做这个操作，理论上我们是否也已经删除了这个节点？因为以node为根的左孩子已经指向了我们刚刚返回的待删除节点的右孩子。之后的将待删除节点node.right=null和我说的将待删除节点node置为null是否只是为了防止loitering变量。

• 提问者 hellocp7 #3

  我意识到了我说的把待删除节点node置为null是有问题的。我想表达的是手动回收node指向的那块区域，只是java似乎没有手动回收垃圾的方法。这就make sense了。我懂了。谢谢老师

点开查看后面2条评论