New(p);

End;

Таким образом, дерево на рисунке 4 б) можно представить так, как на
рисунке 5.

Далее будем иметь дело только с двоичными деревьями, поэтому термин “дерево” будет означать двоичное дерево.

3. ОСНОВНЫЕ ОПЕРАЦИИ С ДВОИЧНЫМИ ДЕРЕВЬЯМИ

3.1. Обход дерева

Наиболее распространенная задача обработки древовидных структур – выполнение некоторой определенной операции над каждым элементом дерева. При этом происходит “посещение” всех вершин, т.е. обход дерева. При обходе каждый узел проходится, по меньшей мере, один раз, а, вообще говоря, три раза. Полное прохождение дерева дает линейную расстановку узлов. Если, обходя дерево, обрабатывать вершины при первой встрече, то (см. рис. 4 б)) получим последовательность A, B, D, E, C, F; если при второй встрече, то получим D, B, E, A, C, F; если при третьей встрече, то получим D, E, B, F, C, A.

Эти три способа обхода называются соответственно

– обходом сверху вниз (в прямом порядке, префиксным обходом, preorder);

– обходом слева направо (в обратном порядке, инфиксным обходом,
inorder);

– обходом снизу вверх (в концевом порядке, постфиксным обходом,
postorder или endorder).

Способы прохождения деревьев определяются рекурсивно. Если дерево пусто, то никаких действий не выполняется, в противном случае обход выполняется в три этапа

Префиксный обход	Инфиксный обход
Обработать узел	Пройти левое поддерево
Пройти левое поддерево	Обработать узел
Пройти правое поддерево	Пройти правое поддерево

Постфиксный обход

Пройти левое поддерево

Пройти правое поддерево

Обработать узел

Обход слева направо (инфиксный обход) часто используется при сортировке (см. раздел 4). Префиксный и постфиксный способы обхода дерева играют важную роль при анализе текстов на языках программирования.

Все три метода легко представляются как рекурсивные процедуры.

Пример 3.1. Префиксный обход дерева:

procedure PreOrder(T: Tree);

Begin

if T <> nil then

Begin

{ операция обработки узла дерева, например, writeln(T^.inf);}

PreOrder (T^.L);

PreOrder (T^.R)

End

end; { PreOrder }

Пример 3.2. Инфиксный обход дерева:

procedure InOrder(T: Tree);

Begin

if T <> nil then

Begin

InOrder (T^.L);

{ операция обработки узла дерева, например, writeln(T^.inf);}

InOrder (T^.R)

End

end; { InOrder }

Пример 3.3. Постфиксный обход дерева:

procedure PostOrder(T: Tree);

Begin

if T <> nil then

Begin

PostOrder (T^.L);

PostOrder (T^.R)

{ операция обработки узла дерева, например, writeln(T^.inf);}

End

end; { PostOrder }

Замечание. Ссылка T передается как параметр - значение, т.е. в процедуре используется ее локальная копия.

При реализации нерекурсивных процедур обхода дерева обычно используют вспомогательный стек и операции работы с ним:

– очистить стек (создать пустой стек);

– проверить, является ли стек пустым;

– добавить в стек элемент;

– извлечь элемент из стека.

В стеке запоминаются ссылки на вершины (поддеревья), обработка которых временно откладывается.

Пример 3.4. Описать нерекурсивную процедуру префиксного обхода
дерева.

Описание вспомогательного стека:

type Stack = ^Rec;

Rec = record

inf_S: Tree;

next: Stack

End;

Процедура добавления в стек start элемента T:

procedure Push (var start:Stack; T: Tree);

var p:Stack;

Begin

new(p);

p^.inf_S:=T;

p^.next:=start;

start:=p

End;

Процедура извлечения из стека start элемента T:

procedure Pop (var start:Stack; var T: Tree);

var p:Stack;

Begin

p:=start;

T:=start^.inf_S;

start:=start^.next;