Для построения такого дерева используется рекурсивное правило:
Пусть требуется построить дерево из N элементов (вершин).
Выберем один из них в качестве корня.
2. Строим левое поддерево с количеством вершин NL = N div 2.
3. Так же строим правое поддерево с числом вершин NR = N-NL-1.
Например, при построении дерева из 5 элементов:
1) один элемент идет на корень;
2) оставшиеся 4 элемента разбиваются на два поддерева:
NL = 2 и NR = 2;
3) в каждом из поддеревьев один элемент идет на корень, а другой - на лист: NL1= 1, NR1= 0.
Очевидно, что для отображения структуры дерева в память ЭВМ требуется построение динамических объектов.
Здесь K-ELEMENT есть вершина дерева, а LEFT и RIGHT - поля ссылок на левую и правую вершины поддеревьев.
Отсюда следует процедура-функция формирования дерева, где используется указанный выше принцип построения рекурсивной функции.
У данной процедуры в качестве параметра-аргумента выступает число элементов (вершин) дерева, а значением функции является ссылка - указатель на следующую вершину (левую и правую). Сами элементы запрашиваются с клавиатуры:
function FORMIRTREE (N: integer): SS;
var Z: SS; NL, NR: integer;
begin
¦ if N = 0 then Z:= nil {Пустое дерево}
¦ else
¦ begin
¦ ¦ NL:= N div 2; NR:= N-Nl-1; new(Z);
¦ ¦ write('Ввести вершину'); readln(Z^.k);
¦ ¦ Z^.right:= FORMIRTREE (NR);
¦ end;
¦ FORMIRTREE:= Z; {Запоминание ссылки на корень дерева}
end.
ПОЯСНЕНИЕ. Сначала все N-1 элементов разбиваем на две части - левую и правую. Затем каждую часть соответственно делим на две. Рекурсия прекращается, когда N становится равным нулю - деление закончено, последняя образованная ссылка указывает на корневой элемент:
1
left
right
2
4
3
5
Дерево имеет 2 уровня, на нижнем (втором) уровне располагаются только левые листы (правые отсутствуют из-за нехватки элементов).
Чтобы вывести дерево на экран дисплея, необходимо предусмотреть обход этого дерева по принципу его создания, т.е. в виде рекурсивной процедуры:
procedure PRINTTREE (Z: ss; X: integer; var Y: integer);
var I: integer;
¦ Y:= (X-5)/5 - 1;{ Подсчет числа уровней }
¦ if Z <> nil then
¦ ¦ PRINTTREE(Z^.right, X+5, Y);
¦ ¦ for I:=1 to X do write(' ');
¦ ¦ writeln(Z^.k);
¦ writeln;
¦ ¦ PRINTTREE(Z^.left, X+5, Y);
ЗАМЕЧАНИЕ. Эта рекурсивная процедура выводит на экран элементы слева направо, причем крайним левым элементом оказывается корень дерева. Между соседними уровнями процедура печатает 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 печати дерева>;
¦ write('Введите число элементов дерева');
¦ y:= 0; {Число уровней дерева}
¦ readln (KOL); DER:= FORMIRTREE (KOL);
¦ writeln; writeln(' Д Е Р Е В О:');
¦ PRINTTREE (DER, 5, y); writeln;
¦ writeln(' Всего', y:3:0,' уровня(ей) дерева.');
ПОЯСНЕНИЕ. Дерево, состоящее из пяти элементов (1,2,3,4,5), будет выведено на экран в виде следующего графа:
ДЕРЕВО
4 \
правое поддерево
/
1 \
2 \
левое поддерево
15.3 Основные операции над деревьями
Над деревьями, как и над другими связными списками, выполняются те же операции: поиск элемента, вставка элемента в дерево и удаление из него.
Так как образование дерева с помощью рекурсивной процедуры идет по двум ветвям - LEFT и RIGHT, то и поиск нужного элемента должен реализоваться по тому же принципу. Сам же поиск может иметь в качестве результата (выхода) значение некоторого признака, свидетельствующего, что такой элемент в списке есть, или даже ссылку на этот найденный элемент (звено).
Итак, процедуру поиска элемента в двоичном дереве организуют в виде рекурсивной процедуры, где есть:
1) входные параметры (параметры-значения) - ссылка на дерево (т.е. на корень дерева, где ищется элемент) и значение элемента поиска;
2) выходной параметр (параметр-переменная) - ссылка на найденный элемент.
Таким образом, имеем следующую процедуру:
procedure POISK(S: SS; ZNACH: integer; var ELEM: SS);
¦ if S <> nil then
if S^.k = ZNACH then ELEM:= S
¦ ¦ POISK(S^.left, ZNACH, ELEM);
¦ ¦ POISK(S^.right, ZNACH, ELEM);
ЗАМЕЧАНИЕ. Из самой процедуры видно, что рекурсия заканчивается по достижению последнего элемента дерева, поэтому переменная ELEM получит значение ссылки на последний элемент, равный ZNACH. Если такого элемента в дереве нет, то переменная ELEM не будет определена, т.к. на оператор ELEM:= S программа выходит только при условии S^.K = ZNACH. В этом случае значение переменной ELEM^.K - "мусор".
В качестве элемента поиска может быть и корень дерева, но тогда никакой рекурсии не произойдет, а будет сразу получен ответ. Итак, процедура POISK "пробегает" все дерево независимо от результатов. Для приостановки поиска после получения положительного результата необходимо организовать досрочный выход, что реализует следующая процедура:
procedure POISK1(S: SS; ZNACH: integer; var ELEM: SS);
¦ 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
¦ ¦ POISK1(S^.left, ZNACH, ELEM);
¦ ¦ if j = 0 then
¦ ¦ POISK1(S^.right, ZNACH, ELEM);
ПОЯСНЕНИЕ. Данная процедура заканчивает работу либо при нахождении искомого элемента, либо при достижении конца дерева. В ней имеются две глобальные переменные I и J, которые должны быть обнулены в основной программе. Переменная I служит для подсчета просмотренных во время поиска элементов, которые попутно выводятся на печать. При нахождении элемента ZNACH в левом поддереве вырабатывается признак J = 1, препятствующий вхождению поиска в правое поддерево.
Условие (S^.k >= N1) and (S^.k <= N2) необходимо для того, чтобы не выводились на печать K - элементы "сухих" ветвей (выходящих из терминальных вершин) при обходе дерева. Здесь N1 - наименьший и N2 - наибольший из введенных в дерево элементов. Обе эти переменные должны быть определены в основной программе.
Вставка элементов в дерево более сложна, чем поиск. Это связано с тем, что каждый элемент (кроме терминального) ссылается на два других (левый и правый) и указания на то, после какого элемента надо осуществить вставку, будет недостаточно. Необходимо знать, в какую из ветвей следует ввести новую вершину.
Если поставить вопрос о вставке нового элемента перед указанным, то, казалось бы, ситуация выглядит проще. Но это на самом деле не так. Ведь при вставке элемента перед указанным также следует держать ссылку на предыдущее звено. Поэтому задача имеет тот же вариант, что и раньше:
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39
