Пример №2

Program D1;

Const

n = 10; {Поле z (ниже) моделирует любые данные в записи,}

Type pt=^uzl;

uzl=Record

lson, rson: pt;

kl:byte;

End; {lson (rson) - ссылки на левого(правого) сына узла}

Var

j:word;

y:uzl;

coren:pt;

Procedure Vkl(Var cor:pt; y:uzl); {cor - ссылка на корень}

Var

nov,ss,tt: pt;

b: Boolean;

Begin

New(nov);

nov^:= y; {Порождение и заполнение переменной nov^;}

If cor = Nil Then

cor:= nov {если дерево пусто, делаем ее корнем}

Else {Цикл движения по трассе поиска:}

Begin

tt:= cor;

Repeat

ss:= tt;

b:= y.kl < ss^.kl;

If b Then

tt:= tt^.lson

Else

tt:= tt^.rson

Until tt = Nil;

If b Then

ss^.lson:= nov

Else

ss^.rson:= nov

End {Произошло связыванием нового узла с найденным отцом ss^}

End;

Procedure Obrab(ss:pt);

Begin

Write(‘SS=’ss^.kl:5)

End;

Procedure Obhod(ss:pt); {Блок обхода БДУ слева}

{Ниже описывается тип элементов стека; в нем поле

sl - ссылка на узел БДУ, ssl - цепная связь в стеке}

Type

pnt=^z;

z=Record

sl:pt;

ssl:pnt

End;

Var

tt: pt;

q,t: pnt; {t - ссылка на верхушку стека}

Begin

t:= Nil; {стек - пуст}

Repeat

While ss <> Nil do

Begin

While ss^.lson <> Nil do {"Левая" трасса}

Begin {Очередной узел включается в стек: }

New(q);

q^.sl:= ss;

q^.ssl:= t;

t:= q;

ss:= ss^.lson{Продвижение по трассе}

End;

Obrab(ss);

ss:= ss^.rson

End;

q:= t;

If t <> Nil Then

Begin

ss:=t^.sl;

t:= t^.ssl; {Взятие ссылки из стека}

Dispose(q); {Освобождение памяти}

Obrab(ss); {Обработка узла как корня поддерева}

ss:= ss^.rson {Начало обхода правого поддерева}

End

Until q = Nil {Если стек опустел, обход БДУ закончен}

End;

 

BEGIN

Randomize;

coren:= Nil; {Порождено пустое дерево упорядочения}

y.lson:= Nil;

y.rson:= Nil;

For j:= 1 to n do {Цикл включения n записей в дерево}

Begin

y.kl:= Random(50); {Переменная y подготовлена к включению}

writeln(‘y=’,y.kl)

Vkl (coren, y) {Включение в ДДУ нового узла - псевдослучайной записи}

End;

Obhod(coren); {Получение упорядоченной последовательности ключей}

Readln; { путем обхода дерева и их вывод}

END.