Если относительный порядок поддеревьев Т1,... , Тк в эквивалентном определении ордерева фиксирован, то ордерево называется упорядоченным.

Примеры

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

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

2. Для представления блочной структуры программы и связанной с пей структуры областей определения идентификаторов часто используется ориентированное дерево (может быть, неупорядоченное, так как порядок определения переменных в блоке в большинстве языков программирования считается несущественным). На рис. 9.7, б показана структура областей определения идентификаторов а, Ь, с, d, е, причём для отображения иерархии использованы вложенные области.

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

4. Структура вложенности каталогов и файлов в современных операционных системах является упорядоченным ориентированным деревом. Обычно для изображения таких деревьев применяется способ, показанный па рис. 9.7, г.

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

ОТСТУПЛЕНИЕ

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

ЗАМЕЧАНИЕ

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

Т Е О Р Е М А

В упорядоченном ордереве с р узлами существует такая нумерация узлов числами из диапазона 1 ..р, что номера потомков больше номеров предков и номера старших братьев больше номеров младших братьев.

ЗАМЕЧАНИЕ

Указанный порядок обхода часто называют прямым.

ЗАМЕЧАНИЕ

Построенная в доказательстве теоремы нумерация не является единственной нумерацией, обладающей указанными свойствами.