Алгоритм обхода дерева и поиска в ширину с использованием рекурсии

«... секрет понимания рекурсии заключается в понимании рекурсии»…. Не знаю, кто это сказал, но мне это нравится!

Ладно, к делу, обход дерева. Эта ссылка объясняет, с чем мы имеем дело, но давайте представим, что у нас есть дерево, каждый узел имеет значение (назовем его полезной нагрузкой) и массив узлов, на которые он указывает (назовем эти дочерние элементы). . Немного похоже на это…..

Ясно, что «1» — это наш начальный узел (или ствол, как его часто называют) и имеет «2», «3» и «4» в качестве дочерних элементов. Разве это не мило? С такой структурой мы можем начать с «1» и «обходить» все узлы, получая дочерние элементы и так далее. Теперь представьте, что мы хотим найти конкретное значение, ну, мы должны пройти через все дочерние элементы, проверяя значение каждого узла по мере продвижения. Это может очень быстро стать довольно сложным, и есть несколько способов сделать это. В этом посте мы рассмотрим, как решить эту проблему с помощью алгоритма поиска в ширину.

Как и большинство вещей, о которых любят болтать разработчики, на самом деле все намного проще, если мы избавимся от профессионального жаргона и получим немного старого доброго английского на ходу. Итак, в лучшем случае королевы; «нужно найти «6», спускаясь на один уровень за раз и действуя при этом слева направо».

Хорошо, это просто, мы проверяем «1», смотрим, является ли это «6», если это не смотрим на всех своих детей, так что это означает, что на один уровень ниже мы видим, если это «2», «3» или «4». "6" и так далее. Теперь давайте разберем рубиновый код.

Выше показано, что мы будем использовать для создания каждого узла, поэтому мы создаем узел «1» с чем-то вроде…

start_node = Node.new(1,[node_two, node_three, node_four])

… и так далее для каждого дочернего элемента, пока не будут созданы все двенадцать узлов. Обратите внимание, что узлы «9», «10», «11» и «12» будут иметь пустой массив в качестве аргументов, когда мы создадим их узлы.

Итак, как !$###$! мы собираемся найти узел с «6» в качестве полезной нагрузки, идя из стороны в сторону в соответствии с указом королевы выше? Что ж, если мы используем рекурсию, это просто означает, что мы вызываем метод внутри этого метода, это выглядит так.

Или в рубине…

def method(argument)
сделать что-нибудь…..
method(new_argument)
end

Теперь мы можем просто передать start_node нашему методу, проверить, является ли полезная нагрузка start_node искомым значением, которое мы ищем, и, если нет, запустить цикл Rails по всем дочерним элементам start_node и повторить, вызвав метод (child). Это рекурсия, и она может выглядеть примерно так.

Что это будет эффективно делать, так это проверять «1», а затем получать каждого ребенка, начиная с «2». Сначала он проверит «2», а затем получит дочерние элементы «2», прежде чем проверит «3» или «4». Это явно не широта, а глубина. Хорошо подмечено!!

Таким образом, этот код будет переходить от «2» к «5», проверять, затем переходить к «9», а затем обратно к «10», прежде чем, наконец, перейти к «6». Мы рассмотрим это в следующем посте, а пока давайте сосредоточимся на поиске по одному уровню за раз слева направо.

Рекурсивный подход, который мы собираемся использовать, заключается в передаче массива в качестве аргумента нашему методу поиска, изначально этот массив будет содержать start_node (или «1», как мы его называли), а затем мы создадим массив из дочерние элементы «1» (следовательно, «2», «3» и «4») и передать их в наш метод и так далее.

Итак, в коде что происходит? Мы передаем исходный массив (содержащий first_node) и просматриваем этот массив, проверяя, является ли он искомым значением, если нет, мы строим массив его дочерних элементов и передаем его обратно, вызывая себя. В следующий раз у нас будет массив всех дочерних элементов «1», которые мы проверяем — «2», «3» и «4». Если ни один из них не соответствует нашему поисковому значению, мы создаем массив из «5», «6», «7» и «8» и проверяем каждый из них. Когда мы достигнем «6», мы вернемся! Простой. Обратите внимание, у нас также есть строка кода, чтобы гарантировать, что мы возвращаемся в момент, когда больше нет дочерних элементов, то есть когда мы достигли самого низкого уровня для поиска. В этом случае мы возвращаем ненайденный элемент, такой подход позволяет избежать переполнения стека.

Хорошо, мы закончили!! Наслаждайтесь и надеюсь, что это поможет всем, кто полностью застрял в этой теме.