Деревья в программировании — это способ организации структур данных, в которых присутствуют уровни вложенности. Это действительно чем-то похоже на разветвленное дерево: от ствола отходят самые толстые ветки, на них растут веточки поменьше, и на самых тоненьких — листья. Чтобы добраться до самых дальних, приходится следовать за ними от самого корня (привет, "новая папка", созданная в 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!
