Алгоритмический язык Паскаль (стр. 26 из 31)

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

procedure PRINTTREE (Z: ss; X: integer; var Y: integer);

var I: integer;

begin

¦ Y:= (X-5)/5 - 1;{ Подсчетчислауровней }

¦ if Z <> nil then

¦ begin

¦ ¦ PRINTTREE(Z^.right, X+5, Y);

¦ ¦ for I:=1 to X do write(' ');

¦ ¦ writeln(Z^.k);

¦ writeln;

¦ ¦ PRINTTREE(Z^.left, X+5, Y);

¦ end;

end.

ЗАМЕЧАНИЕ. Эта рекурсивная процедура выводит на экран элементы слева направо, причем крайним левым элементом оказывается корень дерева. Между соседними уровнями процедура печатает 5 пробелов, а между элементами одного уровня - одну строчку. В процедуре параметр Y, как выходной, служит для указания числа уровней построенного дерева. Формула (X-5)/5-1 дает число уровней, т.к. по построению между элементами соседних уровней находится 5 пробелов, а в завершение работы этой процедуры последним печатается самый левый (самый нижний и, значит, самый удаленный от левого края экрана) лист дерева:

Теперь, имея рекурсивную функцию FORMIRTREE формирования дерева и рекурсивную процедуру PRINTTREE печати его элементов, можно записать основную программу построения и печати дерева с указанным числом вершин.

program TREE;

type SS = ^ZVENO;

ZVENO = record

K: integer;

left, right: SS;

end;

var KOL: integer; Y: REAL; DER: SS;

{KOL - число элементов дерева; DER - ссылка на корень дерева}

< рекурсивная функция FORMIRTREE формирования дерева>;

< рекурсивная процедура PRINTTREE печати дерева>;

begin

¦ write('Введите число элементов дерева');

¦ y:= 0; {Число уровней дерева}

¦ readln (KOL); DER:= FORMIRTREE (KOL);

¦ writeln; writeln(' ДЕРЕВО:');

¦ PRINTTREE (DER, 5, y); writeln;

¦ writeln(' Всего', y:3:0,' уровня(ей) дерева.');

end.

ПОЯСНЕНИЕ. Дерево, состоящее из пяти элементов (1,2,3,4,5), будет выведено на экран в виде следующего графа:

ДЕРЕВО

4 \	правое поддерево
/	5
1 \
2 \
3	левое поддерево

15.3 Основные операции над деревьями

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

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

Итак, процедуру поиска элемента в двоичном дереве организуют в виде рекурсивной процедуры, где есть:

1) входные параметры (параметры-значения) - ссылка на дерево (т.е. на корень дерева, где ищется элемент) и значение элемента поиска;

2) выходной параметр (параметр-переменная) - ссылка на найденный элемент.

Таким образом, имеем следующую процедуру:

procedure POISK(S: SS; ZNACH: integer; var ELEM: SS);

begin

¦ if S <> nil then

if S^.k = ZNACH then ELEM:= S

¦ else

begin

¦ ¦ POISK(S^.left, ZNACH, ELEM);

¦ ¦ POISK(S^.right, ZNACH, ELEM);

¦ end;

end.

ЗАМЕЧАНИЕ. Из самой процедуры видно, что рекурсия заканчивается по достижению последнего элемента дерева, поэтому переменная ELEM получит значение ссылки на последний элемент, равный ZNACH. Если такого элемента в дереве нет, то переменная ELEM не будет определена, т.к. на оператор ELEM:= S программа выходит только при условии S^.K = ZNACH. В этом случае значение переменной ELEM^.K - "мусор".

В качестве элемента поиска может быть и корень дерева, но тогда никакой рекурсии не произойдет, а будет сразу получен ответ. Итак, процедура POISK "пробегает" все дерево независимо от результатов. Для приостановки поиска после получения положительного результата необходимо организовать досрочный выход, что реализует следующая процедура:

procedure POISK1(S: SS; ZNACH: integer; var ELEM: SS);

begin

¦ if (S^.k >= N1) and (S^.k <= N2) then

¦ begin write(S^.k:3); i:= i+1; end;

¦ if S^.k = ZNACH then begin j:=1;ELEM:= S end

¦ else if S <> nil then

¦ begin

¦ ¦ POISK1(S^.left, ZNACH, ELEM);

¦ ¦ if j = 0 then

¦ ¦ POISK1(S^.right, ZNACH, ELEM);

¦ end;

end.

ПОЯСНЕНИЕ. Данная процедура заканчивает работу либо при нахождении искомого элемента, либо при достижении конца дерева. В ней имеются две глобальные переменные I и J, которые должны быть обнулены в основной программе. Переменная I служит для подсчета просмотренных во время поиска элементов, которые попутно выводятся на печать. При нахождении элемента ZNACH в левом поддереве вырабатывается признак J = 1, препятствующий вхождению поиска в правое поддерево.

Условие (S^.k >= N1) and (S^.k <= N2) необходимо для того, чтобы не выводились на печать K - элементы "сухих" ветвей (выходящих из терминальных вершин) при обходе дерева. Здесь N1 - наименьший и N2 - наибольший из введенных в дерево элементов. Обе эти переменные должны быть определены в основной программе.

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

Если поставить вопрос о вставке нового элемента перед указанным, то, казалось бы, ситуация выглядит проще. Но это на самом деле не так. Ведь при вставке элемента перед указанным также следует держать ссылку на предыдущее звено. Поэтому задача имеет тот же вариант, что и раньше:

	предыдущее звено;
	новое звено;
	фиксированное звено;

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

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

1) вставлять новый элемент S2 между S и S1;

2) если S ссылается на S1 левым полем, то вставляемый элемент S2 будет также ссылаться на S1 левым полем;

3) если S ссылается на S1 правым полем, то и вставляемый элемент должен ссылаться на S1 правым полем.

а). Левое			б). Правое
	S	S
…	…
	S2	S2
nil	nil
S1	S1
…	…

Отсюда следует процедура вставки (нерекурсивная):

procedure VSTAVKA (S, S1, S2: SS);

begin

¦ if S^.left = S1 then

¦ begin

¦ ¦ S^.left:= S2;

¦ ¦ S2^.left:= S1;

¦ ¦ S2^.right:= nil;

¦ end

¦ else

¦ begin

¦ ¦ S^.right:= S2;

¦ ¦ S2^.right:= S1;

¦ ¦ S2^.left:= nil;

¦ end;

end.

ЗАМЕЧАНИЕ. В отличие от процедуры POISK здесь нет на входе явного указания на корень дерева. Однако при указании двух соседних вершин в ссылках на них фигурирует ссылка на корень дерева. Например, для вставки в дерево DER некоего элемента EL между вторым и третьим элементами левого поддерева необходимо выполнить следующие операторы: