Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Обход дерева Python: Деревья

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

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

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

Depth-first Search

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

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

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

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

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

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

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

from hexlet import fs

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


def dfs(node):
    # Распечатываем имя узла
    print(fs.get_name(node))
    # Если это файл, то возвращаем управление
    if fs.is_file(node):
        return

    # Получаем детей
    children = fs.get_children(node)

    # Применяем функцию dfs ко всем дочерним элементам
    # Множество рекурсивных вызовов в рамках одного вызова функции
    # называется древовидной рекурсией
    list(map(dfs, children))


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

https://repl.it/@hexlet/python-trees-traversal-dfs

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

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

import copy
from hexlet import fs


def change_owner(node, owner):
    name = fs.get_name(node)
    new_meta = copy.deepcopy(fs.get_meta(node))
    new_meta['owner'] = owner
    if fs.is_file(node):
        # Возвращаем обновлённый файл
        return fs.mkfile(name, new_meta)
    children = fs.get_children(node)
    # Ключевая строчка
    # Вызываем рекурсивное обновление каждого ребёнка
    new_children = list(map(lambda child: change_owner(child, owner), children))
    new_tree = fs.mkdir(name, new_children, new_meta)
    # Возвращаем обновлённую директорию
    return new_tree

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

https://repl.it/@hexlet/python-trees-traversal-change-owner

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

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


Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты.

Ошибки, сложный материал, вопросы >
Нашли опечатку или неточность?

Выделите текст, нажмите ctrl + enter и отправьте его нам. В течение нескольких дней мы исправим ошибку или улучшим формулировку.

Что-то не получается или материал кажется сложным?

Загляните в раздел «Обсуждение»:

  • задайте вопрос. Вы быстрее справитесь с трудностями и прокачаете навык постановки правильных вопросов, что пригодится и в учёбе, и в работе программистом;
  • расскажите о своих впечатлениях. Если курс слишком сложный, подробный отзыв поможет нам сделать его лучше;
  • изучите вопросы других учеников и ответы на них. Это база знаний, которой можно и нужно пользоваться.
Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
900
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

  • 130 курсов, 2000+ часов теории
  • 900 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы соглашаетесь c «Политикой конфиденциальности» и «Условиями оказания услуг»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff
Рекомендуемые программы

С нуля до разработчика. Возвращаем деньги, если не удалось найти работу.

Иконка программы Python-разработчик
Профессия
Разработка веб-приложений на Django
26 января 8 месяцев

Используйте Хекслет по максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы соглашаетесь c «Политикой конфиденциальности» и «Условиями оказания услуг»