Python: Деревья
2026-02-26 16:53 Diff
https://ru.hexlet.io/courses/python-trees/lessons/traversal/theory_unit

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

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

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

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

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

Этот алгоритм естественным образом ложится на рекурсивное решение и получается сам собой:

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

Каждая нелистовая вершина обозначена звездочкой. Рассмотрим обход этого дерева по шагам:

  1. Обход начинается с корневого узла. Проверяем, есть ли потомки у вершины A. Если есть, то запускаем обход рекурсивно для каждого потомка независимо

  2. Внутри первого рекурсивного вызова оказывается следующее поддерево:

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

  4. Снова оказываемся в знакомой ситуации:

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

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

Изменение данных

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

Для этого нам придется соединить две вещи:

  • Рекурсию, разобранную выше
  • Код обновления узлов из прошлого урока

Так это выглядит в коде:

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

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