деревьев, для которой в цамяти компьютера потребовалось бы выделить меньшее количество слов, предполагая, что одна связь и одно поле INFO с данными могут уместиться в одном слове.

2.3.2. Представление деревьев в виде бинарных деревьев

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

1) Дерево всегда имеет корень, т. е. оно никогда не бывает пустым; каждый узел может иметь О, 1, 2, 3, ... детей.

2) Бинарное дерево может быть пустым, а каждый его уел может иметь О, 1 или 2 детей; мы будем различать левых и правых детей.

Напомним также, что лес является упорядоченным набором некоторого количества деревьев (и даже равного нулю). Поддеревья любого узла дерева образуют лес.

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

(Л)

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

Затем, наклонив эту схему под углом 45° и слегка откорректировав расположение узлов, получим такое бинарное дерево:

и наоборот, после выполнения этих действий в обратном порядке становится очевидно, что любое бинарное дерево соответствует единственному лесу деревьев.

Приведение схемы (1) к схеме (3) имеет чрезвычайно большое значение. Оно назьшается естественным соответствием {natural correspondence) между лесом и бинарными деревьями. В частности, оно задает соответствие между деревьями и особым классом бинарных деревьев, а именно - между бинарными деревьями с корнем, но без правого поддерева. (При этом можно было бы слепса изменить точку зрения и допустить, что корень дерева соответствует заголовку списрса бинарного дерева. В таком случае получим взаимно однозначное соответствие между деревьями с п -f 1 узлами и бинарными деревьями с п узлами.)

Пусть F = (Гх, Гг,..., Г„) - некоторый лес деревьев. Тогда бинарное дерево B(F), соответствующее F, можно строго определить следующим образом.

a) Если п = О, то B{F) пусто.

b) Если п > О, то корень B(F) является корнем (Tj); B{Tii,Ti2, Tim) является

левым поддеревом дерева B(F), где Tn,Ti2, ,Tim - поддеревья корня (Ti); В{Т2,..., Тп) является правым поддеревом дерева B{F).

Эти правила строго определяют приведение схемы (1) к схеме (3).

Иногда удобно изобраяать схему бинарного дерева в виде (2), без поворота на 45°. Тогда соответствующее вид> (1) прошитое {threaded) бинарное дерево будет выглядеть так:

Г...

••••-< Щ (У)

(Ср. с рис. 24, повернув его на 45°.) Обратите внимание на то, что правые связи-нити проходят от крайнего справа ребенка семьи к его родителю. Левые связи-нити не имеют такой естественной интерпретации из-за отсутствия симметрии между левой и правой сторонами.

Представленные в предыдущем разделе идеи обхода можно теперь применить к лесу (т. е. к деревьям). Хотя простой аналогии симметричного порядка обхода здесь нет из-за отсутствия очевидного места вставки корня среди его наследников, зато прямой и обратный порядки можно перенести самым очевидным образом. Для заданного непустого леса эти два основных способа обхода можно определить, как показано ниже.

Обход в прямом порядке

Посетить корень первого дерева Пройти поддеревья первого дерева Пройти оставшиеся деревья

Обход в обратном порядке

Пройти поддеревья первого дерева Посетить корень первого дерева Пройти оставшиеся деревья

Чтобы понять значение этих двух методов обхода, рассмотрим следующее обозначение древовидной структуры на основе вложенных скобок:

{A{B,CiK)),DiE{H),FiJ),G)). (5)

Оно соответствует лесу (1). При этом сначала дерево представляется символом из его корня, а затем дается представление его поддеревьев. В результате представление непустого леса имеет вид заключенного в скобки списка представлений его деревьев, которые разделены запятыми.

Если обход осуществляется (1) в прямом порядке, то узлы посещаются в последовательности АВCKD EHFJG, которая идентична обозначению (5), но без скобок и запятых. Прямой порядок является естественным способом перечисления узлов дерева: сначала указывается корень, а затем - его потомки. Если древовидная структура представлена с помощью строк с отступами, как на рис. 20, (с), то строки располагаются в прямом порядке. В данной книге разделы нумеруются в прямом порядке (см. рис. 22). Таким образом, например, за разделом 2.3 следует раздел 2.3.1, а затем - разделы 2.3.2, 2.3.3, 2.3.4, 2.3.4.1,..., 2.3.4.6, 2.3.5, 2.4 и т. д.

Интересно отметить, что прямой порядок является освященным веками понятием династический порядок {dynastic order). После смерти короля, герцога или графа соответствующий титул передается первому (т. е. старшему) сыну, затем - наследникам первого сына и, если таковых нет, другим сыновьям семьи в том же порядке. (В Англии титул может точно так перейти и к дочери, но это возможно только после смерти (или при отсутствии) всех сыновей.) Теоретически родовой порядок всех узлов аристократических фамилий можно было бы переписать в прямом порядке. Тогда, рассматривая только живых представителей этих фамилий, можно получить порядок престолонаследования (за исключением тех, кто лишен этого права по закону об отречении от престола).

В обратном порядке узлы (1) имеют последовательность BKCAHEJFGD. Она аналогична прямому порядку, но при использовании обозначения на основе скобок,

{{В,{К)С)А, {{H)E,{J)F,G)D), (6)

каждый узел располагается после своих наследников, а не перед ними.

Определения прямого и обратного порядков обхода прекрасно согласуются с естественным соответствием деревьев и бинарных деревьев, поскольку поддеревья первого дерева отвечают левому бинарному поддереву, а оставшиеся деревья - правому бинарному поддереву. Сравнив эти определения с соответствующими определениями на с. 364, получим, что обход леса в прямом порядке вьшолняется точно так, как обход соответствующего бинарного дерева в прямом порядке. Обход дерева в обратном порядке вьшолняется так же, как обход соответствующего бинарного дерева в симметричном порядке. Алгоритмы, рассмотренные в разделе 2.3.1, следовательно, могут быть использованы без изменений. (Обратите внимание, что обратный порядок обхода деревьев соответствует симметричному, а не обратному порядку обхода бинарных деревьев. И это в определенной степени можно считать везением, поскольку, как было показано выше, довольно трудно вьшолнить обход бинарных деревьев в обратном порядке.) Вследствие этой эквивалентности впоследствии мы будем использовать обозначение Р$ для последователя узла Р при