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

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

Depth-first
Search

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

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

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

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

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

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

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

В примере выбрана схема дерева на массивах. Первый элемент массива это значение узла, второй (если есть) — это дети. По пунктам:

  1. Извлекаем из дерева (или поддерева) значение и детей;
  2. Печатаем значение;
  3. Если нет детей, то выходим. Если есть — вызываем рекурсивно функцию dfs для каждого ребёнка.

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

Мы учим программированию с нуля до стажировки и работы. Попробуйте наш бесплатный курс «Введение в программирование» или полные программы обучения по Node, PHP, Python и Java.

Хекслет

Подробнее о том, почему наше обучение работает →