将节点添加到树中 – 为什么根节点没有被初始化?

huangapple go评论76阅读模式
英文:

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

问题

我已经为向树添加新节点编写了两个函数:一个是公共的,一个是私有的。私有函数是递归的。公共函数调用递归函数。第一个问题:这种做法是否可接受?

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

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

对我来说这非常令人困惑,因为我知道Java是按引用传递的,而不是按值传递的。为什么在调用这些函数后root仍然是null?

控制台输出:

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

I have written two functions for adding a new node to a tree: one public and one private. The private one is recursive. The public one calls the recursive one. First question: Is this acceptable practice?

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

}

Now here is the problem: The root variable does not get initialized. It is declared in the tree class. public Node root;

This is very confusing to me since I am aware that Java is pass-by-reference, not pass-by-value. Why is root null after these functions have been called?

Console output:

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

答案1

得分: 0

当然,从公共方法调用私有方法(甚至递归调用)是没有问题的。
根节点为空,仅仅是因为你正在为 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 架构中为 000000D5098FFA70)。因此,如果你修改了例如 node.left,实际上是在改变地址为 000000D5098FFA70 + 4 处的内存。然而,如果你改变了该地址的值,你将无法再访问该对象。从那一刻起,你只能使用局部变量进行操作。这就是为什么它被称为按值传递。

英文:

Of course there is nothing wrong in calling private method (even recursive) from public method.
Root is null simply because you are assigning new value to node argument, you are not changing object, but you are creating new one.

following

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

will not change argument node in caller. So after calling

addNode(val, root, null, 0);

root stays unchanged (with null value)

Also keep in mind objects are passed by value in Java.

Actually (inside Java) in function you receive only memory address (value) for node (e.g. 000000D5098FFA70 in x64 arch). So if you modify e.g. node.left you are actually changing memory at address 000000D5098FFA70 + 4. However if you change
that address - value - you lose access to this object. And from that moment you are working only with local variable. This is why it is called passed by value.

答案2

得分: 0

如果在Java代码中,一个函数为函数参数赋予了一个新值,这永远不会影响调用者可能传递的变量。你可能对当参数变量被改变时会发生什么感到困惑:例如,如果它是一个对象,并且你为其属性分配了不同的值,那么这个变化对调用者的对象是可见的,因为它确实是同一个对象。但是对参数的简单赋值只会对该局部变量产生影响。

要使其生效,设计你的函数以便返回你提供给它的节点(无论它是否获得了新值)。

还有另一个问题:你目前正在左子树和右子树(如果存在)中都添加一个新节点,这会递归重复。我会假设你试图在二叉搜索树中插入值,因此你应该在哪个子树中选择添加节点。

最后,无需将parentNodeheight作为参数传递,因为你似乎将高度存储在每个节点中,所以你知道新节点的高度必须比其父节点中存储的高度多一(或者当不存在时为0)。

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

private Node addNode(int val, Node node) { 
    if (node == null) {
        return new Node(val, 0, 0);  // 注意:在回溯时将更新高度
    }
    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表示节点在树中的深度。参见树的深度和高度有什么区别?

英文:

If in Java code a function assigns a new value to a function parameter, this never impacts the variable that the caller may have passed as argument. You may have been confused with what happens when a parameter variable is mutated: for instance, if it is an object and you assign a different value to one of its properties, then this change is visible to the caller's object, since it really is the same object. But a plain assignment to a parameter will always have an effect on that local variable only.

To make it work, design your function to return the node that you provided to it (whether it got a new value or not).

There is another issue: you are currently adding a new node in both the left and right subtree (if they exist), and this repeats recursively. I will assume you were trying to insert values in a binary search tree, and so you should choose in which subtree you will add the node.

Finally, it is not needed to pass parentNode or height as argument, since you seem to store the height in each node, and so you know that the new node's height must be one more than the height stored in its parent node (or, when absent, 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 &lt; 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;
}

Finally, the name "height" is a bit misleading here, as this term is supposed to denote the height of the (sub)tree of which the node is the root. But height in this code represents the depth of the node in the tree. See What is the difference between tree depth and height?.

huangapple
  • 本文由 发表于 2020年9月30日 17:25:14
  • 转载请务必保留本文链接:https://go.coder-hub.com/64134605.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定