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

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

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

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

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

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

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

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

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

Чтобы найти следующие бусины, сначала выберите нужную бусину и определите направление от корня. Затем рассмотрите только её непосредственные соединения в сторону от корня. Бусины, до которых нужно пройти через одну или несколько промежуточных бусин, являются более дальними потомками, но не следующими для выбранной бусины.

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

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

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

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

Разбор задач

Задача 1

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

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

Ответ: следующие для А — Б и В; следующие для Б — Г и Д; листья — Г, Д и Е.

Задача 2

Условие: связи заданы так: А→Б, А→В, Б→Г, В→Д, В→Е. Нужно записать все пути от корня до листьев.

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

Ответ: А→Б→Г; А→В→Д; А→В→Е.

Задача 3

Условие: Петя считает деревом схему со связями А→Б, А→В, Б→Г, В→Г. Нужно проверить утверждение.

1. От А до Г можно пройти по ветви А→Б→Г.
2. Существует и второй путь: А→В→Г.
3. Сравниваем результат с определением: в дереве путь к каждой бусине должен быть единственным.

Ответ: Петя ошибается. Схема не является деревом, потому что к Г ведут два разных пути.

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

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

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

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

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

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

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

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

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

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

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