java - 为什么我必须为二叉树的递归插入显式设置左/右 child ？

Question

我只是在玩一棵二叉树，我很好奇为什么第一个实现有效而第二个没有。我在看什么？我认为这是微不足道的，但我仍然想念它。
1:

//just a wrapper around the insertTree method.
public void insertKey(int key){
    
    if(root==null) //a private 'Node' variable.
        root = new Node(key);
    else
        insertTree(key, root);
}

//recursive insert - working
private void insertTree(int key, Node node)
{
    if(key <= node.getKey())
    {
        if(node.left!=null)
            insertTree(key, node.left);
        else
            node.left = new Node(key); //explicitly setting left child
    }
    else
    {
        if(node.right!=null)
            insertTree(key, node.right);
        else
            node.right = new Node(key); //explicitly setting right child
    }
            
}

不起作用的变体:
2:

private void insertTree(int key, Node node)
{  //if node is null, create a new node. Can be either node.left or node.right
       if(node==null)
       {
           node = new Node(key);
           return;
       }
       else
          if(key <= node.getKey())
             insertTree(key, node.left);
          else
             insertTree(key, node.right);
                                
}

Node 只是一个带有 public left, right 的简单类成员(member)及单 int key数据成员。没什么好看的。所以#1 工作得很好，中序遍历产生一个排序的输出。现在，#2 似乎不起作用。根是唯一一个被初始化的，它的左/右 child 继续为空。所以如果我通过了 node.left作为参数，为什么递归方法调用不为其分配新节点？我在这里缺少什么？ Java 是按引用传递的(即引用值)，所以我猜这应该可行，但也许我在这里遗漏了一些菜鸟。

Answer 1

它不起作用的原因是因为 node最后一次递归调用 insertTree 中的变量实际上并不引用与 node.left 相同的内存位置在之前的通话中。调用函数(/method)有效地为堆栈上的所有参数创建新的存储位置，并将参数值复制到那里。

因此，insertTree在您的第二个变体中，只需创建一个新的 Node并将其分配给局部变量 node在那个函数中。该分配不影响其他内存位置。然后它返回，新的 Node永远失去了。

您声明“Java 是通过引用传递的”，但事实并非如此。 Java 按值传递引用。