Дерево

Определения и обозначения

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

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

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

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

Как это устроено

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

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

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

На схеме сначала ищут вершину, от которой начинаются все ветви: это корень. У вершин с выходящими вниз связями есть потомки, поэтому их называют промежуточными, если они не корень; у вершин без потомков — листья. Количество уровней находят, считая их от принятого начала нумерации до самого дальнего элемента. Чтобы посчитать потомков конкретной вершины, различайте непосредственных детей и всех расположенных ниже элементов: число непосредственных потомков — это число связей, ведущих прямо к ним.

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

Основные элементы и характеристики дерева

Сравнивайте столбцы по двум главным признакам: есть ли у вершины родитель и есть ли потомки. Помните, что один корень может одновременно быть листом, если дерево состоит только из него. Число промежуточных вершин и листьев зависит от конкретной структуры.

Разбор задач

Определить типы вершин по схеме

Условие. Дано дерево: А — корень; у А есть потомки Б и В; у Б есть потомок Г; у В есть потомки Д и Е. Нужно назвать корень, все листья и промежуточные вершины. Схему удобно представить так: А ведёт к Б и В, а от Б и В отходят их указанные потомки.

1. Находим вершину без родителя. Такой элемент только один — А, значит, это корень.
2. Проверяем, у каких вершин есть потомки. А, Б и В имеют исходящие связи к детям, поэтому это вершины с потомками.
3. Ищем элементы без потомков. У Г, Д и Е дальнейших связей нет, значит, они листья.

Ответ. Корень — А; листья — Г, Д и Е; промежуточные вершины — Б и В. А тоже имеет потомков, но его выделяют отдельно как корень, поскольку у него нет родителя.

Найти предков, потомков и путь

Условие. В дереве А — корень; потомки А — Б и В; у Б есть Г и Д, а у Г — Е. Для вершины Е нужно записать предков, потомков и путь от корня. Здесь важно не смешивать все элементы ниже вершины с её непосредственными детьми.

1. Двигаемся от Е вверх по связям к родителям: родитель Е — Г, родитель Г — Б, родитель Б — А.
2. Записываем предков от ближайшего к самому дальнему: Г, Б, А. Все они лежат на цепочке от Е к корню.
3. Проверяем, есть ли вершины ниже Е. По условию таких связей нет, поэтому у Е нет потомков, и она является листом.
4. Путь от корня записываем в обратном направлении, от начала к цели: А — Б — Г — Е.

Ответ. Предки Е — Г, Б и А; потомков нет; путь от корня — А — Б — Г — Е. Единственный путь подтверждает, что у каждой вершины дерева только один родитель.

Построить дерево папок и посчитать элементы

Условие. Есть папка «Проект». В ней находятся папки «Тексты» и «Материалы». В папке «Тексты» лежат файлы «план» и «отчёт», а в папке «Материалы» — файл «фото». Нужно построить дерево и определить число вершин, листьев и уровней. Уровень корня считаем нулевым.

1. Обозначаем «Проект» корнем и проводим от него связи к папкам «Тексты» и «Материалы».
2. От «Тексты» проводим связи к файлам «план» и «отчёт», а от «Материалы» — к файлу «фото».
3. Считаем все объекты: одна корневая папка, две вложенные папки и три файла. Всего получается шесть вершин.
4. Листья — объекты без вложенных элементов: три файла. Самый длинный путь от корня проходит через папку к файлу, поэтому встречаются уровни 0, 1 и 2 — всего три уровня.

Ответ. В дереве 6 вершин, 3 листа и 3 уровня. Если в задаче уровни нумеруются с единицы, изменятся номера уровней, но число уровней останется тем же.

Типичные ошибки

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

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

Ошибка — путать предков и потомков. Предки находятся выше вершины на пути к корню, а потомки — ниже неё; путаница часто возникает, если смотреть только на расположение, а не на направление связей. Для проверки проследите цепочку сначала к корню, затем от вершины вниз.

Ошибка — соединять вершины одного уровня или замыкать ветви. Так поступают, когда воспринимают дерево как произвольную сеть, не проверяя иерархию; замыкание создаёт путь обратно к уже посещённой вершине. Убедитесь, что у каждой вершины, кроме корня, один родитель и что по связям нельзя вернуться в исходную точку.

Связь с другими темами

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

Что запомнить

• У дерева есть один корень.
• У каждой вершины, кроме корня, ровно один родитель.
• Лист не имеет потомков.
• В дереве нет замкнутых путей.
• Путь от корня к вершине однозначен.
• Уровень вершины определяется её расстоянием от корня.
• Дерево удобно для представления иерархических связей.