Home Products Download Order Contacts


Subject: Re: Tree traversal algorithm


imho i guess it would have been better if you had 1->2, 1->3 and 1->4
pointers. then you could write some simple algorithm, using stack ...

for you tree, it'd go like this:

node action stack
1 push 1 [] .. 1 has some unvisited children, let's visit them
2 ------ [1] .. 2 has no children at all. we'll take a peek into
stack to see who's the parent and if he has any next chidren. he has 3 so we
proceed to 3
3 ------ [1] .. the same as for 2
4 pop [1] .. no more children found, go up
1 ------ [] .. there are no more parents for 1, so this is the end

"Soeren Meyer-Eppler" píse v diskusním
príspevku news:e42ipd$ocp$1@news01.versatel.de...
> Hello,
> I have a tree structure I want to traverse in in-order (left leaf, node,
> right leaf) sequence. This is pretty easy if you have a binary tree and
> child pointers you can follow. Unfortunately I have a tree with n childs
> and only parent pointers. My definition of in-order for n-childs would
> be leaf,node,leaf,node,leaf,... order. So far I couldn't think of an
> algorithm that'd solve my problem.
> The only idea I could think of was to convert the tree to a binary child
> pointer structure type tree (wasn't there a proof that you can convert
> basically any tree into a binary tree?) and implement basic in-order
> traversal on that. But I don't know how to do this efficiently - or
> rather, at all. If this was the only way to go that'd be depressing,
> since this has to be done at run time, often, and for a lot of trees.
> Here is a little example tree:
> 1
> /|
> 234
> I want to traverse that in 2-1-3-1-4 order. I only have the three
> pointers 2->1, 3->1, 4->1.
> Does anyone have any ideas or hints?
> regards,
> Sören
> Sorry if this is not strictly a graphics algorithm question, but this
> was the most appropriate group I found - and trees are pretty useful for
> graphics too right ;-)


View All Messages in comp.graphics.algorithms

Tree traversal algorithm =>


Copyright © 2006 WatermarkFactory.com. All Rights Reserved.