/
Блог
/
Дневник студента
/

JS. Путешествие по деревьям

JS. Путешествие по деревьям

1 октября 2020 г.
5 минут
9

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

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

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

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

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

const tree = { roots: { trunk: { branch: 'a leaf', hollow: 'a squirrel', }, }, country: { city: 'a citizen', }, 'Internet': { 'Hexlet.io': { 'Frontend JS': { 'Trees': 'this lesson' }, 'Blog': 'this post', }, }, };

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

// Вот так выглядит наша функция: const findPath = (tree) => { const iter = (obj, path) => { const keys = _.keys(obj); return keys.flatMap((key) => { if (_.isObject(obj[key])) { const updatedPath = `${path} —> ${key}`; return iter(obj[key], updatedPath); } const finalPath = `${path.slice(4)} —> ${key}` return `Follow the path [ ${finalPath} ] to find ${obj[key]}`; }); }; return iter(tree, '').join('\n'); };

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

const findPath = (tree) => { const iter = (obj, path) => { // здесь будет внутренняя логика }; return iter(tree, ''); };

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

const keys = _.keys(obj); return keys.flatMap((key) => { // Здесь будет внутренняя логика });

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

return keys.flatMap((key) => { if (_.isObject(obj[key])) { const updatedPath = `${path} —> ${key}`; return iter(obj[key], updatedPath); } const finalPath = `${path.slice(4)} —> ${key}` // поскольку мы начинали с пустой строки, // в начале образовалась лишняя стрелка, // которую мы обрежем методом .slice return `Follow the path [ ${finalPath} ] to find ${obj[key]}`; // последнее значение и есть цель маршрута });

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

Follow the path [ roots —> trunk —> branch ] to find a leaf Follow the path [ roots —> trunk —> hollow ] to find a squirrel Follow the path [ country —> city ] to find a citizen Follow the path [ Internet —> Hexlet.io —> Frontend JS —> Trees ] to find this lesson Follow the path [ Internet —> Hexlet.io —> Blog ] to find this post

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

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

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

const oakForest = ['grove', [ ['trunk', [ ['branch', ['squirrel'] ], ['branch'], ]], ['trunk', [ ['branch'], ['branch', [ ['hollow', [ ['squirrel'], ]] ]], ]], ['trunk', [ ['squirrel'], ['branch', [ ['hollow'], ]], ]], ]];

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

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

const findSquirrels = (tree) => { const [root, branches] = tree; if (!branches) { return []; } const flatBranches = _.flatten(branches); if (flatBranches.includes('squirrel')) { console.log(`Look at the ${root}! There's a squirrel!`); return root; } return branches.flatMap((branch) => findSquirrels(branch)); };

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

const findSquirrels = (tree) => { const [root, branches] = tree; if (!branches) { return []; } // дальше — больше };

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

const flatBranches = _.flatten(branches); // Снова воспользуемся // библиотекой Lodash // и выпрямим массив

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

if (flatBranches.includes('squirrel')) { console.log(`Look at the ${root}! There's a squirrel!`); return root; } return branches.flatMap((branch) => findSquirrels(branch));

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

// Вывод в консоли: Look at the branch! There's a squirrel! Look at the hollow! There's a squirrel! Look at the trunk! There's a squirrel!

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

const squirrelHabitats = findSquirrels(oakForest); console.log(`I found ${squirrelHabitats.length} squirrels in these locations: ${squirrelHabitats.join(', ')}!`); // Вот так выглядит финальный вывод: I found 3 squirrels in these locations: branch, hollow, trunk!

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

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

Заключение

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

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

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

Андрей Агафонов

5 лет назад

9