views:

98

answers:

3

Hi,

We are dealing with a Most similar neigthbour algorithm here. Part of the algorithm involves searching in order over a tree.

The thing is that until now, we cant make that tree to be binary.

Is there an analog to in order traversal for non binary trees. Particularly, I think there is, just traversing the nodes from left to right (and processing the parent node only once?")

Any thoughts?

update

This tree will have in each node a small graph of n objects. Each node will have n children (1 per each element in the graph), each of which will be another graph. So its "kind of" a b tree, without all the overflow - underflow mechanics. So I guess the most similar in order traversal would be similar to a btree inorder traversal ?

Thanks in advance.

+5  A: 

Yes, but you need to define what the order is. Post and Pre order are identical, but inorder takes a definition of how the branches compare with the nodes.

deinst
Good point. "left" and "right" sub-trees (and the nodes in-between) could have a generalization, but it is probably better to explicitly list the requirements in a case like this.
Noah Watkins
+3  A: 

In-order traversal only makes sense for binary trees. However, the SO community could certainly help find the correct analog to in-order traversal given more details on what you want to accomplish, and why in-order traversal stuck out as appropriate.

Noah Watkins
Not true: In-Order traversal makes perfect sense for BTrees, too.
Nick Johnson
It's a matter of how you define it.
Noah Watkins
A: 

There is no simple analog of the in-order sequence for trees other than binary trees (actually in-order is a way to get sorted elements from a binary search tree).

You can find more detail in "The art of computer programming" by Knuth, vol. 1, page 336.

If breadth-first search can serve your purpose then you can use that.

Atul