[Texas PLT logo]

COMP 202: Principles of Object-Oriented Programming II

  Tree Traversal Algorithms  

Mutable Binary Tree Framework

The Mutable Binary Tree Framework stores data in a hierarchical fashion, where mutation is allowed:

 

Tree Traversals

When we process a list, we basically have two ways to traverse it and move data along: forward (as in forward accumulation) or reverse (as in reverse accumulation).  In contrast, due to its non-linear structure, a binary tree can be traversed in many more different ways.  However, we can categorize data movement in two "directions": top-down and bottom-up.  In this lecture, we will study four tree traversal algorithms that are most common in tree processing.

  1. In order traversal
  2. Pre order traversal
  3. Post order traversal
  4. Breadth-first traversal

For the sake of definiteness, we consider the following trees as examples throughout:

mtTree: an empty tree

biTree: the non-empty tree

               1
            /     \
         2         3
      /    \          \
    4      5           6
                       /
                    7

 

In Order Traversal

Here is what it means to process a tree by traversing it in in order.

Here is a concrete example of an in-order traversal of the above biTree.

In class Exercise 1:

Write a visitor that prints the contents of a binary in in-order traversal.  What should the output be for the above biTree?

As you can see, there is so much similarity between the code for exercise 1 and InOrderAdd.  The question is whether or not we can separate the variants from the invariant and capture the abstraction of in-order traversal as the invariant.

Clearly, tree traversal is a visitor. What does it mean to "process the root"?  How can we enforce the order of processing?

Processing the root and each of the subtrees: use an abstract function ILambda; the concrete ILambdas are the variants.

Enforcing the order of processing: use the order in which the arguments of of a function are evaluated; this is the invariant.

So here is the invariant code for  in-order tree traversal.

Post Order Traversal

Here is what it means to process a tree by traversing it in in order.

In class exercise 2:

Write an invariant post order traversal visitor analogous to the above in order traversal visitor.

 

Pre Order Traversal

Here is what it means to process a tree by traversing it in in order.

In class exercise 2:

Write an invariant pre order traversal visitor analogous to the above in order traversal visitor.

 

  Tree Traversal Algorithms  

URL: http://www.clear.rice.edu/comp202/08-fall/lectures/tree/index.shtml
Copyright © 2008-2010 Mathias Ricken and Stephen Wong