Нелинейные информационные структуры

Поскольку классификационная компонента представляется посредством графов класса деревьев, то прежде всего следует вспомнить основные положения, касающиеся нелинейных информационных структур. Дерево формально определяют как конечное множество Т, состоящее из одного или более узлов, таких, что: имеется один, специально обозначенный узел, называемый корнем данного дерева. Остальные узлы, исключая корень, содержатся в n ≥ 0 попарно непересекающихся множествах Т₁, Т₂, …,Т_n, каждое из которых в свою очередь является деревом. Деревья Т₁, Т₂, …,Т_n называются поддеревьями данного дерева. Определение рекурсивно, поэтому каждый узел дерева является корнем некоторого поддерева, которое содержится в этом дереве. Число поддеревьев данного узла называют степенью этого узла, а узел с нулевое степенью называют концевым узлом, листом или терминальной вершиной. Уровень узла по отношению к дереву Т определяется следующим образом: говорят, что корень имеет уровень 1, а другие узлы имеют уровень на единицу выше уровня своего корня. На Рис. 4 и Рис. 5 изображены деревья с семью узлами. Корнем дерева является узел А.

 

 

G G

 

D E F F E D

 

B C C B

 

A A

Рис. 4. Пример дерева Рис. 5. Пример симметричного дерева

Дерево на рис. 4 имеет поддеревья {B} и {C, D, E, F, G}. Корнем дерева {C, D, E, F, G} является узел С, имеющий уровень 2 относительно всего дерева. В свою очередь, он имеет три поддерева: {D}, {E}, {F,G} и, следовательно, его степень равна 3. Узлы B, D, E, G являются концевыми узлами. F – единственный узел степени 1, а G – единственный узел уровня 4.

Подразумевается, что все рассматриваемые нами деревья являются упорядоченными, так что деревья, изображённые на Рис. 4 и 5 считаются различными.

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

Деревья могут изображаться другими структурами или, наоборот, служить изображением других логических структур, например, вложенных множеств, вложенных списков, вложенных уступов и т.п. (Рис. 6).

 

H J A

D F B

B C H

E G J

A C

 

(A (B (H) (J))(C (D) (E (G)) (F))) D E

G

Рис. 6. Примеры древовидных структур F

Так всякий прямоугольный массив можно рассматривать как частный случай древовидной структуры. Например, вот два представления матрицы размера 3*4 (Рис. 7):

A[1,1] A[1,2] A[1,3] A[1,4]

A[2,1] A[2,2] A[2,3] A[2,4]

A[3,1] A[3,2] A[3,3] A[3,4]

 

Рис. 7. Представление массива в виде дерева

Другой пример древовидной структуры дают нам алгебраические формулы. Например, формулу a-b*(c/d+e/f) можно изобразить в соответствии с рис. 8.

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

--

a *

b +

/ /