为什么必须为二叉树的递归插入显式设置左/右子级？

Question

我只是在玩一个二叉树，我很好奇为什么第一个实现有效，而第二个没有。我忽略了什么？我觉得这很琐碎，但我还是很怀念。

//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
    }
            
}

不起作用的变体：

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只是一个简单的类，包含publicleft、right成员和一个int-key数据成员。没什么特别的。所以#1工作得很好，按序遍历产生一个排序的输出。现在#2似乎不起作用了。根是唯一被初始化的根，其左/右子级继续为空。所以如果我通过节点。左作为参数，为什么递归方法调用不为其分配新节点？我错过了什么？Java是通过引用传递的（即引用的值），所以我猜这应该是可行的，但也许我在这里遗漏了什么。

Answer 1

您不应该使用递归向二叉树添加元素。递归涉及昂贵的隐式堆栈。只需迭代即可找到添加节点的正确位置。另外，当你使用迭代时，你不需要两种方法来完成这项工作——一种就足够了。请看以下非常简单的代码：http://www.geekviewpoint.com/java/bst/add

Answer 2

它不起作用的原因是，对insertTree的上一次递归调用中的node变量实际上并没有引用与节点相同的内存位置。在前面的通话中向左。调用函数（/method）可以有效地为堆栈上的所有参数创建新的存储位置，并在那里复制参数值。

因此，在第二个变量中，insertTree只需创建一个新的节点，并将其分配给该函数中的局部变量节点。该赋值不影响其他内存位置。然后它返回，新的节点将永远丢失。

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