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.)
We are defining a BinaryTree
class as a wrapper around
a TreeNode
object, called a root (each TreeNode
object
contains the data and two children, left and right, each of which are themselves
TreeNode
objects).
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 than 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 treeequals
-- takes an Object
as a parameter and
returns true
if it is a BinaryTree
and is equal
to this binary tree; two binary trees are equal if they contain the same nodes
(and the same number of each node), although the order of the nodes and the
shape of the trees may differ (NOTE: whenever you redefine the equals
method, you should also redefine the hashCode
method; in this
case, you may redefine it to throw an UnsupportedMethodException
.)
Hint: Here's an approach you might try. Create a recursive helper
method that returns true if two trees passed to it as parameters both have
the same number of occurrences of all the values in this tree. The
recursive calls would step through the subtrees of this tree as usual, but
would continue to pass the same two trees as parameters (see the example
below, which looks worse than it really is). The structure of the
recursive helper method would be very similar to your other recursive methods.
The equals
method, though, would simply call the helper method,
passing itself and the other tree as the two parameters.
Example: Let variables a
and b
be binary trees
(a) and (b) in Figure 8.1 on p. 279 (which we can see are equal).
Consider the expression a.equals(b)
. The equals
method would call the recursive helper, passing it trees a
and b
as actual parameters. Assume that the formal
parameter names for the two trees in the recursive helper method are
t1
and t2
. (So, t1
is tree
(a) and t2
is tree (b).) The recursive helper method
would verify that trees t1
and t2
have the same
number of occurrences of the root value in this tree (A) and the
same number of occurrences of all values in the left and right subtrees
of this tree. The recursive call to the left subtree would verify
that trees t1
and t2
(which are still trees (a)
and (b)) have the same number of occurrences of the root value in this subtree
(B) and the same number of occurrences of all values in the left
and right subtrees of this tree. Those subtrees are empty, so the
recursive call can just return true
when called for them.
(Equal trees do not need to contain the same number of empty "dummy"
subtrees.) Similarly, the recursive call to the right subtree of the
original tree would verify that trees t1
and t2
have the same number of occurrences of the root value in that subtree (C)
and the same number of occurrences of all values in the (empty) left and
right subtrees of that tree.
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 they contain the same nodes (and the same number of each node), although
the order of the nodes and the shape of the trees may differ. (NOTE: another
definition of equals
could insist that 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 UnsupportedMethodException
.
Hint: Here's an approach you might try. Create a recursive helper method
that returns true if two trees passed to it as parameters both have the same
number of occurrences of all the values in this tree. The recursive
calls would step through the subtrees of this tree as usual, but would continue
to pass the same two trees as parameters (see the example below, which looks
worse than it really is). The structure of the recursive helper method
would be very similar to your other recursive methods. The equals
method, though, would simply call the helper method, passing itself and the
other tree as the two parameters.
Example: Let variables a
and b
be binary trees
(a) and (b) in Figure 8.1 on p. 279 (which we can see are equal). Consider
the expression a.equals(b)
. The equals
method
would call the recursive helper, passing it trees a
and b
as actual parameters. Assume that the formal parameter
names for the two trees in the recursive helper method are t1
and t2
. (So, t1
is tree (a) and t2
is tree (b).) The recursive helper method would verify that trees t1
and t2
have the same number of occurrences of the root value
in this tree (A) and the same number of occurrences of all values in
the left and right subtrees of this tree. The recursive call to the
left subtree would verify that trees t1
and t2
(which
are still trees (a) and (b)) have the same number of occurrences of the root
value in this subtree (B) and the same number of occurrences of all
values in the left and right subtrees of this tree. Those subtrees are
empty, so the recursive call can just return true
when called
for them. (Equal trees do not need to contain the same number of empty
"dummy" subtrees.) Similarly, the recursive call to the right
subtree of the original tree would verify that trees t1
and t2
have the same number of occurrences of the root value in that subtree (C)
and the same number of occurrences of all values in the (empty) left and right
subtrees of that tree.
Authors: Autumn C. Spaulding autumn@max.cs.kzoo.edu
and Alyce Brady abrady@kzoo.edu