Wikipedia states that the following algorithm works for any tree (not necessarily binary trees)
- Perform pre-order operation
- For each i (with i = 1 to n) do:
- Visit i-th, if present
- Perform in-order operation
- 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?