5. Traversal

Познакомиться с понятием "обход дерева"

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

В данном курсе используется один порядок обхода — обход в глубину, так как он естественным образом получается при рекурсивном обходе. Об остальных способах можно прочитать в Википедии либо в рекомендованных книгах Хекслета.

Обход в глубину (Depth-first search)

Один из методов обхода дерева (графа в общем случае). Стратегия этого поиска состоит в том, чтобы идти вглубь одного поддерева настолько, насколько это возможно. Этот алгоритм естественным образом ложится на рекурсивное решение и получается сам собой.

Рассмотрим данный алгоритм на примере следующего дерева:

//     * A
//   / | \
// B * C * D
//  /|   |\
// E F   G J

Каждая нелистовая вершина обозначена звёздочкой. Обход начинается с корневого узла.

1. Проверяем, есть ли у вершины A дети. Если есть, то запускаем обход рекурсивно для каждого ребёнка независимо;
2. Внутри первого рекурсивного вызова оказывается следующее поддерево:

// B *
//  /|
// E F

Повторяем логику первого шага. Проваливаемся на уровень ниже.

1. Внутри оказывается листовой элемент E. Функция убеждается, что у узла нет дочерних элементов, выполняет необходимую работу и возвращает результат наверх.
2. Снова оказываемся в ситуации:

// B *
//  /|
// E F

В этом месте, как мы помним, рекурсивный вызов запускался на каждом из детей. Так как первый ребёнок уже был посещён, второй рекурсивный вызов заходит в узел F и выполняет там свою работу. После этого происходит возврат выше, и всё повторяется до тех пор, пока не дойдёт до корня.

const tree = mkdir('/', [
  mkdir('etc', [
    mkfile('bashrc'),
    mkfile('consul.cfg'),
  ]),
  mkfile('hexletrc'),
  mkdir('bin', [
    mkfile('ls'),
    mkfile('cat'),
  ]),
]);

const dfs = (tree) => {
  // Распечатываем содержимое узла
  console.log(getName(tree));
  // Если это файл, то возвращаем управление
  if (isFile(tree)) {
    return;
  }

  // Получаем детей
  const children = 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 = getName(tree);
  const newMeta = _.cloneDeep(getMeta(tree));
  newMeta.owner = owner;

  if (isFile(tree)) {
    // Возвращаем обновлённый файл
    return mkfile(name, newMeta);
  }

  const children = getChildren(tree);
  // Ключевая строчка
  // Вызываем рекурсивное обновление каждого ребёнка
  const newChildren = children.map((child) => changeOwner(child, owner));
  const newTree = mkdir(name, newChildren, newMeta);

  // Возвращаем обновлённую директорию
  return newTree;
};

// Эту функцию можно обобщить до map (отображения) работающего с деревьями

https://repl.it/@hexlet/js-trees-traversal-changeOwner-nodejs

Ключевое отличие от первого примера – вместо печати на экран, формируются новые узлы и возвращаются наружу. В конце концов из них собирается новое дерево.

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

Тесты

Вопрос 1

Какой вариант обхода дерева используется в рекурсивном решении?

Обход в ширину

Обход в глубину

Обход в обход

Вопрос 2

Сколько раз может быть обработан любой узел в процессе обхода?

Ровно один раз

Любое количество раз

Обход не должен обрабатывать узлы

Вопрос 3

Древовидная рекурсия сводится к рекурсивному вызову для каждого из детей текущего узла

При обходе в глубину, дерево просматривается по уровням. Сначала все узлы на глубине 1, затем 2 и так далее до самого дна

Древовидная рекурсия проще линейной

Упражнение

downcaseFileNames.js

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

Примеры

import { mkdir, mkfile } from '@hexlet/immutable-fs-trees';
import downcaseFileNames from './downcaseFileNames.js';

const tree = mkdir('/', [
  mkdir('eTc', [
    mkdir('NgiNx'),
    mkdir('CONSUL', [
      mkfile('config.json'),
    ]),
  ]),
  mkfile('hOsts'),
]);

downcaseFileNames(tree);
// {
//   name: '/',
//   type: 'directory',
//   meta: {},
//   children: [
//     {
//       name: 'eTc',
//       type: 'directory',
//       meta: {},
//       children: [
//         {
//           name: 'NgiNx',
//           type: 'directory',
//           meta: {},
//           children: [],
//         },
//         {
//           name: 'CONSUL',
//           type: 'directory',
//           meta: {},
//           children: [{ name: 'config.json', type: 'file', meta: {} }],
//         },
//       ],
//     },
//     { name: 'hosts', type: 'file', meta: {}, },
//   ],
// }

downcaseFileNames.js file

// @ts-check
import {  mkdir, mkfile, isFile, getName, getMeta, getChildren,} from '@hexlet/immutable-fs-trees';import _ from 'lodash';
// BEGIN (write your solution here)
// END

Хештеги