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. (Berman, "Data Structures via C++:Objects by Evolution", 1997.)
mainmethod in the
What other methods are provided in the code ?
mainmethod 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
intprimitives, you will need to use the
Find the method in the
BinaryTree class for doing a breadth-first
traversal. Notice that it takes a single parameter, which is a
NodeVisitor is an interface that specifies
a single method, the
visit method. The
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.
NodeVisitorclass gets passed to the traversal algorithm to print values. (The code to do this is already in the
mainmethod, but is commented out.)
PrintActionclass, that implements the
NodeVisitorinterface. Your new class should assume that the data elements in the binary tree nodes are
Integerobjects (as they are in this case) and sum them up. Your class should keep track of the sum as an
intinstance variable and, in the
visitmethod, 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
Integerand then use the
intValuemethod. (Document the precondition that the parameter must be an
Integer.) Provide an additional method that you can call from the
mainafter 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.
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?
PrintActionvisitor 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 the following methods using recursion. Most 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
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
trueif the node is a leaf node;
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-- takes an
Objectas a parameter and returns
trueif the object is in the tree;
numOccurrences-- takes an
Objectas a parameter and returns the number of occurrences of the object in the tree
add method and
method have almost the same algorithm. Note, though, that while the
method uses instance variables directly, the
method makes use of accessor methods.
addmethod have been implemented using method invocations rather than accessing instance variables directly? Could the
breadthFirstTraversalmethod have been implemented using instance variables?
breadthFirstTraversalmethod have been implemented outside the
BinaryTreeclass as client code? If so, would anything about the code have to change? Try implementing a version of the
breadthFirstTraversalmethod as a
staticmethod in the
BinaryTreeLabclass. (Why would it have to be
depth? Justify your answers.
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
BinaryTree class, however, by implementing a new
ExtremeValueCalculatorto find the extreme values (minimum and maximum) in a tree. The
ExtremeValueCalculatorclass should have two
Comparableinstance variables, representing the largest and smallest values seen so far. In the
visitmethod, if the
null, do nothing. If it is not
null, then cast it to a
Comparableand 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
mainafter 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.
equals method. This method takes an
as a parameter and returns
true if it is a
and is equal to this binary tree.
We will define two binary trees as equal
if the two binary trees have
the same nodes in the same locations in the tree.
Whenever you redefine the
equals method, you should also redefine
hashCode method; in this case, you may redefine it to throw
Authors: Autumn C. Spaulding email@example.com
and Alyce Brady firstname.lastname@example.org