4

Wikipedia states that the following algorithm works for any tree (not necessarily binary trees)

  1. Perform pre-order operation
  2. For each i (with i = 1 to n) do:
    1. Visit i-th, if present
    2. Perform in-order operation
  3. Perform post-order operation

where n is the number of child nodes.

The pre-order and post-order parts make sense. The in-order one does not make sense to me however. By performing this algorithm I would perform the in-order operation on the same node several times. Basically, if I have a node with 5 child nodes, then I will perform the in-order operation on the node 5 times, once after visiting each child node. This does not make sense to me. Isn't a tree traversal supposed to go through each node once?

Actually, does an in-order traversal even make sense for generic trees? Doesn't it only apply to binary trees, or trees where the "order" is not ambiguous?

9a3eedi
  • 2,101
  • 3
  • 23
  • 29
  • Why would a binary node be any more likely to have a well-defined order between its children? Nodes of *any* arity can have either ordered lists or simple sets of children. – Kilian Foth Mar 19 '15 at 07:47
  • You're right. I only considered trees that are ordered because they have a fixed number of children, and hadn't considered other ways of ordering children, like alphabetical for example. So an in-order traversal makes sense now. However, performing an operation on the same node several times still doesn't. – 9a3eedi Mar 19 '15 at 08:13

1 Answers1

1

In the algorithm you provided, although it is true that the same in-order operation is performed in the same node multiple times, it is still ran once for each node and each node is visited only once.

Note that this isn't a "in-order" tree traversal, you can't make such a traversal on a ntree, it just doesn't make sense. This is simply a deep-first traversal and the in-order operation is something that is ran after the node has been visited. It has nothing to do with the "in-order functions" that are mentioned elsewhere in on the page.

Maybe I should add, visit is the recursive call in this case, not the in-order operation.

wfdctrl
  • 106
  • 5