← back to the schedule


MINI-LAB #6
Binary Trees

By Autumn C. Spaulding autumn@max.cs.kzoo.edu with Alyce Brady abrady@kzoo.edu



Implementing a Binary Tree

According to Berman, "Data Structures via C++:Objects by Evolution", 1997, a binary tree is either:

  1. An empty tree; or
  2. a node, called a root (the node contains the data), and two children, left and right, each of which are themselves binary trees.

Looking at the Code

In class you will have discussed some of the methods and properties that a BinaryTree class might contain. You should also be familiar with the concept of tree traversal methods. Today you will implement client code to construct a tree, and you will implement several traversals.

  1. Download the Trees.zip file and create a project for it.
  2. Look at the instance variables and constructor of the binary tree class provided to figure out how this implementation represents empty trees, leaves, and non-leaf root nodes.

Think about your constructor. Our definition talks about empty trees. Note that we can create a tree that is entirely empty.

  1. What properties does an empty tree have?
  2. Look at the constructor provided.  Does it match your expectations?
  3. Construct an empty tree in the main method in the BinaryTreeLab class.


Breadth-First Insertion

What other methods are provided in the code ?

  1. Look at the rest of the code, and determine how to add elements to a tree in breadth-first (top-down, left-to-right) order. What does it mean to add in breadth-first order?
  2. Modify the main method to insert the values 12, 7, 3, 4, 8, 25, 0, 142, 17, and 26 in your tree. Since the tree expects objects rather than int primitives, you will need to use the Integer class.

Visitors

Find the method in the BinaryTree class for doing a breadth-first traversal. Notice that it takes a single parameter, which is a NodeVisitor object. Actually, NodeVisitor is an interface that specifies a single method, the visit method. The visit method also takes a single parameter, which is a node in a binary tree. Basically, a traversal consists of stepping through all the nodes in a tree in a particular order, and calling the visit method of a particular NodeVisitor object for each node. This allows us to write generic traversal algorithms that can do a number of different activities. For example, we might have one NodeVisitor object that prints each node (see the PrintAction class), another that sums up numeric values in each node, and another than finds the minimum or maximum node value. Each of these tasks requires traversing the tree, but we don't need to write a separate traversal algorithm for each activity. Instead, we write traversal algorithms for each traversal ordering, and pass to each one an appropriate NodeVisitor object. The NodeVisitor is responsible for taking the appropriate action.

  1. Test your program by printing the values in the tree in breadth-first order. Note which NodeVisitor class gets passed to the traversal algorithm to print values. (The code to do this is already in the main method, but is commented out.).
  2. Implement a new class(name it SumReduction), similar to the PrintAction class, that implements the NodeVisitor interface. Your new class should assume that the data elements in the binary tree nodes are Integer objects (as they are in this case) and sum them up. Your class should keep track of the sum as an int instance variable and, in the visit method, should add the integer value of the data parameter to the sum, so long as the data parameter is not null. To do this, you will need to cast the parameter to an Integer and then use the intValue method. (Document the precondition that the parameter must be an Integer.) Provide an additional method that you can call from the main after the traversal is complete, which will return the computed sum. Test your new class by using it in a traversal and then asking for the sum.

Recursive Depth-First Traversals

How else might you traverse the tree? Remember that, in addition to the breadth-first traversal algorithm, there are three ways to traverse a tree using depth-first traversal algorithms.

Because of the recursive nature of the binary tree structure (trees are sometimes referred to as recursive data structures), the depth-first traversals can be implemented with recursion. Here is the algorithm for traversing a tree using a pre-order traversal:

    if the tree is not empty,
        visit the root
        recursively do a pre-order traversal of the left subtree
        recursively do a pre-order traversal of the right subtree

Question: What is the base case for this recursive algorithm?

  1. Implement the algorithm above for a pre-order traversal. Test your method using the PrintAction visitor and your new summing visitor. Are the results the same or different from your previous results with the breadth-first traversal? Are the results what you expected?
  2. Implement a method that performs an in-order traversal.
  3. Implement a method that performs a post-order traversal.

Additional Methods

Implement the following methods using recursion. Most of these methods will follow the typical depth-first recursive algorithm, but with more explicit handling of the base case than the traversal algorithms above. Some may need to handle more than one base case, such as both empty trees and leaves. The algorithm below is an example of pre-order handling, but a different order may be appropriate for some methods:
    if the tree is empty,
        handle this base case
    otherwise,
        do something with the root
        recursively call this method for the left subtree, possibly doing something with the return value
        recursively call this method for the right subtree, possibly doing something with the return value

  • isLeaf() Returns true if the node is a leaf node; false otherwise.
  • numNodes() Returns the number of nodes in the tree.
  • numLeaves() Returns the number of leaves (nodes with no children) in the tree.
  • depth() Returns the depth (or height) of the tree.
  • contains(Object item) Takes an Object as a parameter and returns true if the object is in the tree; false otherwise.
  • numOccurrences(Object item) Takes an Object as a parameter and returns the number of occurrences of the object in the tree.

Bonus Portion - Another Visitor

Another useful method for a binary tree would be a method that calculated the maximum or minimum value in the tree. We can calculate these values from outside the BinaryTree class, however, by implementing a new NodeVisitor.

Implement a new NodeVisitor class called ExtremeValueCalculator to find the extreme values (minimum and maximum) in a tree. The ExtremeValueCalculator class should have two Comparable instance variables, representing the largest and smallest values seen so far. In the visit method, if the data parameter is null, do nothing. If it is not null, then cast it to a Comparable and test it against the smallest and largest values seen so far. (Document the precondition that the parameter must be Comparable.) If either of the instance variables are null, or if the parameter is smaller than the smallest value or larger than the largest value seen so far, then set the appropriate instance variable to the parameter. (Could the parameter become both the smallest and the largest value seen so far? Be sure to handle this case.) Provide additional methods that you can call from the main after the traversal is complete, one of which will return the minimum value and one of which will return the maximum value (both Comparable). Test your new class by using it in a traversal and then asking for the minimum and maximum values.

Submit your completed program through Kit, under Mini-Lab 6.

EVALUATION

Mini-lab #6 is worth 15 points. This project will be submitted individually. The following items describe the criteria we will use to evaluate your mini-lab:

  • Correct implementation of sumReduction class 2 pts.
  • Correct implementation of preOrderTraversal() method. It should return: 12, 7, 4, 142, 17, 8, 26, 3, 25, 0 1.5 pts.
  • Correct implementation of postOrderTraversal() method. It should return: 142, 17, 4, 26, 8, 7, 25, 0, 3, 12 1.5 pts.
  • Correct implementation of inOrderTraversal() method. It should return: 142, 4, 17, 7, 26, 8, 12, 25, 3, 0 1.5 pts.
  • Correct implementation of isLeaf() method 1 pts.
  • Correct implementation of numNodes() method 1.5 pts.
  • Correct implementation of numLeaves() method 1 pts.
  • Correct implementation of depth() method 1.5 pts.
  • Correct implementation of contains() method 1 pts.
  • Correct implementation of numOccurrences() method 1 pts.
  • Adding appropriate amount of comments to the code (your name and description of the class, method description, and so on) 1 pt.
  • Proper organization of your code (indentation, clarity, cleverness) 0.5 pt.
  • Bonus portion:
    • Correct implementation of the ExtremeValueCalculator class 3 pts.

Have fun! And if you have any questions remember my emailoffice hours, and the collaboration center are here for you!



← back to the schedule