Xref: utzoo comp.sys.amiga.programmer:1087 comp.theory:1578 alt.flame:28847
Path: utzoo!utgpu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!pacbell.com!tandem!zorch!xanthian
From: xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan)
Newsgroups: comp.sys.amiga.programmer,comp.theory,alt.flame
Subject: Re: tree traversal
Keywords: non-recursive tree traversal algorithm needed
Message-ID: <1991Feb25.074028.992@zorch.SF-Bay.ORG>
Date: 25 Feb 91 07:40:28 GMT
References: <anderson.667437145@mrcnext>
Followup-To: comp.theory
Organization: SF-Bay Public-Access Unix
Lines: 37


 anderson@mrcnext.cso.uiuc.edu writes:

> I need _non-recursive_ pre, post and inorder tree traversal
> algorithms.

After a bit of thinking, at least part of this is possible, which surely
means that with more thinking, all of it should be possible.

> The trees are implemented with leftmost-child, right-sibling and
> parent pointers.

As long as your logic can treat it as if it were a bushy tree, that
should not be a problem.

> Please, no algorithms which use "states" or a stack.

Well, you can't avoid saving _some_ state; you have to know at any node
whether your are going up or down, for example, , but you can avoid
saving O(log(N)) state; you can get by with O(1) state.

I don't have the algorithm to hand you, but here is the basis on which
such a thing can be done: use the equivalent of the maze solver's "right
hand rule" and traverse your (logical) tree as if it were a maze of
narrow hallways. You need merely to know if you are going up or down,
note if you have reached a leaf going down or a node of order >1 going
up that it is time to go the other way, and the third obvioous item of
state is that if you return to the root and there is no next (rightward)
path, then you are done.

By the way, this is a question independent of the Amiga, and this kind
of request is best directed to comp.theory, where it is typical, though
a little low level, of the questions there. Followups to this posting
will go there.

Kent, the man from xanth.
<xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>


Brought to you by Super Global Mega Corp .com