Lab 12 — Extending the Binary Tree Class

Purpose

Prerequisites

Understanding of sections 13.1 through 13.4 of Algorithms and Data Structures: The Science of Computing.

Understanding of asymptotic notation, as described in section 9.2 of Algorithms and Data Structures: The Science of Computing.

Background

Binary trees are defined in sections 13.1 and 13.2 of Algorithms and Data Structures: The Science of Computing. Ordered binary trees are defined in section 13.3. This lab uses certain technical terms related to trees (e.g., height, leaves), which are defined in section 13.1. The notion of a “fully balanced” tree is defined in section 13.3.5.

Algorithms and Data Structures: The Science of Computing describes a class that represents ordered binary trees. A complete implementation of this class is available, in a file named OrderedTree.java. The “Final Details” section of this document explains where to find this file.

Any Java source file that uses the OrderedTree class should “import” it via a statement of the form

    import geneseo.cs.sc.OrderedTree;

Subclasses of OrderedTree are subtle in several ways. These subtleties generally parallel those of recursive lists, discussed in section 11.5.1 of Algorithms and Data Structures: The Science of Computing. For this lab, pay particular attention to the makeNewTree method, and to the need for casts when using the getLeft and getRight messages to extract subtrees that will receive recursive messages.

The Comparable Interface

One of the steps in this lab requires determining whether a tree is correctly ordered, which in turn requires determining whether one element is less than or equal to another. The standard Java class library defines an interface named Comparable that is implemented by all standard classes for which one value can meaningfully be less than another. (See section A.5.3 in the appendix to Algorithms and Data Structures: The Science of Computing for an introduction to interfaces.) Only objects that implement Comparable can be stored in ordered binary trees.

Any class that implements Comparable handles a compareTo message, which takes an arbitrary object as its only parameter, and returns an integer according to the following rules:

• a.compareTo(b) is negative if a < b
• a.compareTo(b) is zero if a = b
• a.compareTo(b) is positive if a > b

Thus, for example, the following code compares two strings (the String class implements Comparable, using alphabetical order to decide whether one string is less than another) to see if string1 is less than string2:

    String string1 = ....;
    String string2 = ....;
    if ( string1.compareTo(string2) < 0 ) ....

Exercise

Design and analyze a subclass of OrderedTree that includes the methods described below. Specifically, do the following for each method:

• Develop an algorithm for the method
• Prove the algorithm correct
• Derive the worst-case asymptotic execution time of the algorithm, as a function of tree size (i.e., the number of elements in the tree).

Finally, write in Java a subclass of OrderedTree that includes all of the methods. Write a main program that tests this subclass (trees of Integer objects are good things to test the subclass with, since Integers are objects that are easy to create, that can be stored in ordered trees, and for which it is relatively easy to find the smallest and largest possible value — hint: knowing the smallest and largest values that can possibly be stored in a tree may be helpful for one of the problems in this lab).

The Height of a Tree

Design a method that computes the height of a binary tree. Specifically, this method has no parameters, and returns an integer equal to the height of the tree.

Are Two Trees Identical?

Define two binary trees to be identical if either both are empty, or their roots are equal, their left subtrees are identical, and their right subtrees are identical.

Design a method that determines whether two binary trees are identical. This method takes a second binary tree as its only parameter, and returns a boolean value: true if the tree receiving the message is identical to the parameter, and false otherwise. Use Java’s equals message to determine whether the trees’ roots are equal.

Is a Tree Ordered?

Design a method that determines whether a binary tree is an ordered binary tree. This method returns a boolean value, true if the tree is an ordered binary tree, and false if it is not. The method may take any parameters that are helpful in solving this problem.

You may assume as a precondition that the trees you are testing will never contain duplicate items.

Final Details

Finding the OrderedTree Class

File OrderedTree.java can be Downloaded from the World Wide Web.

Documentation for the OrderedTree class is also available on the Web. The main documentation page is an index to documentation for all the Java classes written for use with Algorithms and Data Structures: The Science of Computing. To see the documentation for a specific class, click on that class’s name in the left-hand panel of the page.

Submitting Your Work

This lab is due on Monday, April 18. Turn in a printout of the code you write, along with the correctness proofs and execution time analyses for your algorithms. The proofs and analyses can be comments in the code, or can be written on a separate sheet of paper.

In addition to your code, proofs, and analyses, turn in two or three sentences discussing any generalizations you can make about container objects, based on the experience you now have with lists and trees. (Lists and trees are both containiners, i.e., objects that exist to store other objects. You have probably noticed that programming with lists is a lot like programming with trees in some respects, and different in others. Based on such observations, your sentences should say a little bit about what features you would expect all containers to have, and what ways you would expect different containers to differ from each other.)

Portions copyright © 2004. Charles River Media. All rights reserved.

Revised Apr. 10, 2005 by Doug Baldwin