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

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

____________________________________________________________________

телей мы рассмотрим в следующем разделе. Для того чтобы записать индексы на левые и правые поддеревья в массиве поступим следующим образом: если вершина – корень имеет номер индекса n, то левое и правое поддерево – соот-

ветственно 2*n и 2*n+1. Нумерация начинается с n=1. Ячейка со значением -1

обозначает отсутствие вершины. Сначала сделаем вручную распределение ин-

дексов в массиве для нашего дерева, табл. 4.1.

Визуально массив, реализующий наше исходное двоичное дерево можно представить следующим образом, рис. 4.29.

351

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

____________________________________________________________________

При обходе этого двоичного дерева слева последовательность обработки вершин будет следующей:

8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15

Блок схему алгоритма обхода мы с вами уже рассматривали, см. рис. 4.23.

Последовательность состояний стека для данного алгоритма будет сле-

дующей, рис. 4.30:

Рис. 4.300. Состояния стека при обходе двоичного дерева слева

Напишем программу обхода двоичного дерева слева. Сначала отладим программу для уже готового дерева. Далее мы научимся организовывать ввод дерева в диалоговом режиме с клавиатуры. Для этого подготовьте в текстовом

352

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

____________________________________________________________________

редакторе "Блокнот" (NotePad) файл представления двоичного дерева в виде массива приведенного в таблице 4.1 с именем "derevo.dat" и разместите его в папке с проектом. Можете взять готовый файл из прилагаемого к книге DVD

диска. В соответствии со структурой массива будем использовать запись вида:

type

T = record

TElem: integer;

TLeft: integer;

TRight: integer;

end;

Где T – элемент массива типа запись, TElem вершина дерева, TLeft ин-

декс в массиве левого поддерева, TRight индекс в массиве правого поддерева.

Чтобы не загромождать текст основной программы, процедуры

Put_Stack и Take_Stack оформим в виде отдельного модуля STACK.

Текст модуля:

unit STACK; interface const

SizeOfArrayCTEK= 100;

SizeOfArrayDER= 100;

type

T = record

TElem: integer;

TLeft: integer;

TRight: integer;

end;

353

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

____________________________________________________________________

procedure Put_Stack(var ELEM: integer; var CTEK: array of T; var ukaz: integer; var ERROR: Boolean);

procedure Take_Stack(var ELEM: integer; var CTEK: array of T; var ukaz: integer; var EMPTY: Boolean);

implementation

{ ======================================== } procedure Put_Stack(var ELEM: integer;

var CTEK: array of T; var ukaz: integer; var ERROR: Boolean);

{ ======================================== } begin

if ukaz > SizeOfArrayCTEK then ERROR:= true

else begin

CTEK[ukaz].TElem:= ELEM; ukaz:= ukaz + 1;

end;

end;

procedure Take_Stack(var ELEM: integer; var CTEK: array of T; var ukaz: integer; var EMPTY: Boolean);

354

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

____________________________________________________________________

begin

if ukaz = 1 then EMPTY:= true

else begin

ukaz:= ukaz - 1;

ELEM:= CTEK[ukaz].TElem; end;

end;

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; ERROR, EMPTY: Boolean; fder: TextFile;

begin

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

ukaz:= 1;

{Чтение из файла дерева}

Assign(fder, 'derevo.dat');

355

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