Путь дерева

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

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

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

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

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

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

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

Путь от корня к выбранной вершине задаётся последовательностью всех вершин на этом спуске. Например, запись Корень—А—Б—В показывает, что сначала идут из корня в А, затем в Б и наконец в В. Такой путь единственный, потому что у вершины есть только одна цепочка родителей, ведущая вверх к корню.

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

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

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

Основные характеристики пути в дереве

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

Разбор задач

Путь от корня до вершины

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

1. Начинаем запись с корня, потому что путь задан от него.
2. Переходим в А, затем в Б и после этого в В.
3. Проверяем, что каждая соседняя пара соединена ребром.

Ответ: Корень—А—Б—В. В пути четыре вершины и три ребра, поэтому его длина равна трём.

Путь между двумя вершинами

Условие. Пусть вершины Б и Г находятся в разных ветвях: корень соединён с А, А — с Б и В, а В — с Г. Нужно найти путь между Б и Г и указать его длину. Общей вершиной, ближайшей к обеим заданным вершинам, будет А.

1. От Б поднимаемся к А: получаем участок Б—А.
2. От А идём к В, а затем к Г: получаем участок А—В—Г.
3. Соединяем участки без повторения А и считаем рёбра.

Ответ: Б—А—В—Г. В записи четыре вершины и три ребра, значит, длина пути равна трём.

Сравнение путей от корня

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

1. У первого пути три ребра, у второго — два.
2. Значит, длиннее путь Корень—А—Б—Д.
3. Сравниваем записи от начала и выделяем общую начальную часть: Корень—А.

Ответ: первый путь длиннее на одно ребро. На обоих путях лежат вершины Корень и А.

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

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

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

Выбирать произвольную общую вершину. Иногда берут любого общего предка и получают лишний участок пути. Найдите ближайшего общего предка, а затем проверьте, что все рёбра между концами пройдены ровно один раз.

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

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

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

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

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

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