Хотя задача этого алгоритма - поиск, его можно при^д нить и для сортировки. В самом деле, он очень напоминае метод сортировки включением, а поскольку вместо массив используется дерево, пропадает необходимость перемещен/ компонент выще места включения. Сортировку с помощыц дерева можно запрограммировать почти столь же эффе т 5БН0, как и лучщие методы сортировки массивов. Но небхо^ димо принять некоторые меры предосторожности. Разумеется при появлении одинаковых ключей, теперь надо поступать иначе. Если в случае х - p.key алгоритм работает так же как и в случае х > p\.key, то он представляет метод устойчивой сортировки, т. е. элементы с одинаковыми ключами появляются в той же последовательности при обычном обходе дерева, что и в процессе их включения в дерево.

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

Наша цель - написать программу, которая (читая текст f и печатая его с добавлением последовательных номеров строк) собирает все слова этого текста, сохраняя при этом номера строк, в которых они встречались. Когда этот просмотр закончится, нужно построить таблицу, содержащую все собранные слова в алфавитном порядке, со списками соответствующих строк.

Очевидно, что дерево поиска (называемое также лексикографическим деревом) лучше всего подходит для представления слов, встречающихся в тексте. Теперь каждый узел не только содержит слово в качестве значения ключа, но одновременно представляет собой начало списка номеров строк. Каждую запись номера строки мы будем называть отметкой. Следовательно, в этом примере мы встречаем и деревья, и линейные списки. Программа состоит из двух основных частей (см. программу 4.5): фазы чтения текста и построения дерева и фазы печати таблицы. Ясно, что последняя является частным случаем процедуры обхода дерева, где посещение каЖ' дого узла предполагает печать значения ключа слова и проход по связанному с ним списку номеров строк (отметок)-Кроме того, полезно привести еще некоторые пояснения, о носящиеся к программе 4.5:

1. Словом считается любая последовательность букв и цифР начинающаяся с буквы.

yogram crossref(f,oiifpiil);

ifiocmpoehue ;.;абпицы перекрестных ссылок с использованием

\воичного дерева]

const с1 = 10; {длина слова]

с2 =! 8; [количество слов в строке]

сЗ - б; [количество цифр в числе]

с4 = 9999; [максимальный номер сщроки] fype alfa - packed array [1.. cl] of char;

wonlref ~ \,vorih

itemref у (cm;

word = record Ae;: alfa;

first, last; Itemref; Ш left, right: wordrcf

Ш. end ;

В item = packed record В lno:0..c4;

Wr next: itemref

end ;

yar roof: wordref;

k,kl: integer;

n: integer; [номер текущей строки]

Щ id: alfa; Щ f: text;

й: array [I.. cl] oichar; octdate search {yat ivi: -wordref);

таг w: wordref; x: itemref; legin w := wl; if IV - nil then begin new{w); new{x); With \v\ do

begin Aej := id; left ;= nil; right I- nil;

first :~ x; last :-= x end ;

л:./ о := n; x\.next :- nil; н1 : w end else

if < w\.key then jetfrcCwt./O else Uid> w\.key then лсйгсА(и'}.п^йО else begin/7w(x); x\.ho :- n; x\.next:- nil; wdasfMext := л;; \v].last:~ x

® d [search] ;

procedurei?ra /e<H; wordref);

procuvxepnntword(w: -word);

var I: integer; x: itemref; begin write ( , w.key); X := w.first; / := 0; repeat if 1 = c2 then begin writeln;

I := 0; write ( :cl+l) .

end ;

/ := l+l; write (х|./ о:сЗ); x := x\.next until x = nil: writeln end [printword] ; begin ii w Ф nil then

begin printtreejwl.left);

prinfword(wi); printtree(w\.right)

end [printtree] ;

begin roo := nil; n := 0; kl := cl; page {output); reset{f);

while -leo/ (/) do

begin if и = e4 then и := 0;

n := и+1; write {п:сЪ); [следующая строка] writeif ); while -ieo/л (/) do begin [просмотр непустой строки] if /Г in [a .. г'] then begin := 0;

repeat if fc < cl then

begin fc := fc+1; :=/t;. енй ;

write (/t);- get (/) until -i(/t in [a .. z,0.. 9]); if fc > fcl then fcl := fc else repeat fl[fcl] := fcl := fcl-1 until fcl = fc; pack {a,l,id); search{root) end else

begin [проверка на кавычку или комментарий] if /Г = then

repeat write{f\); get{f)

until /1 - else if /t - { then ...