Пример №2Program 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.
|
