Preorder Traversal - Looks at the root value, then the left subtree, then the right subtree.
Reverse Preorder Traversal - Also looks at the root value, then the right subtree, then the left subtree.
Inorder Traversal - Looks at the left subtree, then the root, then the right subtree.
Reverse Inorder Traversal - Looks at the right subtree, then the root, then the left subtree.
Postorder Traversal - Looks at the left subtree, then the right subtree, then the root.
Reverse Postorder Traversal - Looks at the right subtree, then the left subtree, then the root.
Level-by-level Traversal - Looks at all the nodes, level by level, going down one at a time, from left to right.
As can be seen, there are many different ways to traverse Binary Trees. I've added the following example below to look at a Preorder Traversal (taken from EIMACS):
public void printValues(TreeNode tree){
System.out.print( tree.getValue() );
if ( tree.getLeft() != null ){
printValues( tree.getLeft() );
}
if (tree.getRight() != null ){
printValues( tree.getRight() );
}
}
public void printValuesReverse(TreeNode tree){
System.out.print( tree.getValue() );
if (tree.getRight() != null ){
printValuesReverse( tree.getRight() );
System.out.print( tree.getValue() );
if (tree.getRight() != null ){
printValuesReverse( tree.getRight() );
}
if ( tree.getLeft() != null ){
printValuesReverse( tree.getLeft() );
}
printValuesReverse( tree.getLeft() );
}
}
This can be done for all types of binary tree traversals. Although it is a simplistic concept, it outlines important ways of finding your data via binary trees. Each type of traversal has its own advantages and disadvantages, and is left to the developer to figure out which would be the best method to choose.
To keep things easy to remember, you can divide tree traversals into two types:
ReplyDelete1. depth-first
2. breadth-first
The latter is what you listed as "level-by-level". Depth-first searches are subdivided into three types, named for when the root node is visited:
1. pre-order (root, left, right)
2. in-order (left, root, right)
3. post-order (lef, right, root)
Even though it is good to know of them, the reversed ones you added to the list don't add much conceptually, so you don't need to focus on them.
Nice, post, btw. Please continue to use links to Wikipedia and other good sources when you mention a concept that can benefit from further elaboration.