Блог

Это в основном то, что делает рекурсия, она добавляет 1 каждый раз, когда вызывается countNodes, когда он переходит к дочернему узлу ( int count = 1; ) и завершается, когда он пытается перейти к следующему дочернему элементу конечного узла (поскольку у листа нет дочерних элементов). Каждый узел рекурсивно вызывает countNodes для каждого из своих левых и правых дочерних элементов, и количество медленно увеличивается и поднимается вверх.

Попробуйте посмотреть на это так, где 1 добавляется для каждого узла и 0 для несуществующего узла, где рекурсия останавливается:

           1
        /   
       1     1
      /    / 
     1   0 0   0
    / 
   0   0
 

Каждый из 1 суммируется, при этом родительский узел (вызывающая функция на каждом уровне рекурсии) добавляет 1 left_size right_size и возвращает этот результат. Поэтому значения, возвращаемые на каждом этапе, будут:

           4
        /   
       2     1
      /    / 
     1   0 0   0
    / 
   0   0
 

Я не уверен, что это сделало его более понятным, но я надеюсь, что это так.

Допустим, вы вызываете countNodes(myTree); . Предполагая myTree , что это не null , countNodes в конечном итоге будет выполнено count = countNodes(root->left); , где root есть myTree . Он повторно вводит вашу countNodes функцию со всем корнем дерева в root->left (который есть myTree->left ). Затем логика повторяется; если нет root->left , то функция возвращает 0. В противном случае он в конечном итоге вызовет count = countNodes(root->left); снова, но на этот раз root на самом деле будет myTree->left . Таким образом, это будет учитываться myTree->left->left . Позже он делает то же самое с нужными узлами.

В этом прелесть рекурсивных алгоритмов. Функция определяется для текущего узла и его дочерних элементов. Вам нужно только убедить себя в том, что текущий вызов является правильным, если рекурсивные вызовы левого и правого дочерних элементов являются правильными. Точно такие же рассуждения применимы к дочерним элементам и их дочерним элементам и так далее … все будет просто работать.

Он будет начинаться с root-> left-> (subnode-> left) и т. Д., Пока эта ветвь не вернет 0, например, если это не фактический узел (лист в дереве);

Затем самый глубокий узел проверит наличие root-> right и повторит ту же процедуру. Попробуйте визуализировать это с помощью небольшого дерева :

Итак, в этом случае ваша функция будет идти A-> D-> B, тогда все правильные узлы вернут 0, и вы получите последнее 1 от вашего узла C.

Реализация алгоритма, которую вы пишете, является исчерпывающей. Он посещает все дерево.

Если дерево пустое, счетчик равен нулю. Если нет, мы получаем левый узел, назовем его L и добавим 1 к нашему счету.

Поскольку доказано, что поддерево дерева само по себе является деревом, мы снова выполняем тот же алгоритм для дерева, у которого L в качестве корня.

Теперь мы делаем это для дерева, у которого корневой правый узел является корневым.

Теперь … это действительно работает.

Поддерево дерева — это дерево, также для пустых или одиночных узлов. Вы должны посмотреть на определение дерева.

Вы можете доказать это с помощью математической индукции и сформулировать свою проблему в терминах индуктивного рассуждения. Рекурсивные алгоритмы часто используют структуру, очень похожую на индуктивные рассуждения.

Хитрость с рекурсивными функциями заключается в том, что существует базовый вариант и индуктивный шаг, точно так же, как математическая индукция.

Базовый случай — это то, как ваш рекурсивный алгоритм знает, что нужно остановиться. В этом случае это if (root == NULL) — этот узел не представляет дерево. Эта строка выполняется на каждом отдельном узле вашего двоичного дерева, даже если она вызывает каждый из root них одновременно. Это значение равно false для всех узлов дерева, но когда вы начнете вызывать рекурсивную процедуру для дочерних элементов конечных узлов — а это все NULL , — тогда оно вернется 0 как количество узлов.

Индуктивный шаг — это то, как ваш рекурсивный алгоритм переходит из одного решенного состояния в следующее нерешенное состояние путем преобразования нерешенной проблемы в (одну или несколько) уже решенных проблем. Вашему алгоритму необходимо подсчитать количество узлов в дереве; вам нужен 1 текущий узел, и тогда у вас есть две более простые проблемы — количество узлов в дереве слева и количество узлов в дереве справа. Получите оба из них, добавьте их вместе, добавьте 1 для текущего узла и верните это как количество узлов в этом дереве.

Эта концепция действительно является фундаментальной для многих алгоритмов в информатике, поэтому ее стоит изучить, пока вы полностью ее не поймете. См. Также быструю сортировку, последовательность Фибонокки.

Подумайте, что программа идет первой в самых глубоких ветвях. Затем он возвращается назад, возвращая номер счетчика своему предыдущему члену.

     A
   / 
  B   C
 /    
D   E   F
 

Итак, сначала программа выполняется до

 count  = countNodes(root->left);
 

Он приостанавливает то, что было сделано до сих пор (по-видимому, ничего особенного), и переходит в B. То же самое происходит там, и оно переходит в D. В D он делает то же самое. Однако здесь у нас особый случай. Программа видит в начале строки

 if ( root == NULL )
 

что несуществующий левый дочерний элемент D действительно равен NULL . Поэтому вы получаете обратно 0.
Затем мы возвращаемся к тому, где мы остановились в прошлый раз, и продолжаем так. В прошлый раз мы были на B, поэтому мы продолжаем проходить мимо строки

 count  = countNodes(root->left);
 

и запустите следующую строку

 count  = countNodes(root->right);
 

Это продолжается до тех пор, пока вы не вернетесь к A. Но в точке A мы снова остановились сразу после поиска левого конца A. Поэтому мы продолжаем с правого выхода. Как только мы закончим проходить всю эту ветку, мы вернемся к A.

На данный момент у нас не осталось незавершенных дел (пауз), поэтому мы просто возвращаем количество, которое мы собрали в ходе всего этого процесса.

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

Нарисуйте все дерево, затем назначьте 1 для всех конечных узлов (конечные узлы находятся на уровне N). После этого вы должны быть в состоянии вычислить количество узлов, которое генерируется каждым узлом на более высоком уровне (N-1), просто суммируя: 1 1, если у узла есть два дочерних элемента, или 1, если у узла есть только один дочерний элемент. Таким образом, для каждого узла на уровне N-1 присвоите значение 1 сумма (слева, справа). После этого вы должны быть в состоянии вычислить количество узлов всего дерева. Рекурсия, которую вы опубликовали, сделайте именно это.

http://www.jargon.net/jargonfile/r/recursion.html

ОБНОВЛЕНИЕ: дело в том, что и структура данных, и программа являются рекурсивными.

• для структуры данных это означает: поддерево также является деревом.
• для кода это означает: подсчет дерева: = подсчет поддеревьев (и добавление одного)