Понимание двоичного дерева поиска

Question

У меня проблемы с пониманием того, как этот метод дерева двоичного поиска подсчитывает узлы, я просмотрел много примеров в Интернете, однако не могу найти пример, который бы точно объяснил, что происходит.

Вот пример:

public int nodes() {
    int leftNodes = 0;

    if (left != null) {
        leftNodes = left.nodes();
    }
    int rightNodes = 0;

    if (right != null) {
        rightNodes = right.nodes();
    }
    return leftNodes + rightNodes + 1;
}

Вот как я понимаю процесс этого метода, и, возможно, кто-то может помочь мне понять, где я ошибаюсь.

1. Метод вызывается извнесебя из объекта BTS;"tree.nodes () и т. д.".
2. int leftNodes объявляется и устанавливается равным 0.
3. Если есть левый узел (предположим, что он есть), тогда будет присвоено значение leftNodesк возвращаемому значению вызова узла ();
4. Рекурсивный вызов снова пройдет через метод узлов, снова присвоив leftNodes ноль.

Так что я не делаюпонять, где переменная leftNodes увеличивается?Кажется, что он просто повторяется через метод снова, но значение не меняется, и, как я вижу, leftNodes и rightNodes всегда будут равны 0.

Я нашел другой пример подсчета BTS, этот с использованием C ++

int CountNodes(node*root)
{
if(root==NULL)
    return 0;
if(root->left!=NULL)
{
    n=n+1;
    n=CountNodes(root->left);
}
if(root->right!=NULL)
{
    n=n+1;
    n=CountNodes(root->right);
}
return n;
}

Мне гораздо проще следовать этому методу, так как n явно увеличивается каждый раз, когда обнаруживается узел.

Мой вопрос заключается в том, как увеличивается значение leftNodes / rightNodes в рекурсивевызов?

Answer 1

Это базовая реализация inorder traversal.Для каждого узла он переходит к левому дочернему элементу до тех пор, пока не останется левого дочернего элемента (из-за рекурсии думайте, как при каждом посещении узла он помещается в стек).Затем он повторяет ту же процедуру для вершины стека до тех пор, пока в стеке не останется никакого элемента (опять же обратите внимание, что стек используется для упрощения операций по сравнению с рекурсией).При этом он в основном увеличивает общую сумму на единицу для каждого посещаемого узла.

Answer 2

Переменные leftNodes и rightNodes являются локальными для метода nodes(), что означает, что для каждого вызова метода существует различный экземпляр этих переменных.

Поэтому, когда вы вызываете рекурсивно,метод (например, left.nodes()), значение leftNodes является одинаковым до и после рекурсивного вызова, потому что он (вызов) будет иметь один экземпляр leftNodes (и rightNodes).

Answer 3

Вы должны подумать о конце рекурсии.

Предположим, у вас есть один узел без дочерних элементов.

И left, и right будут null, поэтомуВы не будете делать рекурсивные вызовы.

Вы вернете

leftNodes + rightNodes + 1; // 0 + 0 + 1 == 1

Теперь предположим, что у вас есть простое дерево, состоящее из корня, левого и правого дочерних элементов.

Когда вы вызываете nodes() для корня этого дерева, оба значения left и right не равны нулю, поэтому мы будем называть left.nodes() и right.nodes().Поскольку оба левых и правых потомка являются конечными узлами (т. Е. У них нет дочерних узлов), рекурсивные вызовы для обоих вернут 1, как объяснено выше.

Поэтому, когда рекурсивные вызовы вернутся, мы вернемся

leftNodes + rightNodes + 1; // 1 + 1 + 1 == 3

- количество узлов в нашем дереве.