В действительности нужно сделать следующие действия. Вытолкнуть узел из стека. Если ранее узел не встречался, нужно затолкнуть в стек правый дочерний узел, пометить узел как "встречавшийся", затолкнуть его, а затем затолкнуть в стек левый дочерний узел. Если ранее узел встречался (помните, что он уже помечен?), следует просто его обработать. Но как пометить узел? В конце концов, узел - это указатель, и в действительности не хотелось бы с ним возиться. Я предлагаю следующее решение: после заталкивания в стек "встречавшегося" узла нужно затолкнуть узел nil. В этом случае выталкивание из стека нулевого узла свидетельствует о том, что следующий узел в стеке является тем, который должен быть обработан.
Нерекурсивный алгоритм симметричного обхода работает следующим образом. Затолкните в стек корневой узел и войдите в цикл, который должен выполняться до момента опустошения стека. Вытолкните верхний узел из стека. Если он является нулевым, вытолкните из стека следующий узел и посетите его. Если вытолкнутый узел не является нулевым, затолкните в стек правый дочерний узел (если он является ненулевым), затем сам узел, затем затолкните нулевой указатель и в заключение затолкните в стек левый дочерний узел (если он является ненулевым). Снова выполните цикл.
Как и в случае обхода в ширину, метод предполагает, что дерево является не пустым, и что в нем присутствует, по меньшей мере, один узел. В данном случае это еще более важно, поскольку метод может работать совершенно не правильно, если нулевой узел заталкивается в стек, который не связан с алгоритмом.
Листинг 8.6. Нерекурсивный симметричный обход
function TtdBinaryTree.btNoRecInOrder(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;
{если он является нулевым, вытолкнуть из стека следующий узел и выполнить с ним указанное действие. Если в результате возвращается запрос на прекращение обхода, вернуть этот узел}
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
{затолкнуть правый дочерний узел, если он не нулевой}
if (Node^.btChild[ctRight] <> nil) then
Stack.Push(Node^.btChild[ctRight]);
{затолкнуть узел, а за ним - нулевой указатель}
Stack.Push(Node);
Stack.Push(nil);
{затолкнуть левый дочерний узел, если он не нулевой}
if (Node^.BtChild[ctLeft] <> nil) then
Stack.Push(Node^.btChild[ctLeft]);
end;
end;
finally
{уничтожить стек}
Stack.Free;