方法不修改通过的原始节点(Java)

Question

我创建了一个程序，将 key/value 对存储到二叉搜索树中。 class 包含一个根指针，用于跟踪树的根节点。 This.root 在构造函数中设置为 null。

以下方法 put(K, V) 尝试将新的 key/value 对插入树中。如果键已经存在于树中，方法 returns 与该键对应的现有值。如果不是，则通过辅助方法 put(K, V, BNode) 插入 key/value 对。 ***通常我只会 return this.put(...)，但在这个代码片段中我将它替换为 return null 以便我可以在它之前添加一个打印语句来检查根节点是否实际被修改

我的程序无法插入第一个 key/value 对。我将 print 语句放在我的 insert 和 put 方法中以检查它们是否正常工作。在这种情况下，curr（只是 this.root）在插入之前为 null，正如预期的那样，因为我们从一棵空树开始。我创建一个新节点，并在 insert() 中调用 return 这个节点。现在 curr 指向这个创建的节点。打印语句 "curr key" + curr.key 打印出正确的密钥，表明此节点创建成功。但是当我尝试打印 this.root.key 时出现 NullPointerException。第二种方法中修改curr不应该也修改了第一种方法中的this.root吗？

//this.root is the root node of this binary search tree
public V put(K key, V val) {
    System.out.println("put reached");
    this.put(key, val, this.root); // original return statement
    System.out.println("root key: " + this.root.key); // checks if root node was modified
// THIS print statement returns a NullPointerException

    return null; // dummy return statement
}

private V put(K key, V val, BNode curr) {
    V originalValue = this.get(key, curr); // returns null if key does not exist
//else returns corresponding key value

    if (originalValue == null) {
        curr = this.insert(key, val, curr); // helper method which uses recursion to insert 
        System.out.println("curr key " + curr.key); // checks if curr was modified
        this.size++;
        this.state++;
    }

    return originalValue;
}

private BNode insert(K newKey, V newValue, BNode n) {
    if (n == null) {
        return new BNode(newKey, newValue); 
    } else if (newKey.compareTo(n.key) < 0) {
        n.left = this.insert(newKey, newValue, n.left);
    } else {
        n.right = this.insert(newKey, newValue, n.right);
    }

    return n;
}

Answer 1

Shouldnt modification of curr in the second method have also modified this.root in the first method?

简短回答：否。这是因为 root 的值永远不会改变。

这应该有助于澄清问题，并解释为什么这比我能做的更好：Is Java "pass-by-reference" or "pass-by-value"?。

简而言之，如果您想将一个新节点指定为根节点，您需要明确地执行此操作，而不是尝试更改传递给该方法的值，因为这只会更改 curr 指向的内容。

Answer 2

感谢 trappski 的快速回复

如果 Java 确实是通过引用传递，那么我的程序中一直存在的问题现在就更有意义了。但是，如果只修改一个重复的 BNode，而不是作为树的一部分的原始 BNode，为什么像这个这样的递归方法会起作用？

private BNode deleteMin(BNode n) {
    if (n.left == null) {
        return n.right;
    }

    n.left = this.deleteMin(n.left);
    return n;
}

方法不修改通过的原始节点(Java)

Method does not modify original node passed through (Java)

java

tree