{уничтожить стек}
Stack.Free;
end;
{внести изменения, отражающие то, что дерево пусто}
FCount := 0;
FHead^.btChild[ctLeft] nil;
end;
Если сравнить этот код с кодом общего метода нерекурсивного обхода, приведенным в листинге 8.7, то несложно заметить, что они во многом совпадают. Единственное реальное различие состоит в том, что в коде отсутствует какая-либо процедура действия - мы уже знаем, что будет делаться с каждым узлом.
Метод Traverse действует всего лишь в качестве контейнера различных внутренних методов обхода, большинство из которых мы уже рассмотрели. Остальные методы представляют собой соответствующие рекурсивные методы обхода дерева.
Листинг 8.12. Обход в классе бинарного дерева
function TtdBinaryTree.btRecInOrder(aNode : PtdBinTreeNode;
aAction : TtdVisitProc; aExtraData : pointer): PtdBinTreeNode;
var
StopNow : boolean;
begin
Result := nil;
if (aNode^.btChild[ctLeft] <> nil) then begin
Result := btRecInOrder(aNode^.btChild[ctLeft],
aAction, aExtraData);
if (Result <> nil) then
Exit;
end;
StopNow := false;
aAction(aNode^.btData, aExtraData, StopNow);
if StopNow then begin
Result := aNode;
Exit;
end;
if < aNode^.btChild[ ctRight ] <> nil) then begin
Result := btRecInOrder(aNode^.btChild[ctRight], aAction, aExtraData);
end;
end;
function TtdBinaryTree.btRecPostOrder(aNode : PtdBinTreeNode;
aAction : TtdVisitProc; aExtraData : pointer): PtdBinTreeNode;
var
StopNow : boolean;
begin
Result := nil;
if (aNode^.btChild[ctLeft] <> nil) then begin
Result :=btRecPostOrder(aNode^.btChild[ctLeft], aAction, aExtraData);
if (Result <> nil) then
Exit;
end;
if (aNode^.btChild[ctRight] <> nil) then begin
Result := btRecPostOrder(aNode^.btChild[ctRight],
aAction, aExtraData);
if (Result <> nil) then
Exit;
end;
StopNow := false;
aAction(aNode^.btData, aExtraData, StopNow);
if StopNow then
Result :=aNode;
end;
function TtdBinaryTree.btRecPreOrder(aNode : PtdBinTreeNode;
aAction : TtdVisitProc; aExtraData : pointer): PtdBinTreeNode;
var
StopNow : boolean;
begin
Result := nil;
StopNow := false;
aAction(aNode^.btData, aExtraData, StopNow);
if StopNow then begin
Result :=aNode;
Exit;
end;
if (aNode^.btChild[ctLeft] <> nil) then begin
Result := btRecPreOrder(aNode^.btChild[ctLeft], aAction, aExtraData);
if (Result <> nil) then
Exit;
end;
if (aNode^.btChild[ctRight]<> nil) then begin
Result := btRecPreOrder(aNode^.btChild[ctRight], aAction, aExtraData);
end;
end;
function TtdBinaryTree.Traverse(aMode : TtdTraversalMode;
aAction : TtdVisitProc;
aExtraData : pointer;
aUseRecursion : boolean): PtdBinTreeNode;
var
RootNode : PtdBinTreeNode;
begin
Result := nil;
RootNode := FHead^.btChild[ctLeft];
if (RootNode <> nil) then begin
case aMode of
tmPreOrder :
if aUseRecursion then
Result := btRecPreOrder(RootNode, aAction, aExtraData) else
Result := btNoRecPreOrder(aAction, aExtraData);
