Отметим, что эта процедура подсчитывает число формируемых узлов с помощью глобальной переменной-счетчика k. k-му узлу присваивается k-u ключ, а поскольку ключи упорядочены в алфавитном порядке, k, умноженное на постоянный масштабный коэффициент, дает горизонтальную координату каждого ключа; это значение сразу запоминается вместе с остальной информацией. Заметим также, что мы отказались от соглащения, что ключи являются целыми числами, и счИ' таем, что они относятся к типу alfa, означающему массивы символов определенного (максимального) размера, на которых задан алфавитный порядок.

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

k := 0; root :== iree{0,n)

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

Теперь мы можем перейти к следующему этапу: отображению дерева на страницу. В этом случае ;мы должны прО' двигаться строго последовательно от уровня корня вниз. На каждом шаге обрабатывается один ряд (уровень) узлов. Но каким образом мы находим' узлы, лежащие в одном рядУ? Для этой цели, а именно связывания вместе узлов, находя щихся на одном уровне, ранее мы ввели поле записи, назЫ* ваемое link. Устанавливаемые связи показаны пунктирным? линиями на рис. 4.39. На каждом этапе работы предпола* гается наличие цепочки, связывающей узлы, которые нужн напечатать в одном горизонтальном ряду. Мы называем эту

ваемую кее, подобную той, которая использовалась в программе 4.3, Параметры i и / ограничивают значения индексов узлов, которые принадлежат дереву. Его корень определяется как узел с индексом щ. Но прежде всего нам нужно описать тип переменных, представляющих узлы. Они должны содер. жать две ссылки на поддеревья и ключ узла. Для целей, которые будут обсуждаться на следующем этапе, вводятся также два дополнительных поля, называемые pos и link. Описания типов показаны в (4.79), и процедур а-функция включена в программу 4.6.

type ref = \ node;

node = record key: alfa;

pos: lineposition; (4.79)

left, right, link: ref

цепочку current (текущей). Рассматривая каждый узел, мы определяем его потомков (если они имеются) и связываем йХ во вторую цепочку, которую мы называем next (следующей). Когда мы продвигаемся на один уровень вниз, цепочка fiext становится цепочкой current, а next присваивается значение nil.

PARIS

ROME

Рис. 4.39. Дерево, нарисованное с псмощыо программы 4.6.

Подробно ЭТОТ алгоритм описан в программе 4.6. Следующие замечания могут прояснить некоторые моменты:

1. Списки (цепочки) узлов, находящихся на одном уровне, формируются слева направо, в результате самый левый

(узел оказывается последним. Поскольку узлы должны печататься в порядке появления, список нужно инвертировать. Это происходит в тот момент, когда цепочка next становится цепочкой current.

2. Строка, в которой печатаются ключи (главная строка), содержит также горизонтальные части дуг (см. рис. 4.40). Переменные wl, u2, 3, ы4 обозначают начальные и конечные позиции левых и правых горизонтальных дуг узла.

3. Каждой главной строке предшествуют три строки, изображающие вертикальные части дуг..

Теперь опишем структуру программы 4.6. Ее две основные Составляющие - это процедура построения оптимального дерева поиска при заданном распределении весов w и процедура изображения дерева с заданными индексами узлов г. Вся Программа предназначена для обработки текстов программ.

LABEL-

ELSE-

-CONST-

rBEGINn

rDOWNTOi rFILE-i f-IF-i

FUNCTIONn

rPROCEDURE

rN Li

ARRAY CASED V DO END FOR GOTO IN MOD OF PROGRAM

Рис. 4.40. Идеально сбалансированное дерево. .(Средняя длина пути сба

-SET-

I-UNTIL

iORDn. f-TO-I

WHILEi

REPEAT THEN TYPE VAR WITH

кансированного дерева = 5.566.)