Организация в памяти и рекурсивный обход

Дерево является частным случаем графа и представляет собой множество вершин, связанных ребрами. Мы будем рассматривать деревья в практическом плане с точки зрения их представления и использования. Есть много определений деревьев. По одному из них, дерево – это связный граф без циклов. Рекурсивное определение: дерево – это либо пустое дерево, либо вершина, связанная ребрами с конечным числом дереьев. Число вершин дерева на единицу превышает число ребер.

Дерево является иерархически организованной структурой. Основой дерева является корень. Каждая вершина, кроме корня, имеет единственного предшественника, называемого отцом. Последователи вершины называются ее сыновьями. Вершины, не имеющие сыновей, называются листьями. Деревья принято изображать корнем вверх.

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

Деревья обязаны своим названием обычным деревьям. С помощью деревьев представляются иерархически организованные объекты. Например, руководителю предприятия можно поставить в соответствие корень. Его заместители соответствуют сыновьям корня. Руководители служб, подчиняющиеся напрямую заместителям, образуют следующий уровень иерархии. Листьям будут соответствовать рядовые сотрудники, не имеющим подчиненных.

Другим примером может служить некоторое техническое изделие. Всему изделию ставится в соответствие корень дерева. Основным узлам, на которые разбирается изделие, соответствуют сыновья корня. Подобным образом строится все дерево. Деталям, считающимся неразборными, соответствуют листья дерева.

В программировании используется древовидная структура модулей приложения. Алгебраическое выражение может быть представлено бинарным деревом, переменные и константы которого соответствуют листьям, а знаки операций – остальным вершинам. Данный пример подробнее рассматривается ниже.

Самым простым представлением дерева является список его вершин. Элемент списка содержит информационную часть, указание на отца и список сыновей. Недостаток такого представления в том, что степени вершин дерева могут значительно отличаться. Приходится резервировать память, ориентируясь на максимальную степень, что часто крайне нерационально.

Другим способом записи дерева является упаковка в два списка. Первый список соответствует вершинам, второй – сыновьям этих вершин, перечисляемым без разделителей в порядке рассмотрения вершин. Каждый элемент первого списка содержит информационную часть соответствующей вершины, указание на отца, количество сыновей и ссылку на ту часть второго списка, откуда начинается перечисление сыновей. Ссылка может задаваться указателем для динамических списков или индексом массива. Указанный способ экономичен по памяти, но вызывает трудности при корректировке дерева. Например, добавление новой вершины ведет к изменению большого числа ссылок.

В приложениях, использующих системы управления базами данных, используют только ссылку на отца. Тогда нахождение сыновей сводится к поиску всех записей с определенным значением поля отца. Такой поиск обеспечивается средствами системы.

Еще один способ записи связан с использованием бинарного дерева. Первый (старший) сын вершины исходного дерева представляется левым сыном соответствующей вершины бинарного дерева, а следующий сын того же отца (то есть брат) - правым сыном. Отсутствие левого сына бинарного дерева является признаком листа исходного дерева. Корень наоборот не должен иметь правого сына.

Например, сильно ветвящееся дерево

представляется бинарным деревом

Обходом дерева называется обработка всех его вершин в некотором порядке. Рассмотрим варианты обхода бинарного дерева, состоящего из корня R и листьев A и B. Имеются три стандартных порядка обхода: сверху вниз, снизу вверх и слева направо.

При обходе сверху вниз корень посещается раньше листьев, то есть вершины перечисляются в порядке R,A,B. Обход снизу вверх дает порядок A,B,R. Слева направо вершины обходятся в порядке A,R,B.

Указанные варианты обхода обобщаются на случай любого бинарного дерева. Так если вершина A является корнем поддерева, то на это поддерево рекурсивно распространяется выбранный вариант обхода.

Рассмотрим описанные варианты обхода на примере дерева, представляющего алгебраическое выражение (A+B/C)*(D-E*F). Как указывалось раньше, этому выражению соответствует дерево

Обход сверху вниз дает префиксную форму записи выражения (знак перед операндами): +A/BC-D*EF. Обход снизу вверх приводит к постфиксной форме (знак после операндов): ABC/+DEF*-*. При обходе слева направо получается инфиксная форма (знак между операндами): A+B/C*D-E*F.

Префиксная форма называется еще польской, а постфиксная – обратной польской записью. Обе эти формы не требуют скобок, тогда как в инфиксной форме скобки необходимы. Обратная польская запись широко используется в трансляторах.

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

Program SozdTree; { создание и обходы бинарного дерева }

Uses Crt;

Type

ukaz=^uzel;

uzel=record

Key: integer;

Left, Right: ukaz;

end;

Var

Kon, Root: ukaz;

K, L, N: integer;

Prizn: char;

Procedure Sozd(T: ukaz);

Begin

if T<>Nil then

begin

Write('Введите номер вершины ');

ReadLn(T^.Key);

Write('У вершины ', T^.Key, ' имеется левый сын(д/н) ? ');

ReadLn(Prizn);

if Prizn='н' then T^.Left:=Nil

else

begin

WriteLn('Переходим к левому сыну вершины ', T^.Key);

New(Kon);

T^.Left:=Kon

end;

Sozd(T^.Left);

Write('У вершины ', T^.Key, ' имеется правый сын(д/н) ? ');

ReadLn(Prizn);

if Prizn='н' then T^.Right:=Nil

else

begin

WriteLn('Переходим к правому сыну вершины ', T^.Key);

New(Kon);

T^.Right:=Kon

end;

Sozd(T^.Right)

end

End;

Procedure PechPr(T: ukaz);

Begin

if T<>Nil then

Begin

WriteLn('Вершина ', T^.Key);

PechPr(T^.Left);

PechPr(T^.Right);

end

End;

Procedure PechPo(T: ukaz);

Begin

if T<>Nil then

Begin

PechPo(T^.Left);

PechPo(T^.Right);

WriteLn('Вершина ',T^.Key);

end

End;

Procedure PechIn(T: ukaz);

Begin

if T<>Nil then

Begin

PechIn(T^.Left);

WriteLn('Вершина ', T^.Key);

PechIn(T^.Right);

end

End;

Begin

ClrScr;

New(Root);

Sozd(Root);

WriteLn('Дерево создано !');

ReadLn; { пауза }

PechPr(root);

WriteLn('Печать в порядке сверху вниз ');

ReadLn;

PechPo(Root);

Writeln('Печать в порядке снизу вверх ');

ReadLn;

PechIn(Root);

WriteLn('Печать в порядке слева направо ');

ReadLn

End.

Здесь дерево представлено с помощью указателей. Можно представить дерево и массивом на основе следующих объявлений:

Type

uzel=record

Key: integer;

Left, Right: integer;

{индексы в массиве вершин, -1 –признак листа}

end;

Var

Ver: array[1..100] of uzel; {вершина с индексом 1 – корень дерева}

Kon: integer; {число вершин, а также индекс последней вершины}

Необходимые изменения текста программы можно произвести путем контекстной замены:

· T^ - Ver[T]. ;

· New(Root) – Kon:=1;

· New(Kon) – Kon:=Kon+1;

· T: ukaz - T: integer;

· Root – 1;

· Nil - -1.

Полезно на примере дерева из 5-6 вершин рассмотреть работу одной из рекурсивных процедур (например, PechPr). Удобно в этом случае считать, что при каждом рекурсивном обращении в память загружается новая копия процедуры.