Tree Traversal

To traverse a non-empty binary tree in preorder, perform the following operations recursively at each node, starting with the root node:

   1. Visit the root.
   2. Traverse the left subtree.
   3. Traverse the right subtree.

(This is also called Depth-first traversal.)



To traverse a non-empty binary tree in inorder, perform the following operations recursively at each node:

   1. Traverse the left subtree.
   2. Visit the root.
   3. Traverse the right subtree.

(This is also called Symmetric traversal.)



To traverse a non-empty binary tree in postorder, perform the following operations recursively at each node:

   1. Traverse the left subtree.
   2. Traverse the right subtree.
   3. Visit the root.



Finally, trees can also be traversed in level-order, where we visit every node on a level before going to a lower level. This is also called Breadth-first traversal.



Example

In this binary search tree,

Preorder traversal sequence: F, B, A, D, C, E, G, I, H (root,left child,right child)
Inorder traversal sequence: A, B, C, D, E, F, G, H, I (leftchild,rootnode,right node)

Note that the inorder traversal of this binary search tree yields an ordered list

Postorder traversal sequence: A, C, E, D, B, H, I, G, F (leftnode,rightnode,rootnode)
Level-order traversal sequence: F, B, G, A, D, I, C, E, H

원문 : http://en.wikipedia.org/wiki/Tree_traversal