Файловая структура – пример дерева, с которым знакомы все, кто пользуется компьютером. Она состоит из директорий и разного вида файлов:
python-package # Корневая директория
├── Makefile # Файл
├── README.md # Файл
├── __tests__ # Директория
│ └── test_fs.py # Файл
├── setup.cfg # Файл
├── pyproject.toml # Файл
└── .venv # Директория
└── lib # Директория
└── python3.6 # Директория
└── site-packages # Директория
└── pip # Директория
└── __init__.py # Файл
В этом уроке мы начнем знакомиться с деревьями и обсудим, по какому принципу они работают.
Как устроены деревья
Выше вы увидели файловую систему. Деревом она называется из-за своей структуры. Все элементы файловой системы выстраиваются в иерархию. В ней на верхнем уровне находится корневая директория или диск, если речь идет про Windows. Далее расположены файлы и директории, которые сами по себе могут содержать файлы и директории.
Ключевая черта древовидной структуры в том, что она рекурсивна. Другими словами, дерево состоит из поддеревьев, которые в свою очередь состоят из поддеревьев, которые в свою очередь состоят из поддеревьев и так далее.
Эта особенность определяет основные способы работы с деревьями в коде, все они работают рекурсивно.
Перейдем к основным терминам. Само дерево состоит из двух компонентов.
Первый компонент — это узлы, они же вершины или ноды. Узлы делятся на два типа:
- Внутренние — те, у которых есть потомки
- Листовые — те, у которых нет потомков
В случае файловой системы листовые узлы представлены файлами, а внутренние — директориями.
Второй компонент — ребра между узлами. В реальности ребра не существуют. Они нужны лишь для того, чтобы визуализировать связь и по необходимости описывать ее.
Так узлы и ребра выглядят на схеме:
У каждой вершины в дереве есть родитель. Единственное исключение — это корневой узел. У него нет родителей, потому что именно с него начинается дерево.
Еще у вершины могут быть потомки в любом количестве.
Кроме того, в деревьях выделяют понятие глубина. Она определяет, сколько шагов нужно пройти по вершинам от корневой, чтобы достичь текущей вершины (той, на которую смотрим).
Вершины, находящиеся на одной глубине и имеющие общего родителя, называют братскими или сестринскими.
Реализация через вложенные кортежи
Описать деревья можно огромным количеством способов. Самый примитивный вариант — это вложенные кортежи:
(('index.html', 'main.py'), 'index.py', ('favicon.ico', 'app.css'))
# * корень – кортеж
# / | \
# * index.py *
# / | | \
# index.html main.py favicon.ico app.css
# Еще пара примеров деревьев с произвольными данными:
() # Пустое дерево
(3, 2, (3, 8), ((8), 3))
(1, None, ((3)), (5, 'string', (False, (3), {"key": "value"})))
В примерах выше корень — это сам кортеж, а все его элементы — это потомки. Если потомок не является кортежем, то он рассматривается как листовой узел, иначе — как внутренний узел. В свою очередь, внутренний узел состоит из потомков.
Любое дерево состоит из двух больших частей:
- Данных, которые хранятся внутри дерева
- Структуры дерева, которые отвечают за связи между данными
Рассмотрим такой пример:
(('index.html', 'main.py'), 'index.py', ('favicon.ico', 'app.css'))
Что в этом дереве структура, а что данные? Данные здесь – листовые узлы, а вот внутренние кортежи – исключительно структура. Они определяют, где какие файлы находятся, но сами не содержат никаких данных.
Подобная организация дерева непригодна для хранения файловой структуры. Как минимум это дерево не позволяет задать имя для директории.
Расширим структуру так, чтобы она позволяла добавлять больше информации. Представим каждый элемент дерева парой:
- Первый элемент — это значение, хранящееся в узле
- Второй элемент — список потомков
Если второй элемент отсутствует, то считаем, что текущий узел — листовой:
('app', [ # Корень
('dist', [ # Внутренний узел
('index.html'), # Лист
('main.py') # Лист
]),
('index.py'), # Лист
('assets', [ # Внутренний узел
('favicon.ico'), # Лист
('app.css'), # Лист #
]),
])
# app
# / | \
# dist index.py assets
# / \ / \
# index.html main.py favicon.ico app.css
Такой вариант многословнее, но позволяет хранить данные в любом узле, даже не листовом. Причем это не обязательно должна быть строка, как в примере выше. Изменение данных на словари позволит добавлять туда все что угодно.
Реализация через словари
Самый гибкий и удобный способ представления деревьев — это словари. В таком дереве каждый узел — это словарь, а списки используются только для хранения потомков:
# Обратите внимание на разделение структуры и данных
# Здесь оно значительно более очевидное
{
"value": 5,
"children": [
{"value": 10},
{"value": 100},
{"value": "nested", "children": []}
]
}
По большому счету, список и словарь сами по себе всегда могут рассматриваться как деревья. Это справедливо для любой рекурсивной структуры данных — то есть для такой структуры, элементами которой может быть сама структура.
В любом списке может содержаться список, как и в любом словаре может содержаться словарь.
Дополнительные материалы
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
