Пошаговый метод для подбора рекурсивных алгоритмов для обходов дерева?

Question

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

Для случайного примера, подсчитывая количество узлов в двоичном дереве, которые не являются корнем или листьями? Как мне рекурсивно думать об этой проблеме и в конечном итоге придумать решение psuedocode? Раньше я начинал такую ​​проблему, создавая различные сценарии и создавая псевдокод для учета случаев, с которыми я столкнулся, но я чувствовал, что (и сделал) пропустил какую-то логику здесь и там.

Любые предложения?

Answer 1

В целом рекурсия заключается в поиске повторяющегося шаблона и экстраполяции его на более общее решение. Согласно Википедии:

«Рекурсия процесс повторяющихся элементов в автомодельного образом.»

Но это довольно расплывчаты и неконкретны определение Давайте вернемся к примерам

..

---

бинарное дерево очень повторяющаяся структура Рассмотрим это (почти) минимальный пример:.

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

visit(l_child) 
already in root 
visit(r_child) 

      already in root 
      / \ 
      /  \ 
visit(l_child)  visit(r_child) 

Так в основном вы:

starting in the root → 
visiting the left child → 
getting back to the root → 
visiting the right child → 
getting back to the root. 

Взгляните на другой пример бинарного дерева:

Как вы можете видеть, что есть огромное сходство с предыдущей структурой. Теперь давайте посмотрим на каждый цветной узел:

visit(l_subtree) 
already in root  
visit(r_subtree) 

Это точно такой же узор. Так как мы знаем, как пройти поддерева, мы можем думать о более общем алгоритме:

inorder(node): 
    if node == null: //we've reached the bottom of a binary tree 
     return 0 
    inorder(node.l_child) 
    do_something(node) 
    inorder(node.r_child) 

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

Если рекурсия по-прежнему не интуитивно понятна, вы можете проверить это fractals example.