end;
Нерекурсивный алгоритм обхода в глубину работает аналогично. Необходимо затолкнуть в стек корневой узел и войти в цикл, который будет выполняться до момента опустошения стека. В цикле необходимо вытолкнуть из стека верхний узел. Если он является нулевым, нужно вытолкнуть из стека следующий узел и выполнить его обработку. Если узел не является нулевым, следует затолкнуть в стек сам узел, затем нулевой указатель, затем правый дочерний узел (если он является ненулевым), а затем левый дочерний узел (если он является ненулевым). Затем необходимо снова выполнить цикл.
Листинг 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;