On Thu, Mar 21, 2013 at 10:32 AM, Xiangrong Fang <xrf...@gmail.com> wrote:
> I have read this. My question is not about how to write enumerator, but how
> to do this for TREEs
Usually linearizing recursion is done with a stack. Here's a sample
implementation that will give you an in-order tree traversal (Left -
Parent - Right), that for a binary search tree will produce a sorted
enumeration:
constructor TTreeEnumerator.Create(ATree: TTree);
begin
FStack := TStack.Create;
FStack.Push(FTree.FRoot);
end;
function TTreeEnumerator.DoMoveNext: Boolean;
var
Node: PNode;
begin
if FStack.Empty then
Exit(False);
while not FStack.Empty do
begin
Node := FStack.Pop;
if not Assigned(Node) then
begin
FCurrent := FStack.Pop;
Exit(True);
end
else
begin
if Assigned(Node.Right) then
FStack.Push(Node.Right);
FStack.Push(Node);
FStack.Push(nil);
if (Node.Left <> nil) then
FStack.Push(Node.Left);
end;
end;
end;
To reverse the sorting just swap Left and Right in the code of DoMoveNext.
HTH
Constantine
_______________________________________________
fpc-pascal maillist - fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
