Tree traversal

There are three types of depth-first traversal: pre-order,in-order, and post-order.

For a binary tree, they are defined as operations recursively at each node, starting with the root node as follows:

Pre-order

Visit the root.
Traverse the left subtree.
Traverse the right subtree.

iterativePreorder(node)
  parentStack = empty stack
  parentStack.push(null)
  top =  node 
  while ( top != null )
      visit( top )
      if ( top.right != null ) 
          parentStack.push(top.right)
      if ( top.left != null ) 
          parentStack.push(top.left)
      top = parentStack.pop()

In-order

Traverse the left subtree.
Visit root.
Traverse the right subtree.

iterativeInorder(node)
  parentStack = empty stack
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null)
      parentStack.push(node)
      node = node.left
    else
      node = parentStack.pop()
      visit(node)
      node = node.right

Post-order

Traverse the left subtree.
Traverse the right subtree.
Visit the root.

iterativePostorder(node)
  parentStack = empty stack  
  lastnodevisited = null 
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null)
      parentStack.push(node)
      node = node.left
    else
      peeknode = parentStack.peek()
      if (peeknode.right ≠ null and lastnodevisited ≠ peeknode.right) 
        /* if right child exists AND traversing node from left child, move right */
        node = peeknode.right
      else
        parentStack.pop() 
        visit(peeknode)
        lastnodevisited = peeknode

Tree traversal,布布扣,bubuko.com

Tree traversal

原文：http://www.cnblogs.com/linyx/p/3627184.html