tree traversal

摘自维基百科


preorder(node)
if (node == null) return
visit(node)
preorder(node.left)
preorder(node.right)




iterativePreorder(node)
if (node == null) return
s <-- empty stack
s.push(node)
while (not s.isEmpty())
node <-- s.pop()
visit(node)
// right child is pushed first so that left is processed first
if (node.right != null) s.push(node.right)
if (node.left != null) s.push(node.left)


inorder(node)
if (node == null) return
inorder(node.left)
visit(node)
inorder(node.right)


iterativeInorder(node)
s <-- empty stack
while (not s.isEmpty() or node != null)
if (node != null)
s.push(node)
node <-- node.left
else
node <-- s.pop()
visit(node)
node <-- node.right




postorder(node)
if (node == null) return
postorder(node.left)
postorder(node.right)
visit(node)


iterativePostorder(node)
s <-- empty stack
lastNodeVisited <-- null
while (not s.isEmpty or node != null)
if (node != null)
s.push(node)
node <-- node.left
else
peekNode <-- s.peek()
// if right child exists and traversing node
// from left child, then move right
if (peekNode.right != null and lastNodeVisited != peekNode.right)
node <-- peekNode.right
else
visit(peekNode)
lastNodeVisited <-- s.pop()