理解 Java 中的引用； BST 的 addNode() 函数没有正常运行

Question

我想了解为什么我的第一个 addToTree() 实现不起作用，但第二个实现。我评论了不同的行：

public static void addToTree(Node n, int value){ //return type is void
    if (n != null){
        if (n.val >= value){
            addToTree(n.left, value);
        } else { 
            addToTree(n.right, value);
        }
    } else {
        n = new Node(value);
    }
}

这是实际有效的实现：

public static Node addToTree(Node n, int value){ //return type is Node
    if (n != null){
        if (n.val >= value){
            n.left = addToTree(n.left, value); //sets n.left with the return value
        } else { 
            n.right = addToTree(n.right, value); //sets n.right with the return value
        }
    } else {
        n = new Node(value);
        return n; //returns the new node after creating (adding) it
    }
    return n;
}

为什么我必须将 n.right 和 n.left 设置为 addToTree() 的 return 值？我不明白为什么 void 函数在这里不起作用以及为什么必须 returned 新节点。这是否解释了 Java 的 'Pass by value' 性质？调用addToTree(n.left, value)的时候，不是传递给n.left的引用吗？

Answer 1

简短回答：Java 是按值传递，而不是按引用传递

长答案：由于 Java 是按值传递的，因此在方法中传递的任何值都将首先复制到内存中的不同位置，然后将该位置传递给该方法。并且当方法更改值时，新（即复制）位置的值将更改，而原始副本保持原样。

在原始值的情况下，只有值被复制到新位置，但在传递给方法的引用类型值的情况下也会被复制，但由于它们是对其他位置的引用，因此该位置该引用指向的内容仍然相同。

在你的例子中，当你在下一次递归调用中传递 n.left/right 时，引用被复制到不同的位置，最后一次递归调用在那个不同的位置写入 n=new Node(value);，但实际节点。left/right 保持不变。

当您看到引用类型作为按值传递时，我知道这一切令人困惑。理解为什么将两个整数传递给方法进行交换不起作用，但传递两个元素的数组并交换数组中的值在 Java 中起作用。这个概念基本上是一样的。查看此 link 了解更多信息：Java: Why does this swap method not work?

Answer 2

第一个实现的问题是您创建的新节点被分配给 n 但随后 n 立即超出范围并且对该节点的引用丢失。

当您声明方法参数 Node n 时，您正在定义类型 Node 的变量 n，其作用域仅限于此方法。当您调用该方法并传递像 addToTree( myNode, myValue ) 这样的参数时，方法内部的变量 n 被赋值 myNode，就像赋值 n = myNode 一样。在您的方法结束时，您将一个新值分配给 n。这类似于做这样的事情：

Node myNode = new Node( 7 );
Node n = myNode; // Now n points to the same object as myNode
...
n = new Node( 10 ); // Now n points to a different object

此时您是否希望 myNode 的值为 10？不，因为这两个变量指向不同的对象。在您的方法中，变量 n 被分配了一个带有 value 的新节点，但是一旦您的方法结束，n 的范围就会结束，并且对新节点的引用也会消失。

所以基本上你创建了一个新节点然后你立即失去了它。您必须从您的方法中 return 该新节点，以便有人可以将其保存在树中的某个位置。在您更改的其他行中，您正在将新节点保存在树中，例如n.left = addToTree( n.left, value )。这将获取将成为新创建节点的方法调用的结果，并将其存储在节点 n.

的左侧

理解 Java 中的引用； BST 的 addNode() 函数没有正常运行

Understanding references in Java; addNode() function for BST is not behaving as it should

java

data-structures

binary-search-tree