[SOLVED] Tree Traversal. Pre- and Postorder for general trees, inorder only for binary trees?

Tree Traversal. Pre- and Postorder for general trees, inorder only for binary trees?

I read that preorder and postorder traversal were also defined for general (n-ary) trees like that:

preOrder(v)
  if(v==null) return;
  print(v)
  for each child w of v
     preOrder(w)

postOrder(v)
  if(v==null) return;
  for each child w of v
     postOrder(w)
  print(v)

But inorder traversal ist just for binary trees. Why I cant make an inOrder traversal method like the pre and postOrder examples shown above?

Solution

You can of course define a traversal that is an n-ary generalisation of what inorder is for binary trees.

For binary trees inorder means visiting a node after its left child is visited, but before its right child is visited.

For n-ary, you could for instance say a node should be visited after its k leftmost children have been visited, and before any other of its children. k would be a predefined constant, and when k=1, and your tree happens to be binary, then you have the same traversal as the classic inorder traversal.

inOrder(k, v)
  if(v==null) return;
  for each child w among the first k children of v:
      inOrder(k, w)
  print(v)
  for each child w not among the first k children of v:
      inOrder(k, w)

But as you can see, this is a bit of a clumsy traversal, and one could wonder if there is really a practical use for it.