Иерархические структуры

Для сохранения прогресса вступите в курс. Войти или зарегистрироваться.

Обход деревьев — крайне важная тема. Иерархические структуры встречаются на каждом шагу: это и файловая система, и html и даже исходный код большинства языков программирования. Если вы научитесь решать задачи по обходу таких структур, то сможете справиться с большинством стандартных вычислительных задач на своей работе. Это мое мнение, которое подтверждается богатым опытом, но, конечно же, не является истиной в последней инстанции.

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

Начнем с самого простого примера, в котором не требуется накапливать результат. Предположим, что у нас есть список списков любой вложенности, который содержит числа. Все что нужно сделать — узнать, есть ли среди этих чисел хотя бы один ноль. Пример входных данных для подобной функции выглядит так: l(1, l(5, 0), 10, l(l(8), 3)).

Прежде чем разбирать код, опишем алгоритм, по которому работает функция hasZero:

  • Рекурсивно обходим список:
    • Если список закончился, а 0 не найден, то возвращаем false (guard expression).
    • Если текущий элемент — не список, то проверяем, равен ли он нулю.
      • Если равен нулю, то возвращаем true.
    • Если текущий элемент — список, то запускаем hasZero рекурсивно, передав туда текущий элемент.
      • Если результат этого вызова true, то возвращаем true.
    • Если не сработали предыдущие терминальные условия, проверяем следующий элемент списка.

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

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

Более интересный и сложный пример связан с агрегацией: посчитать количество чего-либо в дереве или собрать список узлов, соответствующий какому-либо критерию. Общий механизм обхода в этих случаях останется абсолютно тем же, но к нему добавится аккумулятор, который нужно прокидывать до самой глубины. По сути, вся задача сводится к реализации рекурсивного reduce. Ниже код функции searchZeros, которая, в отличие от предыдущей реализации, возвращает число нулей в дереве:

Главное в этом коде находится тут: return iter(rest, iter(current, acc));. Если current список, то прежде чем продолжать проверять список, по которому идет алгоритм, нужно выполнить поиск в найденном поддереве и так далее до самого дна. Соответственно, сначала отработает код iter(current, acc), который вернет acc для поддерева, сложенный с текущим значением аккумулятора. В итоге, на выходе получится новый аккумулятор, который передается дальше.

Мы учим программированию с нуля до стажировки и работы. Попробуйте наш бесплатный курс «Введение в программирование» или полные программы обучения по Node, PHP, Python и Java.

Хекслет

Подробнее о том, почему наше обучение работает →