向树添加节点-为什么根没有被初始化？

Question

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

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);

}

现在问题来了：根变量没有初始化。它在树类中声明<代码>公共节点根

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

控制台输出：

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

Answer 1

当然，从公共方法调用私有方法（甚至递归）并没有什么错。Root为null仅仅是因为您正在为节点参数分配新值，您并没有更改对象，而是在创建新对象。

以下内容

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

不会更改调用方中的参数节点

addNode(val, root, null, 0);

root保持不变（使用null值）

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

实际上（Java）在函数中，您只收到节点的内存地址（值）（例如x64 arch中的000000D5098FFA70）。因此，如果您修改例如node.left，您实际上是在地址0000D5098FFA70 4处更改内存。然而，如果您更改了地址值，您将失去对该对象的访问权限。从那时起，您只能使用局部变量。这就是为什么它被称为按值传递。

Answer 2

如果在Java代码中，一个函数为一个函数参数分配了一个新的值，这永远不会影响调用者作为参数传递的变量。您可能对参数变量发生变化时会发生什么感到困惑：例如，如果它是一个对象，并且您为它的一个属性指定了不同的值，那么调用方的对象就可以看到这种变化，因为它实际上是同一个对象。但对参数的简单赋值总是只对局部变量有影响。

为了让它工作，设计你的函数来返回你提供给它的节点（不管它是否有新的值）。

还有另一个问题：您当前正在左子树和右子树（如果存在）中添加一个新节点，这会递归重复。我假设您试图在二叉搜索树中插入值，因此您应该选择在哪个子树中添加节点。

最后，不需要将父母节点或高度作为参数传递，因为您似乎将高度存储在每个节点中，因此您知道新节点的高度必须比其父节点中存储的高度多一个（或者，如果不存在，则为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”有点误导，因为这个术语应该表示节点为根的（子）树的高度。但此代码中的height表示节点在树中的深度。看看树的深度和高度有什么区别？。