Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

1 Файловая структура - пример дерева, с которым знакомы все, кто пользуется компьютером. Она состоит из директорий и разного вида файлов:

2 В этом уроке мы начнем знакомиться с деревьями и обсудим, по какому принципу они работают.

3 <h2>Как устроены деревья</h2>

4 Выше вы увидели файловую систему. Деревом она называется из-за своей структуры. Все элементы файловой системы выстраиваются в иерархию. В ней на верхнем уровне находится корневая директория или диск, если речь идет про Windows. Далее расположены файлы и директории, которые сами по себе могут содержать файлы и директории.

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

6 Эта особенность определяет основные способы работы с деревьями в коде, все они работают рекурсивно.

7 Перейдем к основным терминам. Само дерево состоит из двух компонентов.

8 Первый компонент - этоузлы, они же вершины или ноды. Узлы делятся на два типа:

9 <ul><li>Внутренние- те, у которых есть потомки</li>

10 <li>Листовые- те, у которых нет потомков</li>

11 </ul>В случае файловой системы листовые узлы представлены файлами, а внутренние - директориями.

12 Второй компонент -ребрамежду узлами. В реальности ребра не существуют. Они нужны лишь для того, чтобы визуализировать связь и по необходимости описывать ее.

13 Так узлы и ребра выглядят на схеме:

14 У каждой вершины в дереве естьродитель. Единственное исключение - это корневой узел. У него нет родителей, потому что именно с него начинается дерево.

15 Еще у вершины могут бытьпотомкив любом количестве.

16 Кроме того, в деревьях выделяют понятиеглубина. Она определяет, сколько шагов нужно пройти по вершинам от корневой, чтобы достичь текущей вершины (той, на которую смотрим).

17 Вершины, находящиеся на одной глубине и имеющие общего родителя, называютбратскимиилисестринскими.

18 <h2>Реализация через вложенные кортежи</h2>

19 Описать деревья можно огромным количеством способов. Самый примитивный вариант - это вложенные кортежи:

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

21 Любое дерево состоит из двух больших частей:

22 <ol><li>Данных, которые хранятся внутри дерева</li>

23 <li>Структуры дерева, которые отвечают за связи между данными</li>

24 </ol>Рассмотрим такой пример:

25 Что в этом дереве структура, а что данные? Данные здесь - листовые узлы, а вот внутренние кортежи - исключительно структура. Они определяют, где какие файлы находятся, но сами не содержат никаких данных.

26 Подобная организация дерева непригодна для хранения файловой структуры. Как минимум это дерево не позволяет задать имя для директории.

27 Расширим структуру так, чтобы она позволяла добавлять больше информации. Представим каждый элемент дерева парой:

28 <ul><li>Первый элемент - это значение, хранящееся в узле</li>

29 <li>Второй элемент - список потомков</li>

30 </ul>Если второй элемент отсутствует, то считаем, что текущий узел - листовой:

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

32 <h2>Реализация через словари</h2>

33 Самый гибкий и удобный способ представления деревьев - это словари. В таком дереве каждый узел - это словарь, а списки используются только для хранения потомков:

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

35 В любом списке может содержаться список, как и в любом словаре может содержаться словарь.