Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

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

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

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

4 <h2>Содержание</h2>

5 <ul><li><a>Дерево - объект!</a></li>

6 <li><a>Дерево - массив!</a></li>

7 <li><a>Заключение</a></li>

8 </ul><h2>Дерево - объект!</h2>

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

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

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

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

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

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

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

16 <h2>Дерево - массив!</h2>

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

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

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

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

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

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

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

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

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

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

27 <h2>Заключение</h2>

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

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

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