Все пути дерева

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

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

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

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

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

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

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

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

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

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

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

Элементы дерева и пути от корня

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

Разбор задач

Задача 1

Дано дерево с корнем A и рёбрами A–B, A–C, B–D, B–E, C–F. Требуется выписать все пути от корня до листьев. Сначала нужно определить, у каких вершин нет потомков.

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

Ответ: A–B–D, A–B–E, A–C–F. Всего получилось три пути, потому что в дереве три листа.

Задача 2

Для дерева, заданного списком рёбер, нужно определить путь между вершинами D и F и его длину. Удобно идти от обеих вершин вверх, к родителям, пока не встретится общий предок.

1. Поднимаемся от D: сначала попадаем в B, затем в A.
2. Поднимаемся от F: сначала попадаем в C, затем в A.
3. Общий предок — A, поэтому объединяем участки D–B–A и A–C–F, не повторяя A.

Ответ: путь D–B–A–C–F. В нём четыре ребра, значит, его длина равна 4, а вершин в последовательности пять.

Задача 3

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

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

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

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

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

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

Некоторые пытаются найти несколько путей между одной парой вершин. Это противоречит определению дерева: отсутствие циклов оставляет только один маршрут. Если варианты появились, проверьте, не повторяете ли вы вершины или не добавили ли лишнее ребро.

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

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

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

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

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

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