2

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

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 只是一个具有公共left, right成员和单个int key数据成员的简单类。没有什么花哨。所以#1 工作得很好，中序遍历产生了一个排序的输出。现在，#2 似乎不起作用。根是唯一被初始化的，它的左/右子节点继续为空。所以如果我确实node.left作为参数传递，为什么递归方法调用不为其分配一个新节点？我在这里想念什么？Java 是通过引用传递的（即引用值），所以我猜这应该可行，但也许我在这里遗漏了一些菜鸟。

4

2 回答 2

3

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

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

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

于 2012-12-31T03:02:49.470 回答
0

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

于 2012-12-31T17:55:54.010 回答