JS. Путешествие по деревьям
2026-02-26 18:11 Diff
https://ru.hexlet.io/blog/posts/js-puteshestvie-po-derevyam

Деревья в программировании — это способ организации структур данных, в которых присутствуют уровни вложенности. Это действительно чем-то похоже на разветвленное дерево: от ствола отходят самые толстые ветки, на них растут веточки поменьше, и на самых тоненьких — листья. Чтобы добраться до самых дальних, приходится следовать за ними от самого корня (привет, "новая папка", созданная в 2012 на дне папки с фотографиями).

Если вы проходили курс "JS. Деревья" на Хекслете, то помните, что знакомство с такими структурами происходит на примере виртуальной файловой системы. Вооружившись рекурсией, как сборщик сахарного тростника – мачете, вы пробираетесь к новым знаниям через дебри папок и файлов, не подозревая, что на том конце вас ждут ОНИ — объекты и массивы!

Да, деревья могут быть представлены разными типами данных, и к этому тоже нужно привыкнуть. Хотя везде и применяется один и тот же принцип, поначалу распознать его в незнакомом представлении дерева бывает непросто. Поэтому сегодня мы пройдемся по древовидным объектам и массивам, и научимся работать с ними.

Содержание

Дерево — объект!

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

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

Поскольку мы хотим получить целый маршрут, составленный из отдельных звеньев пути, нам не обойтись без аккумулятора. Первым делом добавим внутреннюю функцию iter, которая будет принимать на вход кусочки нашего пути и складывать их в маршрут через переменную path. Основная функция findPath должна вернуть iter, вызванную с нашим деревом и начальным отрезком пути в качестве аргументов (в нашем случае путь начинается с пустой строки '', но мы могли бы написать здесь какую-то точку отсчета, если бы захотели).

Теперь проработаем внутреннюю логику iter. Чтобы обойти наше дерево-объект, нам понадобятся ключи. Получим их с помощью функции _.keys() из библиотеки Lodash, и применим к каждому наши условия, используя flatMap, поскольку от вложенности мы хотим избавиться.

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

Обход дерева закончен, осталось соединить массив методом .join() и вот он, наш результат:

Отлично! Все маршруты на месте, и выстроены в нужной последовательности. Согласитесь, это было несложно!

Дерево — массив!

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

Представьте себе, что, устав от изучения программирования, вы решили прогуляться по такому лесу. Вы внимательно смотрите на деревья — не покажется ли белочка? Если пушистая прыгунья действительно покажет ушки, нужно крикнуть "Смотри, там белка!" — надо же как-то развлекаться — ну и неплохо бы запомнить, где мы видели всех этих зверьков. (Просто оцените, как образно я рисую для вас картину происходящего, чтобы отвлечь от этого жуткого массива, брр...).

Напишем функцию по поиску белок, и будем разбираться:

Главное и самое неочевидное в работе с массивом — это выделить базовую структуру, на основании которой можно будет запустить рекурсию. В нашем случае она выглядит так: ['узел', [его потомки]]. Вынесем эти составляющие в константы, используя деструктуризацию. Теперь определим условие, при котором рекурсия должна остановиться. Очевидно, что если у элемента нет потомков, мы не можем продолжить движение по этой ветви, поэтому в такой ситуации мы будем возвращать пустой массив — все равно мы планируем избавиться от вложенности, и пустые массивы просто исчезнут.

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

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

Наш обход завершен! В консоли - сообщения об увиденных нами белках, а функция вернула список мест, в которых прятались зверьки.

Осталось привести наш результат к более-менее информативному виду:

Все белки найдены, и это победа!

P.S. В моем варианте лес получился немного безликим. Если хотите потренироваться с обходом деревьев самостоятельно, придумайте для каждого элемента уникальное имя (для ленивых подойдет что-то вроде 'branch1-1', 'branch1-2') и соберите полный "адрес" местонахождения белки — от корня дерева, до кончика беличьего хвоста, так, как мы делали в примере с объектом.

Заключение

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

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

Удачи в освоении JavaScript!