2.2. Представление деревьев

Конечное корневое дерево Гформально определяется как непустое конечное множество упорядоченных узлов, таких, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы разбиты на поддеревьев

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

Рис. 2.3. Корневое дерево с тремя поддеревьями

Важной разновидность корневых деревьев являются бинарные деревья. Бинарное дерево Глибо пустое, либо состоит из выделенного узла, называемого корнем, и двух бинарных поддеревьев: левого и правого

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

2.2.1. Представление деревьев на связанной памяти

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

Рис. 2.4. Регулярная связанная структура представления дерева

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

Рис. 2.5. Универсальная связанная структура представления дерева

Применение указателей и связанных списков придает памяти гибкость, необходимую для представления различных структур. Но при этом легко и перестараться; поэтому следует избегать слишком большого количества указателей; сложность программной поддержки таких структур возрастает «экспоненциально», теряется четкость основной структуры, которую пытаются представить в памяти (последний пример представления дерева это наглядно подтверждает).

2.2.2. Представление деревьев на смежной памяти

Представление деревьев на смежной памяти (одномерный массив) предполагает неявное присутствие ребер, переход по которым выполняется посредством арифметических операций над индексами элементов массива — смежной памяти. Формирование таких деревьев с помощью адресной арифметики можно осуществлять двумя способами. Идея первого способа применима при любом постоянном количестве ребер, выходящих из вершин (регулярное дерево). Рассмотрим данный способ формирования на примере двоичного (бинарного) дерева.

Пусть имеется одномерный массив смежных элементов Неявная структура двоичного дерева определяется как на рис. 2.6.

По дереву на рис. 2.6 легко перемещаться в обоих направлениях. Переход вниз на один уровень из вершины можно выполнить, удвоив индекс к (индекс левого под дерева) или удвоив и прибавив 1 (индекс правого поддерева). Переход вверх на один уровень из вершины можно выполнить, разделив пополам и отбросив дробную часть. Рассмотренная структура применима к любому дереву с постоянным количеством ребер, выходящих из вершин.

Рис. 2.6. Двоичное дерево на смежной памяти с последовательной нумерацией вершин

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

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

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

Пример файла исходных данных:

(см. скан)

Выходной файл для данного примера:

В алгоритме 2.4 представлена программа расчета всех искомых маршрутов длины . Алгоритм делится на две части. В первой части (процедура CreateTreeAbc) выполняется формирование двоичного регулярного дерева на смежной памяти рис. 2.7.

Алгоритм 2.4. Программа на Pascalе поиска замкнутых маршрутов по треугольнику

(см. скан)

(см. скан)

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

Рис. 2.7. Двоичное дерево маршрутов по треугольнику на смежной памяти

Во второй части алгоритма выполняется формирование искомых маршрутов (процедура RouteTreeAbc), основой для построения которых служит дерево прохода на рис. 2.7. Для формирования всех маршрутов теперь достаточно подняться по нему от листьев с метками а вершины треугольника к корню, запоминая пройденные метки. Ясно, что число маршрутов будет равно числу вершин на последнем уровне (количество листьев) с меткой а.