Home Products Download Order Contacts


Subject: Re: Tree traversal algorithm

Soeren Meyer-Eppler wrote:

> 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.

Wow. That must be the single most unhelpful way of storing a tree,
ever. That almost makes bogo-sort look like a good idea in comparison
;-) The first order of business should arguably be to tar and feather
whoever came up with that input data structure design, or at least get
him to pay for your work fixing up his mistakes.

> But I don't know how to do this efficiently -

Forget about efficiency. That's the least of your worries here.

That said, it's pretty straight forward: sort your N parent-child
pairs by parent. This will give you all child nodes of each parent
nicely arranged next to each other. Keep that sorted table, and store
the start and length of that sequence with each node. Done.

Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.


View All Messages in comp.graphics.algorithms

Tree traversal algorithm =>

Re: Tree traversal algorithm

Copyright 2006 WatermarkFactory.com. All Rights Reserved.