Search trees

Search trees

[VBTricks.de.vu Webmaster]

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

Re: Search trees

[Robert A Duff]

"VBTricks.de.vu Webmaster" <vbtricks@gmx.net> writes:

> 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.

Do you understand how recursion works internally?  
Whenever you call a procedure, the machine code pushes
some information on a stack (return address, local variables).
If you want to avoid recursion, you can simulate this process
by writing explicit stack-management code.

- Bob

Re: Search trees

[VBTricks.de.vu Webmaster]

Hello Bob,

no I do not know how recursion works internally. But I think there must 
be another way. Can you help me?


Thanks in advance,

Stefan

Re: Search trees

[Robert A Duff]

"VBTricks.de.vu Webmaster" <vbtricks@gmx.net> writes:

> no I do not know how recursion works internally. But I think there must
> be another way. Can you help me?

Use a stack to keep track of which tree nodes have not yet been fully
processed.

- Bob

Re: Search trees

[VBTricks.de.vu Webmaster]

Hello Robert,

but how do I implement this? I have very little knowledge of Ada95 (at 
least none of stack programming).


Thanks in advance,

Stefan

Re: Search trees

[Georg Bauhaus]

VBTricks.de.vu Webmaster wrote:
> Hello Robert,
> 
> but how do I implement this? I have very little knowledge of Ada95 (at 
> least none of stack programming).

Not sure what you mean by "stack programming",
but what may be meant here is that you write some helper
subprograms.  Calling them will move nodes onto a "stack" and move them
back when necessary when you simulate recursive Infix. "Stack" here is
something that you program, it doesn't yet exist in the system.

It might help to pay attention to the imaginary steps you take
while executing Infix in your head.
  How do you remember nodes when you follow a call of Infix from
within Infix? How many nodes will you have to remember befor Put is
called for the first time? Why do you have to remember nodes, anyway?
How long will they have to be remembered?

The way a stack package can be written is likely described in
every book about programming in Ada. Which one do you have?


-- Georg

Re: Search trees

[Jeffrey Carter]

VBTricks.de.vu Webmaster wrote:

> 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.

Sounds like homework to me.

One way to avoid recursion is to use a non-recursive searchable 
structure, such as a skip list.

-- 
Jeff Carter
"I would never want to belong to any club that
would have someone like me for a member."
Annie Hall
41

Re: Search trees

[Jeffrey Carter]

Georg Bauhaus wrote:

> Not sure what you mean by "stack programming",
> but what may be meant here is that you write some helper
> subprograms.  Calling them will move nodes onto a "stack" and move them
> back when necessary when you simulate recursive Infix. "Stack" here is
> something that you program, it doesn't yet exist in the system.

Unless he uses one of the fine libraries available for Ada, such as the 
PragmAda Reusable Components (PragmARC.Stack_Unbounded, for example). 
But that's probably not acceptable for homework.

-- 
Jeff Carter
"I would never want to belong to any club that
would have someone like me for a member."
Annie Hall
41

Re: Search trees

[VBTricks.de.vu Webmaster]

Hello again,

well, now I know what a stack is and I programmed my solution using a 
stack. Works perfectly thanks (only problem was to put out the nodes at 
the right position for infix-walkthrough).


But now it works,

Thanks,

Stefan