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

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 是树分支的左右引用。

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

Answer 1

问题是 wrapper classes are immutable in Java. cardinalidade is just a parameter of contaNosPrivado here and, unfortunately, cannot act as an argument 像其他对象类型参数一样，即这个局部引用不能改变初始引用引用的对象的内部字段。对它的任何更改只会影响它影响任何原始局部变量的方式。

What exactly happens inside your contaNosPrivado:
On invocation, it is indeed supplied a reference to an Integer object. This reference is assigned to a local variable named cardinalidade.
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++;
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);
}

Answer 2

正如 @John McClane 所指出的，您不能通过 reference 传递 Integer 参数，只能通过 value.

但也不需要私有辅助方法，您可以将其全部简化为一个方法：

public int countLeaves( BinaryTreeNode n )
{
    return n == null? 0 : ( countLeaves( n.rightLeaf ) + countLeaves( n.leftLeaf ) );
}

或者（原谅我可怜的葡萄牙语）：

public int contaNos( Arvbin r )
{
    return r == null? 0 : ( contaNos( r.esq ) + contaNos( r.dir ) );
}

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

Recursive method for binary tree node couting

java

recursion

binary-tree