Теория: Обход дерева

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

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

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

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

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

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

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

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

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

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

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

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

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

<?php

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

function dfs($tree)
{
  // Распечатываем содержимое узла
  echo getName($tree) . "\n";
  // Если это файл, то возвращаем управление
  if (isFile($tree)) {
      return;
  }

  // Получаем детей
  $children = getChildren($tree);

  // Применяем функцию dfs ко всем дочерним элементам
  // Множество рекурсивных вызовов в рамках одного вызова функции
  // называется древовидной рекурсией
  array_map(fn($child) => dfs($child), $children);
}

dfs($tree);
// => /
// => etc
// => bashrc
// => consul.cfg
// => hexletrc
// => bin
// => ls
// => cat

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

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

<?php

function changeOwner($tree, $owner)
{
  $name = getName($tree);
  $newMeta = getMeta($tree);
  $newMeta['owner'] = $owner;

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

  $children = getChildren($tree);
  // Ключевая строчка
  // Вызываем рекурсивное обновление каждого ребенка
  $newChildren = array_map(function ($child) use ($owner) {
      return changeOwner($child, $owner);
  }, $children);
  // Создаем директорию
  $newTree = mkdir($name, $newChildren, $newMeta);

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

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

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

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