16.2. Binary Tree Traversals¶
Often we wish to process a binary tree by “visiting” each of its nodes, each time performing a specific action such as printing the contents of the node. Any process for visiting all of the nodes in some order is called a traversal. Any traversal that lists every node in the tree exactly once is called an enumeration of the tree’s nodes. Some applications do not require that the nodes be visited in any particular order as long as each node is visited precisely once. For other applications, nodes must be visited in an order that preserves some relationship.
In the following examples, we will be calling the visit() method
on each node. The definition below simply prints the value of the node, but other actions can be performed:
public void visit(BinaryTreeNode<T> node) {
System.out.print(node.getValue() + " ");
}
Note
In lecture, our “visit” action was simply a System.out.println() of the current node’s value.
16.2.1. Preorder Traversal¶
For example, we might wish to make sure that we visit any given node before we visit its children. This is called a preorder traversal.
Figure 16.2.1: A binary tree for traversal examples.
16.2.2. Postorder Traversal¶
Alternatively, we might wish to visit each node only after we visit its children (and their subtrees). For example, this would be necessary if we wish to return all nodes in the tree to free memory. We would like to delete the children of a node before deleting the node itself. But to do that requires that the children’s children be deleted first, and so on. This is called a postorder traversal.
16.2.3. Inorder Traversal¶
An inorder traversal first visits the left child (including its entire subtree), then visits the node, and finally visits the right child (including its entire subtree). The binary search tree makes use of this traversal to print all nodes in ascending order of value.