**comp.graphics.algorithms**

## Subject: **Re: Tree traversal algorithm**

hi!

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:

current

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"

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

Reply

View All Messages in

**comp.graphics.algorithms**

path:

Tree traversal algorithm =>

Replies:

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.