Подсчет с рекурсией в двоичных деревьях путают меня

Question

Я стараюсь как можно больше узнать о древе и их алгоритмах. И похоже, что я не могу понять, как работает рекурсия, когда я хочу что-то считать в двоичном дереве. Например, если я хочу подсчитывать узлы или листья или что-то еще. Когда я смотрю в решении, я не понимаю, как увеличивается счетчик и т. Д. Я могу вспомнить решение для этой конкретной проблемы, но когда у меня возникает другая проблема, которая включает подсчет, я не знаю, как начать свою функцию.

У вас есть совет по поводу моей проблемы? Как вы узнали разные алгоритмы подсчета с рекурсией. Я прекрасно понимаю каждое итеративное решение, и я знаю, как его использовать.

Заранее спасибо за ваш ответ

Answer 1

Для подсчета что-то в виде двоичного дерева, его рекурсивное определение приходит в довольно удобно:

Дерево состоит из трех элементов: узел N, который является корнем , поддерево L, которое является самим деревом и поддеревом R, которое также является деревом.

Используя это определение, мы можем, например, сосчитать листья дерева следующим образом:
Число листьев дерева

• 0, если дерево пусто (N является null)
• 1, если оба L и R пустые
• количество листьев в L и R иначе

Основная идея заключается в том, что мы можем использовать свойство, что отпуск не имеет детей (оба L и R пустые) и тот факт, что пустое дерево не имеет листьев, как базовый случай. С этой точки мы можем просто сказать, что дерево имеет либо одно из вышеуказанных свойств, и, таким образом, сам корень - это увольнение или нет узлов в дереве, или листья распределены по L и R, и нам просто нужно подсчитать и суммируйте количество листьев в обоих поддеревах.

Или в псевдокоде:

countLeaves(node N): 
    //the tree is empty 
    if N == null: 
     return 0 

    //N is a leave 
    if L == null && R == null: 
     return 1 

    //count leaves in both subtrees 
    return countLeaves(L) + countLeaves(R) 

Answer 2

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

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

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