[стр.-8]
Рис. 2.3. Корневое дерево с тремя поддеревьями
Важной разновидность корневых деревьев являются бинарные деревья. Бинарное дерево Глибо пустое, либо состоит из выделенного узла, называемого корнем, идвух бинарных поддеревьев: левого 7", и правого
Лесом называют упорядоченное множество деревьев. Тогда дерево можно определить как непустое множество узлов, такое, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы образуют лес с поддеревьями корня.
2.2.1. Представление деревьев
памяти
на связанной
Почти все машинные представления деревьев основаны на связанных распределениях. Каждый узел состоит из поля данных и некоторых полей для указателей. следующем примере представления дерева каждый узел имеет по три поля указателей.
first
ь | X | |||
/ | ||||
к | f | X | X | X |
S | X | X | X | * | X | X | г | X | X | X |
Рис. 2.4. Регулярная связанная структура представления дерева
Произвольное дерево с переменным числом поддеревьев всегда можно представить с помощью односторонних списков с использованием двухкомпонентных звеньев, в которых в первом поле находится либо указатель, либо данные, а во втором — всегда указатель.
Рис. 2.5. Универсальная связанная структура представления дерева
Применение указателей и связанных списков придает памяти гибкость, необходимую для представления различных структур. Но при этом легко и перестараться; поэтому следует избегать слишком большого количества указателей; сложность программной поддержки таких структур возрастает «экспоненциально», теряется четкость основной структуры, которую пытаются представить в памяти (последний пример представления дерева это
наглядно подтверждает).
2.2.2. Представление деревьев на смежной памяти
Представление деревьев на смежной памяти (одномерный
массив) предполагает неявное присутствие ребер, переход по которым выполняется посредством арифметических операций над индексами элементов массива — смежной памяти. Формирование таких деревьев с помощью адресной арифметики можно осуществлять двумя способами. Идея первого способа применима при любом постоянном количестве ребер, выходящих из вершин (регулярное дерево). Рассмотрим данный способ формирования на примере двоичного (бинарного) дерева.
Пусть имеется одномерный массив смежных элементов а2,..., ап. Неявная структура двоичного дерева определяется как на рис. 2.6.
По дереву на рис. 2.6 легко перемещаться в обоих направлениях. Переход вниз на один уровень из вершины а [к] можно выполнить, удвоив индекс k (индекс левого поддерева) или удвоив и прибавив 1 (индекс правого поддерева). Переход вверх на один уровень из вершины а[т] можно вьшолнить, разделив m пополам и отбросив
дробную часть. Рассмотренная структура применима к любому дереву с постоянным количеством ребер, выходящих из вершин.
2—2697
-а[1]
а[4
а[5]
а[3]
а[7]
/
\
a[2k]
a[2k+l].
a[m]
a[n]
Рис. 2.6.дерево на смежной памяти с последовательной
нумерацией вершин
Другой способ, основанный на индексной арифметике, применим только для двоичных деревьев. Пусть для представления дерева используется одномерный массив а,-, ам,..., dj. Корнем дерева полагают элемент ат, где индекс элемента корня рассчитывается по формуле т = (/+j)/2\, т.е. середина массива. Левое поддерево располагается в массиве в,, а/+1,..., ат \, а правое поддерево — в массиве ат+1, ат+2,..., dj. Корни поддеревьев рассчитываются подобным же образом, как и корень основного дерева. Второй способ формирования двоичных деревьев на смежной памяти имеет довольно ограниченное применение. Основное его использование — поиск данных, в сортированных массивах, таблицах и т.д.
В качестве примера использования представления регулярных деревьев на смежной памяти рассмотрим решение следующей за-
задается в текстовом файле исходных данных. Результаты расчетов всех маршрутов сохранить в выходном текстовом файле. Каждый маршрут представить как последовательную комбинацию меток а,Ь,с посещаемых вершин треугольника при движении по нему. Каждый маршрут должен включать
метку, где первой и последней меткой должна быть вершина а.
Пример файла исходных данных:
дачи.
Задача. Написать программу поиска всех замкнутых маршрутов длины п< 15 по ребрам треугольника abc. Длину ребра принять равной 1. Начальная и конечная точка искомых маршрутов — вершина а. Длина маршрута п
а
