Пошаговый перебор элементов дерева по связям между узлами-предками и узлами-потомками называется обходом дерева. Подразумевается, что в процессе обхода каждый узел будет затронут только один раз. По большому счёту, всё так же, как и в обходе любой коллекции, используя цикл или рекурсию. Только в случае деревьев способов обхода больше, чем просто слева направо и справа налево.
В данном курсе используется один порядок обхода — обход в глубину, так как он естественным образом получается при рекурсивном обходе. Об остальных способах можно прочитать в Википедии либо в рекомендуемых Хекслетом книгах.
Обход в глубину (Depth-first search)
Один из методов обхода дерева (графа в общем случае). Стратегия этого поиска состоит в том, чтобы идти вглубь одного поддерева настолько, насколько это возможно. Этот алгоритм естественным образом ложится на рекурсивное решение и получается сам собой.
Рассмотрим данный алгоритм на примере следующего дерева:
// * A
// / | \
// B * C * D
// /| |\
// E F G J
Каждая нелистовая вершина обозначена звёздочкой. Обход начинается с корневого узла.
- Проверяем, есть ли у вершины A дети. Если есть, то запускаем обход рекурсивно для каждого ребёнка независимо;
- Внутри первого рекурсивного вызова оказывается следующее поддерево:
// B *
// /|
// E F
Повторяем логику первого шага. Проваливаемся на уровень ниже.
- Внутри оказывается листовой элемент
E
. Функция убеждается, что у узла нет дочерних элементов, выполняет необходимую работу и возвращает результат наверх. - Снова оказываемся в ситуации:
// B *
// /|
// E F
В этом месте, как мы помним, рекурсивный вызов запускался на каждом из детей. Так как первый ребёнок уже был посещен, второй рекурсивный вызов заходит в узел F
и выполняет там свою работу. После этого происходит возврат выше, и всё повторяется до тех пор, пока не дойдёт до корня.
const tree = fsTrees.mkdir('/', [
fsTrees.mkdir('etc', [
fsTrees.mkfile('bashrc'),
fsTrees.mkfile('consul.cfg'),
]),
fsTrees.mkfile('hexletrc'),
fsTrees.mkdir('bin', [
fsTrees.mkfile('ls'),
fsTrees.mkfile('cat'),
]),
]);
const dfs = (tree) => {
// Распечатываем содержимое узла
console.log(fsTrees.getName(tree));
// Если это файл, то возвращаем управление
if (fsTrees.isFile(tree)) {
return;
}
// Получаем детей
const children = fsTrees.getChildren(tree);
// Применяем функцию dfs ко всем дочерним элементам
// Множество рекурсивных вызовов в рамках одного вызова функции
// называется древовидной рекурсией
children.forEach(dfs);
};
dfs(tree);
// => /
// => etc
// => bashrc
// => consul.cfg
// => hexletrc
// => bin
// => ls
// => cat
https://repl.it/@hexlet/js-trees-traversal-dfs-nodejs
Печать на экран в примере выше это лишь демонстрация. В реальности же нас интересует либо изменение дерева, либо агрегация данных по нему. Агрегацию данных рассмотрим позже, а сейчас разберём изменение.
Допустим, мы хотим реализовать функцию, которая меняет владельца для всего дерева, то есть всех директорий и файлов. Для этого нам придётся соединить две вещи: рекурсию, разобранную выше, и код обновления узлов, который изучался в прошлом уроке.
const changeOwner = (tree, owner) => {
const name = fsTrees.getName(tree);
const newMeta = _.cloneDeep(fsTrees.getMeta(tree));
newMeta.owner = owner;
if (fsTrees.isFile(tree)) {
// Возвращаем обновлённый файл
return fsTrees.mkfile(name, newMeta);
}
// Дальше идет работа, если директория
const children = fsTrees.getChildren(tree);
// Ключевая строчка
// Вызываем рекурсивное обновление каждого ребёнка
const newChildren = children.map((child) => changeOwner(child, owner));
const newTree = fsTrees.mkdir(name, newChildren, newMeta);
// Возвращаем обновлённую директорию
return newTree;
};
// Эту функцию можно обобщить до map (отображения), работающего с деревьями
https://repl.it/@hexlet/js-trees-traversal-changeOwner-nodejs
Ключевое отличие от первого примера – вместо печати на экран, формируются новые узлы и возвращаются наружу. В конце концов из них собирается новое дерево.
Всё, что будет дальше делаться по ходу курса, неизменно базируется на этом алгоритме. Попробуйте открыть редактор на своём компьютере и самостоятельно реализовать эту функцию без подглядывания. Так вы убедитесь в том, что поняли происходящее.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
- Статья «Как учиться и справляться с негативными мыслями»
- Статья «Ловушки обучения»
- Статья «Сложные простые задачи по программированию»
- Вебинар «Как самостоятельно учиться»
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.