[fpc-pascal] How To write an enumerator for trees

[kyan]

On Thu, Mar 21, 2013 at 10:32 AM, Xiangrong Fang <xrfang at 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