← back to the schedule


Binary Trees PROJECT

By Autumn C. Spaulding with Alyce Brady



Over the next few labs you will be working with several different Binary Tree data structures. The incomplete class diagram on the right shows a K_BinaryTree interface, with a K_RecBinaryTree class that implements the interface as a recursive data structure. The diagram also shows two subclasses of K_RecBinaryTree that provide more specialized binary trees — K_CompleteRecBinTree, which implements a recursive Complete Binary Tree, and K_BST, which implements a Binary Search Tree — as well as two related test drivers, BinaryTreeTester and BSTTester.

This lab will focus on K_RecBinaryTree and its K_CompleteRecBinTree subclass; a future lab will focus on K_BST.

Implementing a Binary Tree

A recursive definition of a binary tree is that it is either:

  • An empty tree; or
  • A node, called a root, containing the data and two children, left and right, each of which is itself a binary tree.

Understanding the Code

In preparation for this lab, you should be familiar with the general methods and properties of binary trees. You should also be familiar with the concept of tree traversal methods. In this lab you will implement client code to construct a tree, and you will implement several traversals.

  • Download six files into a new Trees folder:
  • K_BinaryTree: Look over the K_BinaryTree interface to see which methods are specified.
  • K_RecBinaryTree: Look at the K_RecBinaryTree class. Start with the class documentation at the top of the file and then look at the instance variables, constructor(s), and basic observer methods (isEmpty, getData, leftChild, and rightChild) to see how this implementation represents empty trees, leaves, and non-leaf nodes.
  • Look at the javadoc comments for the add method and re-read the class documentation to understand why instances of this class happen to always be complete binary trees. (What is a complete binary tree?)
  • Note that K_RecBinaryTree does not support a remove method, throwing an UnsupportedOperationException instead.
    Stop and Think: Why is removing a node from a binary tree trickier than removing a node from a linked list? Does it matter whether the node you might want to remove is a leaf node, a non-leaf node with non-empty left and right children, a non-leaf node with an empty left child, or a non-leaf node with an empty right child? If you could remove an arbitrary node from a tree, would the tree still qualify as a complete binary tree?
  • There are several other methods in K_RecBinaryTree, some of which have not been fully implemented. You can delay reading them until you get to the implementation phase.
  • K_CompleteRecBinTree: Read the class documentation for the K_CompleteRecBinTree class. The purpose of this class is to provide a "complete" implementation for a complete binary tree, including support for a remove method. Look at the javadoc comments and signatures for the methods without reading all of the code in the method bodies. What instance variables, constructor(s), or methods does this method have? Is that what you expected?
  • Look again at both K_RecBinaryTree and K_CompleteRecBinTree. How many constructors do these classes have? Is that what you expected? Can we construct empty trees and trees with internal nodes and leaf nodes with the methods provided, or do we need additional methods for basic tree construction?

Initial Experimentation

Identify Expected Results

  • Look over the BinaryTreeTester test driver and the K_RecBinaryTree and K_CompleteRecBinTree classes. What do you expect will be the result if you run the program without modifying any of these three classes?
    Tip: Always explicitly identify expected results before running a test. If it is complicated, write your expected results down. Otherwise it is too easy to see actual results and say, "Yeah, that looks right," even if the results are close but wrong.
  • Note that the test driver adds values (12, 7, 3, etc.) to the tree. What tree do you expect this to construct? Draw it out. What should be the result of a pre-order traversal? A breadth-first traversal?
    The tree expects Integer objects rather than int values, but Java "auto-boxing" will turn int values into Integer objects automatically, when needed.

Actual Results - Run the Code

  • Copy your queue interface and class, along with the linked list classes used by your queue implementation, into your Trees folder.
  • Compile and run the BinaryTreeTester program as provided. Did it behave as expected? If not, study the code further to understand why not. Was the problem with the actual results, or with your expected results? Study the code to understand any differences in behavior.
  • How much of the K_RecBinaryTree and K_CompleteRecBinTree classes can you test with the methods you have so far? What more would you need to test it more thoroughly?

Understanding Visitors

Find the method in the K_RecBinaryTree class for doing a pre-order depth-first traversal. Notice that it takes a single NodeVisitor parameter. 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. A traversal could consist 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 responsible for executing the appropriate action.

  • Read over the NodeVisitor interface and the PrintAction class. Do you see how this could result in printing all of the data elements in the tree if the visit mathod in the PrintAction class were called for each node in the tree?

Recursive Depth-First Traversals

Remember that, in addition to breadth-first traversals, there are three depth-first ways to traverse a tree.

Because of the recursive nature of the binary tree structure, 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,
        view or do something with the root ("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?

  • Note that although the preOrderTraversal method in K_RecBinaryTree has not been completed, the postOrderTraversal method has been. Add code to the test driver to test the postOrderTraversal method. How do you expect the program to behave now? Be explicit about exactly what you expect the results to be. Run the program. Did the actual results match your expected results? If they did not match, was the problem with the actual results, or with your expected results? Study the code to understand any differences in behavior.
  • Compare the provided postOrderTraversal method with the algorithm above. Implement the preOrderTraversal method in K_RecBinaryTree using the algorithm above and the implementation of the postOrderTraversal method as guides. Specify what results you expect to see when you run the program. Run it. Did the actual results match your expected results? If they did not match, was the problem with the actual results, or with your expected results?
  • Implement the inOrderTraversal method. Add code to the test driver to test your completed method. Are the results the same or different from your previous results with the pre-order traversal? Are the results what you expected?

Breadth-First Traversal

  • Read over the add method to see how it adds elements in breadth-first order.
  • Implement the breadthFirstTraversal method in K_RecBinaryTree using a queue and a loop similar to that in the add method. (The breadthFirstTraversal method is simpler, though.) Re-run the program. Are the results what you expected?

Additional Methods

Add signatures for the following methods to the K_BinaryTree interface.

  • isLeaf() Returns true if the node is a leaf node; false otherwise. (This method is not recursive, but could be used by other recursive methods.)
  • numNodes() Returns the number of nodes in the tree.
  • numLeaves() Returns the number of leaves (nodes with no non-empty children) in the tree.
  • contains(T item) Takes an object as a parameter and returns true if the object is in the tree; false otherwise.
  • numOccurrences(T item) Takes an object as a parameter and returns the number of occurrences of the object in the tree.

Implement these methods in K_RecBinaryTree. Most of these methods will follow a 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 existing height method in K_RecBinaryTree is similar to a post-order traversal, while the algorithm below is an example of pre-order handling. 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

Add appropriate tests to your test driver.

Other Visitors

We can add new functionality to the program without having to modify the K_RecBinaryTree class if the behavior is just based on the data values in the tree and not their relationships to each other. We can do this by creating new Visitor classes.

  • Implement a new class (name it SumReduction), similar to the PrintAction class, that implements the NodeVisitor interface. Note that this class specifies that the data elements in the binary tree nodes are Integer objects. Your class should sum the data elements in the visit method, keeping track of the sum as an int instance variable. (The method should never be called with a null data parameter, but it is still a good idea to check for that before adding the value to the sum.) Your new class should also have an additional method that returns the sum. Modify the test driver to test your ability to calculate and then print the sum.
  • Another useful method for a binary tree would be a method that calculated the maximum or minimum value in the tree. 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 test driver 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.
Note: numNodes, contains, and numOccurrences above could have been implemented as visitors rather than embedded methods in the K_RecBinaryTree class. The numLeaves method, on the other hand, could not, unless the NodeVisitor interface were changed so that the visit method takes a node as a parameter rather than just the node's data element.

Clean and Refactor

Follow this link to clean and refactor your comments and code.

Submission

Submit your completed program through Kit, under Binary Tree.

Have fun! And if you have any questions remember I am available through email, Teams, and my office hours. And don't forget the Collaboration Center, which is a great place to work and ask questions too!



← back to the schedule