Hi,

I would like to add enumerator support for my TTreap implementation ( https://github.com/xrfang/fpcollection/blob/master/src/units/treap.pas).

The tree nodes are defined as:

      PNode = ^TNode;
      TNode = record
        Count: Cardinal;
        Key: TKey;
        Value: TValue;
        Priority: Cardinal;
        Left, Right: PNode;
      end;

Now I don't know how to write an enumerator for it. I would like to traverse the tree "In-Order", either from the left-most node or from the right-most node, so that I can output nodes like:

      for n in MyTreap do WriteLn(n^.Key);

Thanks.

See here:

http://wiki.freepascal.org/for-in_loop#Declaring_enumerators

Mattias

Xiangrong Fang wrote

Now I don't know how to write an enumerator for it. ...

Syntax or algorithm ?

-Michael

I have read this. My question is not about how to write enumerator, but how to do this for TREEs

Thanks

发送自魅族MX

-------- 原始邮件 --------
发件人：Mattias Gaertner
时间：3月21日 15:39 周四

主题：Re: [fpc-pascal] How To write an enumerator for trees

I have read this. My question is not about how to write enumerator, but how to do this for TREEs

Xiangrong Fang: Please anser to a message instead of creating a new thread !

There might be no necessary sort order of a tree.

So you first need to invent a usable sort order and set up the enumerator accordingly. An Enumerator can work on any sort order it only needs to be strict. Regarding performance it is essential to use a sort order that allows for quickly finding the elements one after the other.

-Michael

Xiangrong Fang 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

I am not creating a new thread, but just replied it. My question is about algorithm not syntax. I will try the sample program by Kyan.

Thanks.

2013/3/21 Michael Schnell

Xiangrong Fang wrote

I am not creating a new thread, but just replied it.

your post did not contain a references control line pointing to the post you were replying to... that breaks the linking and it won't be placed in the tree...

my 2 centavos...

kyan wrote

HTH Constantine

Are you the man who created Kyan Pascal? I used that many years ago.

S. Fisher wrote

--- On Thu, 3/21/13, kyan wrote: Are you the man who created Kyan Pascal? I used that many years ago.

I'd never heard of it till now.

I wish. I'm nowhere nearly that good. :)