**comp.graphics.algorithms**

## Subject: **Tree traversal algorithm**

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 ;-)

Reply

View All Messages in

**comp.graphics.algorithms**

path:

Replies:

Re: Tree traversal algorithm

Re: Tree traversal algorithm

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.