Предварительные сведения и понятия
В начале введём понятие атрибутированного дерева.
Как известно, дерево - это граф, в котором нет циклов. Мы будем рассматривать ориентированные деревья, то есть деревья, у которых имеется выделенная вершина - корень, и все ребра ориентированы от более близких к корню вершин к более дальним.
Пусть A - некоторая вершина ориентированного дерева. Если она не является корнем, то существует единственная вершина B, из которой в A идет ребро. Вершину B мы будем называть родителем вершины A, а вершину A, соответственно, ребёнком вершины B. В отличие от родителя, детей у вершины может быть много.
Деревья, которые мы рассматриваем, являются атрибутированными, то есть с каждой вершиной могут быть связаны её атрибуты - объекты произвольного типа.
Мы будем рассматривать гетерогенные деревья, то есть деревья, у которых каждая вершина имеет определённый тип. Тип регламентирует, какие дети и атрибуты и какого типа могут быть у вершины данного типа. При этом все дети и атрибуты именуются. Кроме того, в определении типа может содержаться указание на то, что детей (или атрибутов) данного типа может быть несколько (то есть они образуют список), а также на то, что какой-то ребёнок или атрибут является необязательным, то есть может отсутствовать у вершины данного типа.
Заметим, что на рис. нет атрибута name - это возможно, так как в определении типа этот атрибут заявлен необязательным, в то же время список list присутствует всегда, хотя может и не содержать элементов.
Итак, в определении типа вершины должны быть описаны:
- Атрибуты вершины: их имена и типы, а также то, являются ли они обязательными.
- Списки атрибутов: их имена и типы элементов этих списков.
- Дети вершины: их имена и типы, а также то, являются ли они обязательными.
- Списки детей: их имена и типы элементов этих списков.
Детей, атрибуты и списки вершины мы будем называть полями этой вершины.
Пусть имеется конечное множество T типов вершин, замкнутое относительно использования типов (то есть все типы вершин, на которые есть ссылки в определениях типов из этого множества, определены). Далее мы будем рассматривать множество D деревьев, типы вершин которых принадлежат множеству T.
