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 ------  .. 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 ------  .. the same as for 2
4 pop  .. no more children found, go up
1 ------  .. there are no more parents for 1, so this is the end
> 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
Tree traversal algorithm =>
Copyright © 2006 WatermarkFactory.com. All Rights Reserved.