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.)
main
method in the BinaryTreeLab
class.What other methods are provided in the code ?
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.
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.
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.) 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.
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?
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 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
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
-- takes an Object
as a parameter and
returns true
if the object is in the tree; false
otherwise numOccurrences
-- takes an Object
as a parameter
and returns the number of occurrences of the object in the treeThe breadth-first add
method and breadthFirstTraversal
method have almost the same algorithm. Note, though, that while the add
method uses instance variables directly, the breadthFirstTraversal
method makes use of accessor methods.
add
method have been implemented using
method invocations rather than accessing instance variables directly?
Could the breadthFirstTraversal
method have been implemented using
instance variables?
breadthFirstTraversal
method have been implemented
outside the BinaryTree
class as client code? If so, would
anything about the code have to change? Try implementing a version of
the breadthFirstTraversal
method as a static
method
in the BinaryTreeLab
class. (Why would it have to be static
?)
numNodes
or 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
outside the BinaryTree
class, however, by implementing a new NodeVisitor
.
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.
Implement the equals
method. This method takes an Object
as a parameter and returns true
if it is a BinaryTree
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
the hashCode
method; in this case, you may redefine it to throw
an UnsupportedOperationException
.
Authors: Autumn C. Spaulding autumn@max.cs.kzoo.edu
and Alyce Brady abrady@kzoo.edu