Дерево. Следующие вершины, листья

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

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

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

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

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

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

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

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

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

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

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

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

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

Разбор задач

Задача 1. В дереве A соединена с B и C, B — с D и E, а C — с F. Назовите следующие вершины для B и все листья дерева.

1. Смотрим только на линии, отходящие непосредственно от B. Они ведут к D и E, поэтому именно эти вершины следующие для B.
2. Проверяем, есть ли продолжение у каждой вершины: от D, E и F других связей вниз не указано.
3. A, B и C имеют следующие вершины, значит, листьями они не являются. D, E и F — окончания ветвей.

Ответ: следующие для B — D и E; листья — D, E и F.

Задача 2. Дерево задано парами связей: A–B, A–C, B–D, C–E, C–F, E–G. Для каждой вершины, кроме корня, укажите предыдущую вершину; перечислите листья.

1. Начинаем с A: она соединена с B и C и не имеет предыдущей вершины, поэтому это корень.
2. Для каждой оставшейся вершины находим, откуда к ней ведёт связь: у B предыдущая A, у C — A, у D — B, у E — C, у F — C, у G — E.
3. Теперь ищем вершины, от которых не отходят связи к следующим: D и F никуда дальше не ведут, а у G нет продолжения после E. У B, C и E продолжения есть.

Ответ: предыдущие вершины: B — A, C — A, D — B, E — C, F — C, G — E; листья — D, F и G.

Задача 3. По схеме с корнем A определите, является ли вершина C листом, назовите следующие вершины C и подсчитайте количество листьев.

1. Сначала прослеживаем связи, отходящие непосредственно от C. Если линии ведут к другим вершинам, C не лист; эти вершины и будут следующими для C.
2. Затем проверяем концы всех ветвей дерева, начиная от корня A. Каждую вершину без дальнейшего продолжения отмечаем как лист.
3. Считаем отмеченные листья по одному, не учитывая вершины, у которых есть хотя бы одна следующая вершина. Чтобы не пропустить ветвь, проверяем все связи от корня до окончаний.

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

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

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

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

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

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

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

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

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

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