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:
- An empty tree; or
- 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.
- Download the Trees.zip file and create a project for it.
- 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.
- What properties does an empty tree have?
- Look at the constructor provided. Does it match your expectations?
- Construct an empty tree in the
main
method in theBinaryTreeLab
class.
Breadth-First Insertion
What other methods are provided in the code ?
- 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?
-
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 thanint
primitives, you will need to use theInteger
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.
-
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 themain
method, but is commented out.). -
Implement a new class(name it
SumReduction
), similar to thePrintAction
class, that implements theNodeVisitor
interface. Your new class should assume that the data elements in the binary tree nodes areInteger
objects (as they are in this case) and sum them up. Your class should keep track of the sum as anint
instance variable and, in thevisit
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 anInteger
and then use theintValue
method. (Document the precondition that the parameter must be anInteger
.) Provide an additional method that you can call from themain
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?
-
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? - Implement a method that performs an in-order traversal.
- 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()
Returnstrue
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 anObject
as a parameter and returnstrue
if the object is in the tree;false
otherwise. -
numOccurrences(Object item)
Takes anObject
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.
- Correct implementation of the
Have fun! And if you have any questions remember my emailoffice hours, and the collaboration center are here for you!
← back to the schedule