Дерево

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

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

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

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

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

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

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

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

У каждой вершины, кроме корня, только один родитель. Родитель — это вершина, от которой к данной вершине ведёт одна ветвь, если двигаться от корня. Если бы у одной вершины было два родителя, к ней можно было бы прийти разными путями. Тогда нарушилось бы главное свойство дерева — единственный путь от корня до каждого объекта.

Родители и потомки определяются направлением от корня. Родитель находится ближе к корню, а потомок расположен ниже по той же ветви. Например, если от корня идёт ребро к вершине А, а от А — к вершине Б, то А — родитель Б, а Б — потомок А. Такое различение помогает понять порядок объектов, например какие папки находятся внутри других.

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

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

Роли вершин в дереве

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

Разбор задач

Семейное дерево

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

1. Найди главную вершину, от которой начинается схема. Обычно это человек, от которого показаны родственные связи; отметь его как корень.
2. Каждую точку или подпись с именем человека назови вершиной. Все они обозначают объекты семейной схемы, в том числе корень.
3. Проследи линии между подписями и отметь их как рёбра. Каждая такая линия показывает связь между двумя вершинами.

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

Дерево каталогов

Условие. В дереве каталогов найди родителя и потомков папки «Документы», а также перечисли листья. Каталог — это папка, которая может содержать другие папки и файлы. Названия конкретных папок в условии не даны, поэтому ответ нужно составить по схеме: проследить связи вокруг «Документы» и проверить каждую конечную вершину.

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

Ответ. Родитель «Документы» — непосредственно предшествующая ей папка на пути от корня, а потомки — все папки ниже по её ветвям. Листья — все вершины без потомков, не обязательно только потомки «Документы». Если у «Документы» нет продолжения, эта папка тоже является листом.

Уровень вершины и проверка дерева

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

1. Найди корень и начни считать с него: он находится на первом уровне. Не пропускай вершины на пути к заданной.
2. Проследи путь от корня до нужной вершины. Каждый переход по ребру ведёт на следующий уровень, поэтому посчитай вершины пути, включая корень.
3. Проверь всю схему: корень должен быть один, а к каждой другой вершине должен вести единственный путь от корня. Если эти условия выполняются, схема является деревом.

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

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

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

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

Родителя иногда путают с потомком, потому что оба объекта связаны с одной ветвью. Родитель расположен ближе к корню, а потомок — дальше от него. Чтобы проверить себя, начни движение от корня: первая вершина перед выбранной будет её родителем, а вершины дальше — её потомками. Не определяй направление только по тому, что нарисовано сверху или снизу.

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

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

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

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

• У дерева есть один корень.
• Вершины дерева соединяются рёбрами.
• У корня нет родителя.
• У каждой другой вершины ровно один родитель.
• Лист — вершина без потомков.
• От корня до каждой вершины ведёт единственный путь.