Home Products Download Order Contacts


Subject: Tree traversal algorithm


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:


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?



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


Re: Tree traversal algorithm
Re: Tree traversal algorithm

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.