Материал: Мансуров. Основы программирования в среде Lazarus. 2010

4.3 Динамические структуры данных

____________________________________________________________________

Reset(fder); i:= 1;

while not Eof(fder) do begin

Read(fder, DER[i].TElem);

Read(fder, DER[i].TLeft);

Read(fder, DER[i].TRight); inc(i);

end;

Close(fder); ERROR:= false; EMPTY:= false; i:= 1;

writeln(UTF8ToConsole('Обход двоичного дерева слева')); while DER[i].TElem <> -1 do

begin

if DER[i].TLeft <> -1 then begin

ELEM:= i;

Put_Stack(ELEM, CTEK, ukaz, ERROR); if ERROR = true then

begin

writeln(UTF8ToConsole('Ошибка! Переполнение стека.')); writeln(UTF8ToConsole('Увеличьте размер массива')); writeln(UTF8ToConsole('Нажмите любую клавишу')); readkey;

exit;

end;

i:= DER[i].TLeft;

356

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

end else begin

repeat writeln(DER[i].TElem);

Take_Stack(ELEM,CTEK,ukaz,EMPTY); if EMPTY = true then break;

i:= ELEM;

until DER[i].TRight <> -1; if EMPTY = true then break; writeln(DER[i].TElem);

i:= DER[i].TRight; end;

end;

writeln(UTF8ToConsole('Нажмите любую клавишу')); readkey;

end.

Теперь напишем программу, где ввод дерева производится с клавиатуры.

program Derevo_Left;

{$mode objfpc}{$H+}

{Процедуры работы со стеком мы оформили в виде модуля!} uses

CRT, FileUtil, STACK; var

CTEK: array [1..SizeOfArrayCTEK] of T; DER: array[1..SizeOfArrayDER] of T; ukaz: integer;

i,ELEM:integer;

357

4.3 Динамические структуры данных

____________________________________________________________________

ERROR, EMPTY: Boolean;

k: integer;

answ: char;

begin

{Ввод дерева}

writeln(UTF8ToConsole('Вводите дерево строго')); writeln(UTF8ToConsole('сверху вниз и слева направо')); writeln(UTF8ToConsole('Чтобы закончить ввод введите -1'));

i:= 1;

while true do

begin

writeln(UTF8ToConsole('Введите корень.'));

{$i-} // отключение стандартного режима контроля ввода repeat

ERROR:= false; readln(k);

ERROR:= (IoResult <> 0);

if ERROR then {если ERROR=true, значит произошла ошибка при

вводе}

writeln(UTF8ToConsole('Ошибка! Введите номер вершины')); until not ERROR;

{$+} // восстановление стандартного режима контроля ввода/вывода

DER[i].TElem:= k; if k = -1 then begin

DER[i].TLeft:= -1;

DER[i].TRight:= -1; break;

end;

358

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

writeln(UTF8ToConsole('Текущая вершина имеет поддеревья?'));

writeln(UTF8ToConsole('Ответ (y/n)')); repeat

readln(answ);

if (answ = 'y') then begin

DER[i].TLeft:= 2 * i;

DER[i].TRight:= 2 * i + 1;

end else begin

DER[i].TLeft:= -1;

DER[i].TRight:= -1; end;

until (answ = 'n') or (answ = 'y'); inc(i);

end;

{Обход заданного двоичного дерева слева} {Инициализация указателя стека (начального индекса в массиве)}

ukaz:= 1;

ERROR:=false;

EMPTY:=false;

i:= 1;

writeln(UTF8ToConsole('Обход двоичного дерева слева'));

while DER[i].TElem <> -1 do

begin

if DER[i].TLeft <> -1 then

begin

ELEM:= i;

359

4.3 Динамические структуры данных

____________________________________________________________________

Put_Stack(ELEM,CTEK,ukaz,ERROR); if ERROR = true then

begin

writeln(UTF8ToConsole('Ошибка! Переполнение стека.')); writeln(UTF8ToConsole('Увеличьте размер массива')); writeln(UTF8ToConsole('Нажмите любую клавишу')); readkey; exit;

end;

i:= DER[i].TLeft; end

else begin

repeat writeln(DER[i].TElem);

Take_Stack(ELEM, CTEK, ukaz, EMPTY); if EMPTY = true then break;

i:= ELEM;

until DER[i].TRight <> -1; if EMPTY=true then break; writeln(DER[i].TElem);

i:= DER[i].TRight; end;

end;

writeln(UTF8ToConsole('Нажмите любую клавишу')); readkey;

end.

Намучились с вводом дерева? Действительно, муторное это занятие. К сча-

стью, в реальных задачах деревья никто и никогда не вводит. Они формируют-

360