Материал: Мансуров. Основы программирования в среде 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