Value:integer;

left,right:top_ptr;

end;

Var next_number:integer;

r:top_ptr;

{процедура добавления новой вершины в дерево }

procedure add(r:top_ptr;n:integer);

Var pass,succ:top_ptr;

begin pass:=r;

while pass<>nil do {ищется вершина, после которой надо вставить новую}

begin succ:=pass;

if n<pass^.value then pass:=pass^.left

else pass:=pass^.right;

end;

new(pass); {создание нового элемента}

with pass^ do

begin value:=n;

left:=nil;

right:=nil;

end;

if n<succ^.value then succ^.left:=pass {подсоединение нового элемента}

else succ^.right:=pass;

end;

{Процедура сортировки - нерекурсивный вариант обхода бинарного дерева}

procedure tree1(r:top_ptr);

Var pass:top_ptr;

mem_top:record {имитация стека для хранения указателей}

nom:0..lim; {глубина дерева}

adres:array[1..lim] of top_ptr;{массив указателей на вершины}

end;

begin pass:=r; {корень дерева}

with mem_top do {ищется самый левый узел}

begin nom:=0;

while (pass<>nil) or (nom<>0) do {цикл пока указатель не nil}

if pass<>nil then

begin

if nom=lim then {проверка достаточности места в массиве}

begin writeln('Увеличьте lim');

exit;

end;

nom:=nom+1; {увеличить указатель стека на 1}

adres[nom]:=pass; {запомнить в стеке указатель на число}

pass:=pass^.left; {перейти к левой подветви}

end

else begin pass:=adres[nom]; {если указатель nil, восстановить указатель из стека}

nom:=nom-1; {уменьшить стек на 1, удалив из него то что напечатали}

write(pass^.value:4); {напечатать значение величины}

pass:=pass^.right; {переход к правой пподветви}

end;

end;

end;

{процедура сортировки - рекурсивный вариант обхода дерева}

procedure tree2(r:top_ptr);

begin

if r<>nil then begin

tree2(r^.left);

write(r^.value:4);

tree2(r^.right);

end;

end;

{основная программа}

begin {формирование исходного дерева}

writeln('Введите числа');

read(next_number);

new(r);

with r^ do

begin value:=next_number;

left:=nil;

right:=nil;

end;

read(next_number);

while not EOF do

begin add(r,next_number); {вызов процедуры добавления элемента в дерево}

read(next_number)

end;

readln;

writeln('Последовательность по нерекурсивному варианту:');

tree1(r);

writeln;

writeln('Последовательность по рекурсивному варианту:');

tree2(r);

writeln

end.

Как вывод следует отметить, что использование бинарных деревьев при сортировках позволяет достичь эффективности алгоритма, близкого к эффективности дихотомического (двоичного) поиска. Особенно эффективна работа в случае сбалансированного бинарного дерева. Сбалансированным является бинарное дерево, у которого обе ветви одинаково «ветвисты». Для приведения дерева к сбалансированному виду существуют специальные алгоритмы балансировки. Кроме того, некоторые алгоритмы трансляции выражений, использующиеся в компиляторах для преобразования формул в форму, понятную компьютеру, используют бинарные деревья. Однако, вследствие сложности и объемности подобных алгоритмов, в данную методическую разработку они не включены.