Реализация деревьев

Рассмотрим несколько способов представления дерева.

Пусть дано дерево Т с узлами 1,2,3,… n. Одним из простых представлений дерева Т будет линейный массив А, где каждый элемент А[i] является указателем на родителя узла i. Корень дерева Т отличается от других узлов тем, что имеет нулевой указатель или указатель на самого себя как на родителя. Данное представление использует то свойство дерева, что каждый узел, отличный от корня, имеет только одного родителя. Используя это представление, родителя любого узла можно найти за фиксированное время. Прохождение по любому пути, т.е. переход по узлам от родителя к родителю можно выполнить за время, пропорциональное количеству узлов пути. Так всякий прямоугольный массив можно представить как частный случай древовидной структуры. Например, два представления матрицы размера 3x4.

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

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

Рис. 19.а – Исходное дерево

Рис. 19.б – Представление дерева с помощью связанных списков

Здесь есть массив ячеек заголовков, индексированный номерами узлов. Каждый заголовок указывает на связанный список, состоящий из элементов-узлов. Элементы списка header[i] являются сыновьями узла i, например, узлы 9 и 10 – сыновья узла 3.

Представление деревьев с помощью динамических структур предполагает использование рекурсии и ссылок. Узлы дерева определяются как переменные с фиксированной структурой, т.е. фиксированного типа, где степень дерева определяет число компонент-ссылок, указывающих на поддеревья данного узла. Ссылка на пустое поддерево обозначается через nil. Следовательно, дерево состоит из компонент такого типа:

type node = record

elem: ELEM_TYPE;

left, right: ^node

end;

и может строиться, как показано на рис. 20.

Рис. 20 – Дерево, представленное как динамическая структура данных

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

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

Корень дерева отличается от других узлов тем, что имеет нулевой указатель или указатель на самого себя как на родителя.

Дата добавления: 2015-07-16