The C++Course provides a general introduction to programming in C++. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.

Home Trees Traversal
 
del.icio.us Reddit Facebook StumbleUpon MySpace Twitter

Traversal

I already pointed out that recursion provides a natural way to traverse a tree. We can print the contents of an expression tree like this:

    public static void print (Tree tree) {
        if (tree == null) return;
        System.out.print (tree + " ");
        print (tree.left);
        print (tree.right);
    }

In other words, to print a tree, first print the contents of the root, then print the entire left subtree, then print the entire right subtree. This way of traversing a tree is called a preorder, because the contents of the root appear before the contents of the children.

For the example expression the output is + 1 * 2 3. This is different from both postfix and infix; it is a new notation called prefix, in which the operators appear before their operands.

You might suspect that if we traverse the tree in a different order we get the expression in a different notation. For example, if we print the subtrees first, and then the root node:

    public static void printPostorder (Tree tree) {
        if (tree == null) return;
        printPostorder (tree.left);
        printPostorder (tree.right);
        System.out.print (tree + " ");
    }

We get the expression in postfix (1 2 3 * +)! As the name of the previous method implies, this order of traversal is called postorder. Finally, to traverse a tree inorder, we print the left tree, then the root, then the right tree:

    public static void printInorder (Tree tree) {
        if (tree == null) return;
        printInorder (tree.left);
        System.out.print (tree + " ");
        printInorder (tree.right);
    }

The result is 1 + 2 * 3, which is the expression in infix.

To be fair, I have to point out that I have omitted an important complication. Sometimes when we write an expression in infix we have to use parentheses to preserve the order of operations. So an inorder traversal is not quite sufficient to generate an infix expression.

Nevertheless, with a few improvements, the expression tree and the three recursive traversals provide a general way to translate expressions from one format to another.
Home Trees Traversal

Last Update: 2005-12-05