当只引用它的副本时，我的二进制搜索树的顶部节点是如何更新的

Question

这个问题也适用于各种链表方法。所以，当我有一个方法：

public void insert(String key) 
{
if(top == null) 
{
top = new Node(key);

}else {
Node newNode = new Node(key);
Node rover = top;
Node prev = top;
boolean wentLeft = true;
while(rover != null) 
{
if (rover.getName().compareTo(key) < 0)
{
prev = rover;
rover = rover.getRight();
wentLeft = false;
}else {
wentLeft = true;
prev = rover;
rover = rover.getLeft();
}

}

if(wentLeft == true) 
{
prev.setLeft(newNode);
}else {
prev.setRight(newNode);
}
}
nElems++;

}

二进制搜索树的顶部及其子级是如何更新的，尽管在方法中没有直接设置？

我知道这可能与浅层复制有关，像rover/prev这样的东西仍然引用内存中的top，但我仍然不太明白

尽管我觉得我在概念层面上理解了链表和二进制搜索树，但如果不理解这一点，我会觉得继续使用它们很不舒服。

Answer 1

没有进行任何复制。当您指定prev=top时，这只会创建对与top相同对象的另一个引用，而不是副本。

代码之所以有效，是因为节点是逐个插入的。调用prev.setLeft/setRight时，prev已在树中，因为它以前已插入。所以prev已经在树中了，也就是说，prev的父级在顶部，或者prev父级的父级，你就知道了。因此，当new_node成为prev的子级时，它就成为树的一部分。

这就是链接列表和树如此有用的原因。插入图元时，只需要建立一个连接。