将节点添加到树 - 为什么根没有得到初始化？

Question

我写了两个用于向树中添加新节点的函数：一个 public 和一个 private。私有的是递归的。 public 一个调用递归一个。第一个问题：这是可以接受的做法吗？

public void addNode(int val) {
    addNode(val, root, null, 0);
    System.out.println("Root is null: " + (root == null));
}

private void addNode(int val, Node node, Node parent,int height) { 
    
    if(node == null) {
        node = new Node(val, height, 0);
        System.out.println("is new node equal to root?"+(node == root));
        System.out.println("Added node on height: " + node.getHeight());
        return;
    }
        height++;
        addNode(val, node.left, node, height);
        addNode(val, node.right, node, height);

}

现在问题来了：根变量没有被初始化。它在树 class 中声明。 public Node root;

这让我很困惑，因为我知道 Java 是按引用传递，而不是按值传递。为什么调用这些函数后root为null？

控制台输出：

is new node equal to root?false
Added node on height: 0
Root is null: true

Answer 1

从public方法中调用私有方法（甚至递归）当然没有错。 Root 为 null 仅仅是因为您正在为 node 参数分配新值，您不是在更改对象，而是在创建新对象。

正在关注

private void addNode(int val, Node node, Node parent,int height) {
   ...
   node = new Node(val, height, 0);

不会更改调用方的参数 node。所以调用后

addNode(val, root, null, 0);

root 保持不变（null 值）

还要记住对象 在 Java 中按值传递。

实际上（在 Java 中）在函数中您只收到 node 的内存地址（值）（例如 x64 arch 中的 000000D5098FFA70）。所以如果你修改例如node.left 您实际上是在更改地址 000000D5098FFA70 + 4 处的内存。但是，如果你改变该地址 - 值 - 您无法访问该对象。从那一刻起，您只使用局部变量。这就是为什么它被称为按值传递。

Answer 2

如果在 Java 代码中函数为函数参数分配新值，这永远不会影响调用者可能已作为参数传递的变量。您可能对参数变量突变时发生的情况感到困惑：例如，如果它是一个对象并且您为它的一个属性分配了不同的值，那么这种变化是可见的到调用者的对象，因为它确实是同一个对象。但是对参数的简单赋值将始终只对该局部变量产生影响。

为了让它工作，将你的函数设计为 return 你提供给它的节点（无论它是否有新值）。

还有一个问题：您当前正在向左右子树（如果它们存在）中添加一个新节点，并且递归重复。我假设您正在尝试在二叉 search 树中插入值，因此您应该选择您将在哪个子树中添加节点。

最后，不需要传递parentNode或height作为参数，因为你似乎在每个节点中存储了高度，所以你知道新节点的高度必须是一个超过其父节点中存储的高度（或者，如果不存在，则为 0）。

public void addNode(int val) {
    root = addNode(val, root);
}

private void addNode(int val, Node node) { 
    if (node == null) {
        return new Node(val, 0, 0);  // NB: height will be updated when backtracking
    }
    if (val < node.val) {
       node.left = addNode(val, node.left);
       node.left.height = node.height + 1;
    } else {
       node.right = addNode(val, node.right);
       node.right.height = node.height + 1;
    }
    return node;
}

最后，名称“高度”在这里有点误导，因为这个术语应该表示节点是根的（子）树的高度。但是这段代码中的height表示树中节点的depth。参见 What is the difference between tree depth and height?。

将节点添加到树 - 为什么根没有得到初始化？

Adding node to tree - Why is the root not getting initialized?

java

tree

recursion

pass-by-reference

nodes