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

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

function TtdBinaryTree.btNoRecPostOrder(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;

{если он является нулевым, вытолкнуть из стека следующий узел и выполнить с ним указанное действие. Если в результате возвращается значение false (т.е. обход должен быть прекращен), вернуть этот узел}

if (Node = nil) then begin

Node := Stack.Pop;

aAction(Node^.btData, aExtraData, StopNow);

if StopNow then begin

Result := Node;

Stack.Clear;

end;

end

{в противном случае дочерние узлы этого узла в стек еще не заталкивались}

else begin

{затолкнуть узел, а за ним - нулевой указатель}

Stack.Push(Node);

Stack.Push(nil);

{затолкнуть правый дочерний узел, если он не нулевой}

if (Node^.btChild[ctRight] <> nil) then

Stack.Push(Node^.btChild[ctRight]);

{затолкнуть левый дочерний узел, если он не нулевой}

if (Node^.btChild[ctLeft] <> nil) then

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

end;

end;

finally

{уничтожить стек}

Stack.Free;

end;

end;

Как и ранее, по тем же причинам, метод предполагает, что дерево является не пустым.

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

Листинг 8.8. Обход по уровням

function TtdBinaryTree.btLevelOrder(aAction : TtdVisitProc;

aExtraData : pointer): PtdBinTreeNode;

var

Queue : TtdQueue;

Node : PtdBinTreeNode;

StopNow : boolean;

begin

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

Result := nil;

StopNow := false;

{создать очередь}

Queue := TtdQueue.Create(nil);

try

{поместить корневой узел в очередь}

Queue.Enqueue(FHead^.btChild[ctLeft]);

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

while not Queue.IsEmpty do

begin

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

Node := Queue.Dequeue;

{выполнить действия с ним. Если в результате возвращается запрос на прекращение обхода, вернуть этот узел}

aAction(Node^.btData, aExtraData, StopNow);

if StopNow then begin

Result :=Node;

Queue.Clear;

end

{в противном случае продолжить процесс}

else begin

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

if (Node^.btChild[ctLeft]<> nil) then

Queue.Enqueue(Node^.btChild[ctLeft]);

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

if (Node^.btChild[ctRight] <> nil) then

Queue.Enqueue(Node^.btChild[ctRight]);

end;

end;

finally

{уничтожить очередь}

Queue.Free;

end;

end;

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

Как и в случае остальных уже рассмотренных структур данных, мы реализуем стандартное бинарное дерево в виде класса. Действительно, мы уже положили начало такому подходу, рассмотрев различные методы готового класса.

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

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