Введение в информационные системы. Брюхомицкий Ю.А. - 70 стр.

UptoLike

Составители:

Рубрика:

вершины, а степень остальных равна двум. Звездное дерево имеет единствен-

ную вершину степени р – 1, а все остальные вершины – концевые.

Рис. 5. 18. Последовательное (а) и звездное (б) деревья

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

дом уровне имеет определенное значение. Дерево, в котором задан порядок

следования

узлов, называется упорядоченным. Примером является дерево, ото-

бражающее последовательность выполнения алгебраических выражений. На

рис. 5.19 изображено упорядоченное дерево, обход которого в соответствии с

указанной нумерацией узлов позволяет получить алгебраическое выражение:

 a

– a

+ a

/ a

Дерево, в котором все узлы представлены одним типом записи, называ-

ется однородным. Примером является генеалогическое дерево. Напротив, в не-

однородном дереве каждый узел представлен различными типами записи. На

рис. 5.20 показано неоднородное дерево, отображающее график технического

обслуживания механизма.

Узлами этого дерева являются записи, отражающие характеристики

технического средства, атрибуты механика, проводившего техобслуживание

дату обслуживания, тип неисправности и т.п. Все эти записи имеют различный

формат, различный состав полей, т.е. являются записями различных типов.

Рис. 5.19. Упорядоченное дерево, отображающее порядок выполнения

алгебраического выражения

7 9

4 6

–

