logo search
лекции по МОТС / ДИСКРЕТНАЯ МАТЕМАТИКА Графы

9.2.3. Упорядоченные деревья

Множества T1,..., Тk в экивалентном определении ордерева являются поддере­вьями. Если относительный порядок поддеревьев T1,...,Tk фиксирован, то ор­дерево называется упорядоченным.

Пример

Ориентированные и упорядоченные ориентированные деревья интенсивно ис­пользуются в программировании.

  1. Выражения. Для представления выражений языков программирования, как правило, используются ориентированные упорядоченные деревья. Пример представления выражения а + bс показан на рис. 9.7 слева.

Рис. 9.7. Примеры изображения деревьев в программировании

  1. Для представления блочной структуры программы и связанной с ней струк­туры областей определения идентификаторов часто используется ориентиро­ванное дерево (может быть, неупорядоченное, так как порядок определения переменных в блоке в большинстве языков программирования считается не­существенным). На рис. 9.7 в центре показана структура областей определе­ния идентификаторов a,b,c,d,e, причем для отображения структуры дерева использована альтернативная техника.

  1. Для представления иерархической структуры вложенности элементов данных и/или операторов управления часто используется техника отступов, показан­ная на рис. 9.7 справа.

  2. Структура вложенности каталогов и файлов в современных операционных системах является упорядоченным ориентированным деревом.

  3. Различные «уравновешанные скобочные структуры» (например (a(b)(c(d)(e)))) являются ориентированными упорядоченными деревьями.

ОТСТУПЛЕНИЕ

Тот факт, что большинство систем управления файлами использует ориентированные деревья, отражается даже в терминологии - «корневой каталог диска».

ЗАМЕЧАНИЕ

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

Пример

На рис. 9.8 приведены три диаграммы деревьев, которые внешне выглядят раз­личными. Обозначим дерево слева – (1), в центре - (2) и справа - (3). Как упорядоченные деревья, они все различны: (1)  (2), (2)  (3), (3)  (1). Как ориентированные деревья (1) = (2), но (2)  (3). Как свободные деревья, они все изоморфны: (1) = (2) = (3).

Рис. 9.8. Диаграммы деревьев