java - 二叉树节点计数的递归方法

Question

好吧，所以我必须创建一个递归方法来计算树中的节点，我这样做了(变量名称是葡萄牙语，抱歉):

public int contaNos(Arvbin r) {
        Integer cardinalidade = 0;
        contaNosPrivado(r, cardinalidade);
        return cardinalidade;
}
private void contaNosPrivado(Arvbin r, Integer cardinalidade) {
        if (r==null) {
            return;
        }
        cardinalidade=cardinalidade+1;
        contaNosPrivado(r.esq, cardinalidade);
        contaNosPrivado(r.dir, cardinalidade);
        return;
}

Arvbin 是二叉树，esq 和 dir 是对树分支的左右引用。

我认为这会起作用，但由于某种原因，当我尝试运行它时，它返回 0。我使用了一些调试，我认为问题是当方法完成并返回到原始状态时非递归的，cardinalidade 变量设置为 0。我不确定是否是因为自动装箱弄乱了我的 Integer 并将其转换为 int，然后当我调用该方法时，它会传递该值的副本而不是对现有对象的引用，我不知道如何修复它。如果有人可以提供帮助，我将不胜感激

Answer 1

问题是 wrapper classes are immutable在 java 。 cardinalidade 只是这里 contaNosPrivado 的一个参数，不幸的是，它不能充当argument与其他对象类型参数一样，即此本地引用不能更改初始引用引用的对象的内部字段。对它的任何更改只会影响它，就像影响任何原始局部变量一样。

What exactly happens inside your contaNosPrivado:

1. On invocation, it is indeed supplied a reference to an Integer object. This reference is assigned to a local variable named cardinalidade.

2. In this line:

   cardinalidade=cardinalidade+1;
   

   this object is first unboxed to a primitive int variable, this variable is incremented afterwards, and finally the result is reboxed into a new Integer object which is then assigned to cardinalidade. There is no way to 'increment' original object, even if you use the increment operator:

   cardinalidade++;
   

3. Any further processing applies to the newly created Integer object and doesn't affect the reference passed to contaNosPrivado.

要实现您的目标，请使用类似以下内容:

static int contaNosPrivado(Arvbin r) {
    if (r == null)
        return 1;
    else
        return contaNosPrivado(r.esc) + contaNosPrivado(r.dir);
}