СД типа дерево

НЕЛИНЕЙНЫЕ СТРУКТУРЫ ДАННЫХ.

Модули, экспортирующие объекты.

Типы объектов обычно используются в интерфейсной части модуля, а функции и процедуры – в секции реализации. В секции инициализации размещаются вызовы конструкторов. Из виртуализации объекта следует важное свойство – расширяемость или открытость программ, основанных на ООП. Это связано с тем, что модули, содержащие какие-либо программно-инструментальные средства (графика, работа с меню, и т.д.), могут поставляться конечным пользователям в виде подключаемых TPU-файлов с распечаткой типов объектов, находящихся в интерфейсной части. Пользователь такого модуля, используя свойство полиморфизма и наследования, добавляет новые объекты, который настраивают те или иные программные средства на ту или иную предметную область.

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

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

1) Имеется один специально обозначенный узел, называемый корнем данного дерева.

2) Остальные узлы (исключая корень) содержатся в m>=0 попарно не пересекающихся множествах Т₁, Т₂, …, Т_m, каждое из которых в свою очередь является деревом. Деревья Т₁, Т₂, …, Т_m называются поддеревьями данного корня.

A: T₁ = {B, E, F, G} T₂ = {C, H} B: T₁₁ = {E} T₁₂ = {F} T₁₃ = {G} C: T₂₁ = {H}

Рассмотрим один из способов изображения структуры дерева:

Если подмножества Т₁, Т₂, …, Т_m упорядочены, то дерево называют упорядоченным. Если два дерева считаются равными и тогда, когда они отличаются порядком, то такие деревья называются ориентированными деревьями. Конечное множество непересекающихся деревьев называется лесом.

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

Количество подмножеств для данного узла называется степенью узла. Если такое количество равно нулю, то узел является листом. Максимальная степень узла в дереве – степень дерева. Уровень узла – длина пути от корня до рассматриваемого узла. Максимальный уровень дерева – высота дерева.

Структуру дерева можно изображать и с помощью следующих способов:

Дата добавления: 2014-01-07