Search trees

["VBTricks.de.vu Webmaster" <vbtricks@gmx.net>]

Hello,

I'm currently working with search-trees, more exactly different methods 
of listings the items in the search-tree (postfix/postorder, 
infix/inorder, prefix/preorder).

Doing this recursively is no problem, but for an exercise I now need to 
implement these functions iteratively (meaning not recursively). The 
only hint I got was to save which children trees I have not walked 
through. But after four days of thinking I still don't get it.

That's my structure for the nodes of the tree:

    type node;
    type tree is access node;
    type node is record
       value : integer;
       left : tree;
       right : tree;
    end record;

and here a sample for a recursive infix-walkthrough:

procedure Infix(t: tree) is
begin
   if t /= null then
     Infix(t.left);
     Put(t.value);
     Infix(t.right);
   end if;
end;

What is the clue? How do I implement it iteratively? Please help me!


Thanks in advance,

Stefan