Comp201: Principles of Object-Oriented Programming I
Spring 2006 -- Lab13: Binary Tree Processing - Exercises on BiTree   

The purpose of this lab is to provide more practice on manipulating the mutable binary structure BiTRee.  It is always helpful to draw a few pictures to visualize what the tree should look like and how it should be manipulated.  Use anonymous inner classes whenever you need helpers.

Note: This lab is also a homework assignment.

Exercise #0 (Warm up!): Count the number of elements in a binary tree

1. We saw in the lecture an example of a BiTree visitor that counts the number of elements in a binary tree.  Rewrite this visitor here.

2. Write an appropriate JUnit test class.

Exercise #1: Add the elements in a binary tree

1. First, write an appropriate JUnit test class for  a BiTree visitor called AddAll that adds all the elements in a binary tree, assuming the host tree contains Integer objects.

2. Now, write the code for AddAll.

Exercise #2: Compute the height of a binary tree.

Here is a recursive definition of the height of a binary tree.

• The height of an empty binary tree is 0.

• The height of a non-empty tree is 1 plus the greater of the heights of its subtrees.

1. Write an appropriate JUnit test class for a BiTree  visitor called GetHeight that computes the height of a binary tree.

2. Write the code for GetHeight.

Exercise #3: Count the number of leaf nodes of a binary tree.

A binary tree is said to be a leaf node, if  it is not empty and its two subtrees are empty.  

Thus, the number of leaf nodes in an empty binary tree is 0.

The number of leaf nodes in the tree

  A
 / \
*   *

 is 1.

The number of leaf nodes in the tree

    A
   / \
  B   *
 / \
*   *

The number of leaf nodes in the tree

     A
   /   \
  B     C
 / \   / \
*   * *   *

1. Write the (recursive) definition of the number of leaf nodes in a binary tree.

2. Write an appropriate JUnit test class for a BiTree  visitor called CountLeaves that counts the number of leaf nodes in a binary tree.

3. Write the code for CountLeaves.

 Exercise #4: Tree Traversal Algorithms

There are times in processing a binary tree, we need to visit each node in the tree in a specific order.  The three most common ways to traverse a binary tree are:

1. Pre-order traversal:

   • to pre-order traverse an empty tree: process the empty tree..

   • to pre-order traverse a non-empty tree: process the root node, then pre-order traverse the left subtree, then pre-order traverse the right subtree.
     

2. In-order traversal

   • to in-order traverse an empty tree: process the empty tree..

   • to in-order traverse a non-empty tree: in-order traverse the left subtree, the process the root node, then in-order traverse the right subtree.
     

3. Post order traversal

   • to post-order traverse an empty tree: process the empty tree..

   • to post-order traverse a non-empty tree:  post-order traverse the left subtree, then post-order traverse the right subtree, then .process the root node.
     

These traversal algorithms can be easily expressed as visitors to the BiTree.  The following three problems are to illustrate each of the above traversal algorithms.

1. Write a visitor called PreOrderString that returns the String containing the toString() of the nodes of a given binary tree when it is traversed in pre-order.  The nodes' strings should be separated by a space with no leading space nor trailing space.  The empty case should return the empty string "".   
   For example, for the tree
   

        A
      /   \
     B     C
    / \   / \
   *   * *   *
   

   the visitor will return "A B C".
   
   Write an appropriate JUnit test class.
   
   

2. Write a visitor called InOrderString that returns the String containing the toString() of the nodes of a given binary tree when it is traversed in in-order.  The nodes' strings should be separated by a space with no leading space nor trailing space.  The empty case should return the empty string "".   
   For example, for the tree
   

        A
      /   \
     B     C
    / \   / \
   *   * *   *
   

   the visitor will return "B A C".
   
   Write an appropriate JUnit test class.
   
   

3. Write a visitor called PostOrderString that returns the String containing the toString() of the nodes of a given binary tree when it is traversed in post-order.  The nodes' strings should be separated by a space with no leading space nor trailing space.  The empty case should return the empty string "".   
   For example, for the tree
   

        A
      /   \
     B     C
    / \   / \
   *   * *   *
   

   the visitor will return "B C A".
   
   Write an appropriate JUnit test class.

Last Revised Thursday, 03-Jun-2010 09:50:13 CDT

©2006 Stephen Wong and Dung Nguyen