Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

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

В отличие от связных списков, где перемещение по структуре определено однозначно (достаточно следовать всем указателям Next (следующий), пока не будет достигнут конец списка), в бинарном дереве в каждом узле можно выбрать один из двух путей, и поэтому процесс несколько усложняется. Процедуру перемещения по дереву называют обходом (traversal). Существуют четыре основных алгоритма обхода - обходом в ширину (pre-order), симметричным обходом (in-order), обходом в глубину (post-order) и обходом по уровням (level-order). Последний алгоритм - обход по уровням - наиболее прост для визуального представления, но наиболее сложен для кодирования. Этот алгоритм предполагает посещение каждого из узлов, начиная с корневого, и просмотр узлов сверху вниз, уровень за уровнем. На каждом уровне мы посещаем узлы слева направо. Таким образом, мы посещаем корневой узел, левый дочерний узел корневого узла, правый дочерний узел корневого узла, левый дочерний узел левого дочернего узла корневого узла, правый дочерний узел левого дочернего узла корневого узла и т.д. Снова обратившись к рисунку 8.1, мы видим, что при обходе по уровням посещение узлов выполнялось бы в следующем порядке: d, b, f, а, с, е, g.

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

При обходе в ширину вначале мы посещаем корневой узел, затем, используя алгоритм обхода в ширину, выполняем обход левого дочернего дерева, а затем таким же образом выполняем обход правого дочернего дерева. (Обход дерева, изображенного на рис. 8.1, выполнялся бы в следующем порядке: d, b, а, с, /, е, g.) При симметричном обходе вначале выполняется обход левого дочернего дерева корневого узла с применением алгоритма симметричного обхода, а затем симметричный обход правого дочернего дерева. (В дереве, показанном на рис. 8.1, посещение узлов выполнялось бы в следующем порядке: а, b, с, d, е, /, g.) При обходе в глубину вначале выполняется обход в левого дочернего дерева с применением алгоритма обхода в глубину, затем таким же образом выполняется обход правого дочернего дерева, а затем посещается корневой узел. (В дереве, изображенном на рис. 8.1, посещение узлов выполнялось бы в следующем порядке: а, с, b, е, g, f, d.)

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

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

Листинг 8.4. Обход в ширину, симметричный обход и обход в глубину

type

TtdProcessNode = procedure(aNode : PtdBinaryNode);

procedure PreOrderTraverse(aRoot : PtdBinaryNode;

aProcessNode : TtdProcessNode);

begin

if (aNode <> nil) then begin

aProcessNode(aRoot);

PreOrderTraverse(aRoot^.bnChild[ciLeft], aProcessNode);

PreOrderTraverse(aRoot^.bnChild[ciRight], aProcessNode);

end;

end;

procedure InOrderTraverse(aRoot : PtdBinaryNode;

aProcessNode : TtdProcessNode);

begin

if (aNode <> nil) then begin

InOrderTraverse(aRoot^.bnChild[ciLeft], aProcessNode);

aProcessNode(aRoot);

InOrderTraverse(aRoot^.bnChild[ciRight], aProcessNode);

end;

end;

procedure PostOrderTraverse(aRoot : PtdBinaryNode;

aProcessNode : TtdProcessNode);

begin

if (aNode <> nil) then begin

PostOrderTraverse(aRoot^.bnChild[ciLeft], aProcessNode);

PostOrderTraverse(aRoot^.bnChild[ciRight], aProcessNode);

aProcessNode(aRoot);

end;

end;

Обратите внимание на то, как каждая рекурсивная процедура проверяет, не является ли переданный ей узел нулевым. В этом случае она не выполняет никаких действий, немедленно осуществляя выход. Следовательно, со временем рекурсивный вызов процедур завершится (поскольку дерево простирается не до бесконечности).

Однако в каждом случае применения рекурсивной процедуры следует оценить, сколько раз она должна будет выполняться в ходе последовательности рекурсивных вызовов. Дело в том, что рекурсивные процедуры хранят свое состояние в стеке программы, размер которого в общем случае ограничен. Если выясняется, что рекурсивная процедура может иметь слишком много уровней, следует подумать над тем, как избавиться от рекурсии за счет применения внешнего стека. Используя внешний стек вместо стека программы, можно быть уверенным, что при необходимости размер стека в куче можно будет увеличить (пока выделенный объем кучи не будет исчерпан, однако, в общем случае этот объем значительно превышает размер стека программы).

Мы используем стек, созданный на основе связного списка класса TtdStack, который был описан в главе 3. Для выполнения обхода в ширину мы заталкиваем в стек корневой узел и выполняем цикл, который продолжается до тех пор, пока стек не опустеет. Мы выталкиваем из стека верхний узел и посещаем его. Если правая дочерняя связь этого узла является ненулевой, мы заталкиваем ее в стек. Затем заталкиваем в стек левую дочернюю связь узла, если она является ненулевой. (Заталкивание дочерних узлов в указанном порядке означает, что вначале из стека выталкивается левый дочерний узел.) Если стек не является пустым, цикл повторяется. Обход завершается немедленно после опустошения стека.

Листинг 8.5. Нерекурсивный обход в ширину

type

TtdVisitProc = procedure ( aData : pointer;

aExtraData : pointer;

var aStopVisits : boolean );

function TtdBinaryTree.btNoRecPreOrder(aAction : TtdVisitProc;

aExtraData : pointer): PtdBinTreeNode;

var

Stack : TtdStack;

Node : PtdBinTreeNode;

StopNow : boolean;

begin

{предположим, что мы не добрались до выбранного узла}

Result := nil;

StopNow := false;

{создать стек}

Stack := TtdStack.Create(nil);

try

{затолкнуть корневой узел}

Stack.Push(FHead^.btChild[ctLeft]);

{продолжать процесс до тех пор, пока стек не будет пуст}

while not Stack.IsEmpty do

begin

{извлечь узел в начале очереди}

Node := Stack.Pop;

{выполнить с ним указанное действие; если в результате возвращаемое значение переменной StopNow равно true, вернуть этот узел}