- I devised an algorithm for traversing a tree, which does not need to

maintain a stack. Is the algorithm a familiar one? If not, does it

have any flaw?

The algorithm is as follows.

1. Initially:

Node <- pointer to tree's root node

Direction <- downward

2. Visit Node.

If Direction==downward, go to 3.

Otherwise, go to 4.

3. If Node has children,

Node <- Node.OldestChild(), go to 2.

Otherwise, if Node has a younger sibling,

Node <- Node.NextSibling(), go to 2.

Otherwise,

Direction <- upward, go to 4.

4. If Node==pointer to tree's root node, terminate.

Otherwise, Node <- Node.Parent().

If Node has a younger sibling,

Node <- Node.NextSibling(), Direction <- downward, go to 2.

Otherwise, go to 4.

The above algorithm implements depth-first, prefix order of visiting the

tree's nodes.

It may be possible to modify the algorithm to implement infix order or

postfix order by moving the Visit Node statement to other places in the

algorithm, but I did not investigate it.

To implement a breadth-first tree traversal algorithm (i.e. all nodes at

level N are visited before visiting a node at level N+1), it may be

sufficient to maintain a counter remembering the current level and

determine for each visited node which level it belongs to - so only

nodes at the current level are actually manipulated.

--- Omer

--

Every good master plan involves building a time machine. Moshe Zadka

My own blog is at http://www.livejournal.com/users/tddpirate/

My opinions, as expressed in this E-mail message, are mine alone.

They do not represent the official policy of any organization with which

I may be affiliated in any way.

WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html - On Fri, 2005-08-26 at 02:13 +0300, guy keren wrote:

> aha, but you are forgetting that you do not have an upper-bound on the

How about that what-is-its-name transformation, which establishes an

> number of children for a given node. consider this:

>

>

> [ P ]

>

>

> [C1] [C2] [C3] [C4] [C5] [C6] [C7] [C8] [C9] [C10] [C11]

>

>

> lets say we were in C2, and are now returning to P. we now need to find

> which is the next node we should visit. the only way to make this in O(1),

> is that each node will keep a link to its sibling. add these links too,

> then. (if this operation is not O(1), it makes your scanning algorithm

> less efficient then O(N)).

equivalence relationship between general and binary trees?

Then you need to deal only with two children per node.

> if you'll want to scan the tree in reverse order, you'll need the siblings

OK, I give up.

> list to be bidirectional.

>

> if you'll want to make a BFS scan, rather then DFS.....

>

> so, you see, you're creating a tree that lends itself to one manner of

> traversal, and does not work for other types of traversals.

>

> this could be useful for specific types of problems, ofcourse, but this is

> not the generic issue of traversing a tree structure.

I propose a bicycle as a transportation vehicle, pointing out that it is

the best solution for some specialized transportation situations.

You reply by reminding us that most of the transportation needs of

humans are better served by cars and airplanes.

> if you can't bring up something useful - it's better to keep the list

Sounds cool and interesting. Can you tell us more about it?

> quiet. would you like me to bring up my mission-imposible project of

> devising an algorithm that automatically translates C programs into C++

> programs while introducing classes based on usage relations between data

> and functions in the original C program?

How do you avoid the trivial solution of enclosing function declarations

by extern "C" { ... } declarations?

--- Omer

--

Every good master plan involves building a time machine. Moshe Zadka

My own blog is at http://www.livejournal.com/users/tddpirate/

My opinions, as expressed in this E-mail message, are mine alone.

They do not represent the official policy of any organization with which

I may be affiliated in any way.

WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html