Пошаговый перебор элементов дерева по связям между узлами-предками и узлами-потомками называется обходом дерева. Подразумевается, что в процессе обхода каждый узел будет затронут только один раз. По большому счету, все так же, как и в обходе любой коллекции, используя цикл или рекурсию. Только в случае деревьев способов обхода больше, чем просто слева направо и справа налево.
В данном курсе используется один порядок обхода — обход в глубину, так как он естественным образом получается при рекурсивном обходе. Об остальных способах можно прочитать в Википедии, либо в рекомендованных Хекслетом книгах.
Это один из методов обхода дерева. Стратегия этого поиска состоит в том, чтобы идти вглубь одного поддерева настолько, насколько это возможно. Этот алгоритм естественным образом ложится на рекурсивное решение и получается сам собой.
Рассмотрим данный алгоритм на примере следующего дерева:
# * A
# / | \
# B * C * D
# /| |\
# E F G J
Каждая нелистовая вершина обозначена звездочкой. Обход начинается с корневого узла.
# B *
# /|
# E F
Повторяем логику первого шага. Проваливаемся на уровень ниже.
E
. Функция убеждается, что у узла нет дочерних элементов, выполняет необходимую работу и возвращает результат наверх# 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
Ключевое отличие от первого примера – вместо печати на экран, формируются новые узлы и возвращаются наружу. В конце концов из них собирается новое дерево.
Все, что будет дальше делаться по ходу курса, неизменно базируется на этом алгоритме. Попробуйте открыть редактор на своем компьютере и самостоятельно реализовать эту функцию без подглядывания. Так вы убедитесь в том, что поняли происходящее.
Вам ответят команда поддержки Хекслета или другие студенты.
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно
Наши выпускники работают в компаниях:
С нуля до разработчика. Возвращаем деньги, если не удалось найти работу.
Зарегистрируйтесь или войдите в свой аккаунт