remove中的一些问题
来源：7-7 基于二分搜索树的映射实现
Ethan_Qjm
2020-04-22
// 从二分搜索树中删除键为key的节点
@Override
public V remove(K key){
Node node = getNode(root, key);
if(node != null){
root = remove(root, key);
return node.value;
}
return null;
}
private Node remove(Node node, K key){
if( node == null )
return null;
........
老师这里的代码，如果在上面的remove中已经判断node是否为空，那么进入递归函数的条件是node不为空，为什么递归函数的其中一个终止条件还要判断新的node是否为空呢？这样不是永远不会有if(node == null)的情况出现吗？
写回答
1回答
-
liuyubobobo
2020-04-22
上面的 node 和下面的 node 不是一个东西。
上面的 node 是我们先找到待删除节点对应的 node，我们要确认这个待删除节点是存在的，才能进行删除。可能换个名字，叫 delNode，更清晰，是待删除节点。
但下面的 node，是函数的一个参数名，这个参数名 node 所对应的节点，是跟着我们递归过程传的参数不同而在改变的。比如，在初始点用的时候，我们调用的是 remove(root, key)，那么进入这个函数，这个 node 指的是 root。
下面函数的这个 node 在怎么变化，是理解这个删除过程的关键。我建议你实际创建一棵树，3 层就可以，然后删除一个叶子节点，使用单步跟踪的方式实际看一下，递归的 remove 函数中，node 是在怎么变化的。结合这个课程中我讲链表的递归删除的微观操作，理解一下这个过程。
加油！：）
072020-05-20
相似问题