Рекурсивный метод для бинтинга дерева

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

Как указал @ Джон МакКлейн , аргумент Integer нельзя передать ссылкой , только значением .

Но нет необходимости в частном вспомогательном методе, вы можете просто упростить все это до одного метода:

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

Answer 2

Проблема в том, что классы-оболочки неизменны в Java.cardinalidade здесь является просто параметром contaNosPrivado и, к сожалению, не может действовать как аргумент , как другие параметры типа объекта, т. Е. Эта локальная ссылка не может изменять внутренние поля объекта, на который ссылается исходная ссылка.Любое изменение в нем влияет только на то, как оно влияет на любую примитивную локальную переменную.

Что именно происходит внутри вашего contaNosPrivado:

1. При вызове оно действительно предоставляетсяссылка на объект Integer.Эта ссылка назначена локальной переменной с именем cardinalidade.

2. В этой строке:

   cardinalidade=cardinalidade+1;
   

   этот объект сначала распаковывается в примитивную переменную int, эта переменнаявпоследствии увеличивается, и, наконец, результат перезаписывается в новый Integer объект, который затем присваивается cardinalidade.Невозможно «увеличить» исходный объект, даже если вы используете оператор приращения:

   cardinalidade++;
   

3. Любая дальнейшая обработка применяется к вновь созданному объекту Integer и не влияет на ссылкупередано в contaNosPrivado.

Чтобы достичь своих целей, используйте что-то вроде этого:

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