Построение идеально сбалансированного дерева

Для построения такого дерева используется рекурсивное правило:

1. Пусть требуется построить дерево из 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
left			left
	3		right	5		right

Дерево имеет 2 уровня, на нижнем (втором) уровне располагаются только левые листы (правые отсутствуют из-за нехватки элементов).

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

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), будет выведено на экран в виде следующего графа:

ДЕРЕВО