выглядит так:

LLINK f-r- I i ттт

INFO ADBCEFGKHJ- (8)

RTAG J J J J J

Oho подобно представлению (7), но семьи выбраны в порядке "первым вошел - первым вышел", а не в порядке "последним вошел - первым вышел". Представления деревьев в виде (7) или (8) могут рассматриваться как естественный аналог для деревьев последовательного представления линейных списков.

Читатель легко сообразит, как можно создать алгоритм обхода и анализа деревьев, которые показаны выше, в последовательном представлении, поскольку информация из полей LLINK и RLINK позволяет рассматривать эти структуры как полностью связанную древовидную структуру.

Еще один метод, который называется обратным порядком со степенями (postorder with degrees), несколько отличается от описанных выше методов. В случае его использования узлы перечисляются в обратном порядке и вместо связей для каждого узла указывается его степень:

DEGREE 0 0 1 2 0 1 0 1 0 3 /дч

INFO BKCAHEJFGD

Доказательство достаточности этих сведений для характеристики древовидной структуры приводится в упр 2.3.2-10. Такой порядок очень удобен для оценки "снизу вверх" (bottom-up) значений функций, заданных в узлах дерева так, как показано в следующем алгоритме.

Алгоритм F (0»<емка функции, локально определенной в узлах дерева). Пусть / - такая функция узлов дерева, что значение / в узле х зависит только от а; и значений / для детей узла х. Данный алгоритм позволяет с помощью вспомогательного стека оценить / в каждом узле непустого леса.

F1. [Инициализация.] Установить стек пустым, а Р пусть указывает на первый узел леса в обратном порядке.

F2. [Оценка /.] Установить d <- DEGREE (Р). (При первой попытке вьшолнения этого шага значение d будет равно нулю. Вообще, по достижении данного шага верхними элементами d стека по направлению сверху вниз будут элементы f{xd), ..., f{xi), где Xl, Xd - дети узла NODE(P) слева направо.) Оценить /(NODE(P)), используя значения стека f{xd), , f{xi).

F3. [Обновление стека.] Удалить из стека верхние d элементов, а затем разместить значение /(noDE(P)) в верхней части стека.

F4. [Продвижение.] Если Р - последний узел в обратном порядке обхода, то прекратить выполнение алгоритма. (Тогда стек будет содержать следующие элементы по направлению сверху вниз: /(корень(Т„г)), /(корень(Г1)), где Tl, ..., Т,п -деревья данного леса.) В противном случае установить Р равным его последователю в обратном порядке (в представлении (9) это значит, что просто Р Р -Ь с ) и вернуться к шагу F2.

Справедливость алгоритма F доказывается методом индукции по размеру обрабатываемого дерева (см. упр. 16). Этот алгоритм удивительно похож на процедуру

дифференцирования из предыдущего раздела (алгоритм 2.3.2D), которая вычисляет функцию почти такого же типа (см. упр. 3). Та же идея используется во многих программах-иптерпретаторах в связи с оценкой арифметических выражений, заданных в постфиксной системе обозначений. Обсуждение этого вопроса будет продолжено в главе 8 (см. также упр. 17, в котором приводится другая важная процедура, подобная алгоритму F).

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

Первая идея связана с преобразованием представления (3) в представление (6): удалим поля INFO из каждого неконцевого узла и преобразуем эту информацию в новый концевой узел предыдущего узла. Например, деревья (2) в результате такого преобразования примут вид

(10)

При этом предполагается (без потери общности), что все поля INFO в древовидной структуре находятся в концевых узлах. Следовательно, в естественном представлении бинарного дерева из раздела 2.3.2 поля LLINK и INFO являются взаимно исклкь чающими и могут совместно использовать одно и то же поле в каждом узле. Узел может включать такие поля:

LTAG

LLINK или INFO RLINK

Здесь LTAG указывает, является ли второе поле связью. (Сравните это представление, например, с форматом па основе двух слов (10) из раздела 2.3.2.) Сокращая длину поля INFO с б до 3 байт, получим, что каждый узел можно разместить в одном слове. Обратите, однако, внимание на то, что вместо 10 узлов мы теперь используем 15 узлов. Для леса (10) потребуется 15 слов памяти, тогда как для (2) - 20, однако в последнем случае поля INFO занимают 60 байт по сравнению с 30 байт в первом случае. Таким образом, при использовании представления (10) нельзя получить никакой экономии памяти, если не применяется дополнительное пространство в полях INFO. Дело в том, что удаление полей LLINK в (10) компенсируется добавлением почти такого же количества новых полей RLINK в добавленных узлах. Более подробно различия между этими представлення.ми описываются в упр. 4.

В представлении дерева как стандартного бинарного дерева для поля LLINK точнее было бы использовать название LCHILD, поскольку оно направлено от узла-родителя к крайнему слева узлу-ребенку. Этот узел-ребенок обычно является "самым младшим ребенком дерева, так как легче всего вставить узел слева от семьи, чем справа. Поэтому сокращение LCHILD может трактоваться, как "последний ребенок" или "крайний ребенок".

Во многих пр1ложениях древовидных структур довольно часто требуется обращаться к узлам дерева как по направлению вверх, так и по направлению вниз. Прошитое дерево-«1редоставляет возможность перехода к верхним узлам, хотя и с небольшой скоростью. Однако иногда лучше и.меть в каждом узле третью связь PARENT. При ее наличии получим трижды связанное дерево (triply linked tree), каждый узел которого имеет связи LCHILD, RLINK и PARENT. На рис. 26 показано, представление трижды связанного дерева для (2), а пример его использования приводится в разделе 2.4.

Рис. 26. Трижды связанное дерево

Ясно, что связи PARENT самой по себе достаточно для полного описания структуры любого ориентированного дерева (или леса), поскольку схему любого дерева можно нарисовать, зная все направленные вверх связи. Каждый узел, за исключением корня, имеет только одного родителя, но может иметь сразу несколько детей. Поэтому для их определения проще использовать связи, направленные вверх, а не вниз. Почему же тогда они до сих пор не рассматривались? Ответ, конечно же, заключается в том, что направленные вверх связи не всегда пригодны для используемого приложения, так как порой очень трудно быстро определить, является ли узел концевым, или найти какого-либо ребенка узла. Однако есть очень важное приложение, для работы с которым достаточно иметь только связи, направленные вверх. Рассмотрим вкратце элегантный алгоритм обработки отношений эквивалентности, предложенный М. Дж. Фишером (М. J. Fischer) и Б. \. Галлером (В. А. Galler).

Отношением эквивалентности (equivalence relation) "=" называется отношение между элементами множества S, которое удовлетворяет следующим условиям для любых (необязательно различных) объектов х, у и z множества 5.

i) Если х = у и у = Z, то X = Z. (Транзитивность.)

ii) Если X = у, то у = X. (Симметричность.)

iii) X = X. (Рефлексивность.)

(Сравните это определение с определением отношения частичного упорядочения, предложенного в разделе 2.2.3. Они сильно различаются несмотря на совпадение двух из трех условий.) Примерами отношений эквивалентности являются отноше-