Как эта функция считает количество узлов в дереве?

Question

Функция для подсчета количества узлов в дереве.

int count(node *t)
{    
    int i;  
    if (t == NULL)         
        return(0);  
    i = 1 + count(t->left) + count(t->right); // recursion occurs address of left node is passed and 
    return(i);                                // continue to pass until whole left node
}                                             // is traversed and the value of t is
                                              // NULL and 0 is returned same for right node counting
                                              // i = 1 + 0 + 0 = 1

Как подсчитывается количество узлов?

Answer 1

Чтобы понять рекурсию, вы должны сначала понять рекурсию.

Answer 2

Это рекурсивная реализация подсчета узлов дерева.Он вызывается для корневого узла и возвращает «один плюс количество узлов в левом поддереве плюс количество узлов в правом поддереве», что выполняется рекурсивно, пока не достигнет конечных узлов.

Answer 3

Во-первых, вы сами попробовали?

По сути, это добавляет 1 для каждого ненулевого узла.Это примерно так: 1 + number_of_nodes_to_the_left + number_of_nodes_to_the_right.Это расширяется до: 1+(1+number_of_nodes_to_the_left_in_left+number_of_nodes_to_the_right_in_left) + (1+number_of_nodes_to_the_left_in_right + number_of_nodes_to_the_right_in_right).Продолжайте расширяться, и вы увидите, что это в основном 1 + 1 + 1 +.... для каждого ненулевого узла в дереве.

EDIT : чтобы лучше это проиллюстрировать, рассмотрим следующее дерево:

     Node0
       |
(left) |  (right)
Node1 _|_ Node2
            |
     (left) |  (right)
     Node3 _|_ Node4

Когда вы делаете int node_count = count(Node0), поскольку Node0 не равен NULL, он переходит к оператору return, который: return 1 + count(left) + count(right).Вы должны понимать основную вещь, что сама операция в вашей рекурсивной функции происходит одна за другой. Другими словами, операция count(right) не происходит до тех пор, пока операция count(left) не будет завершена.Теперь взгляните на оператор return, который у вас есть, и переведите его в терминах приведенного выше дерева.Это было бы 1+count(Node1)+count(Node2).Так что count(Node2) не рассчитывается до того, как count(Node1) закончится.Таким образом, для count(Node1) функция count вызывается (снова) с Node1 в качестве аргумента.Итак, давайте пока что забудем о полу-вычисленном выражении 1+count(Node1)+count(Node2) (мы вернемся к нему позже).

Теперь для count(Node1) Node1 не равен NULL и, следовательно, переходит к возвращениюзаявление.Это будет (снова) 1+count(left)+count(right).Но подождите, Node1 не имеет левого и правого узлов.Таким образом, когда count(left) вызывается с аргументом NULL, он возвращает 0, и то же самое происходит для count(right).Таким образом, выражение для count(Node1) становится 1 + 0 + 0.Больше нет функций count, вызываемых для Node1, и поэтому он возвращается к своему исходному вызывающему , который был оператором возврата count(Node0).

, так как мы имеемcount(Node1) разобрался, давайте заменим его в операторе возврата count(Node0).Теперь это становится 1 + (1 + 0 + 0) + count(Node2).

Теперь я собираюсь сделать это немного быстрее.Поскольку Node2 имеет двух дочерних элементов, оператор возврата Node2 будет 1 + count(Node3) + count(Node4).Так же, как это было для Node1, count(Node3) и count(Node4) будут возвращать каждый 1 + 0 + 0, превращая оператор возврата count(Node2) в 1 + (1 + 0 + 0) + (1 + 0 + 0).

Теперь, когда count(Node2) полностью вычислендавайте вернемся к исходному вызывающему count(Node2), что составляет 1 + (1 + 0 + 0) + count(Node2).Замените то, что мы получили от count(Node2), и мы получим 1 + (1+0+0) + (1 + (1+0+0) + (1+0+0)).Сложите это, и мы получим значение 5. Это значение возвращается той функции, которая вызвала count(Node0), например, операторы int node_count = count(Node0) и node_count будут иметь значение 5.

Answer 4

Общее количество включает текущий / корневой узел плюс количество в левой ветви плюс количество в правой ветви.Ваш страж - это NULL, что означает, что вы достигли конечного узла любой ветви, которую вы сейчас считаете.Тогда вы расслабляетесь назад.Рекурсия:)

Answer 5

Рассмотрим эти деревья:

Дерево без узлов (то есть указатель NULL) - возвращает 0

Дерево с одним узлом, корнем. Это будет называть:

 i=1+count(t->left)+count(t->right);

с левым и правым значением NULL, и поэтому вернет 1 + 0 + 0

Дерево с корнем и одним правым листом

 i=1+count(t->left)+count(t->right);

вернет 1 для корня, 0 для дерева с корнем слева (по правилам выше) и 1 для дерева с корнем справа (по правилам выше), что равно 1 + 0 + 1

и т. Д.