Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)
This lab reinforces students’ ability
to
design, code, and analyze algorithms related to binary trees. It also gives students
experience working with subclasses of the OrderedTree class defined for Algorithms
and Data Structures: The Science of Computing.
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.
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.
Comparable InterfaceOne 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 < ba.compareTo(b) is zero if a = ba.compareTo(b) is positive if a > bThus, 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 ) ....Design and analyze a subclass of OrderedTree that includes the
methods described below. Specifically, do the following for each method:
Finally, write in Java a subclass of OrderedTree that includes
all of the methods. Write a main program that tests this subclass (trees of
strings
are good things to test the subclass with, since strings are objects that are
easy to create and that can be stored in ordered trees).
Design a method that counts the elements in a binary tree. Specifically, the method takes no parameters, and returns an integer equal to the number of elements in the tree.
Design a method that returns the largest element in an ordered binary tree.
This method has no parameters, and returns a Comparable object.
Assume as a precondition that the tree is not empty.
Do two analyses of worst-case execution time for this algorithm: One analysis that assumes that the tree is fully balanced, and one that allows the tree to be arbitrarily imbalanced.
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.
Design a method that counts a binary tree’s leaves. Specifically, this method has no parameters, and returns an integer equal to the number of leaves in the tree.
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.
Design a method that determines whether or not a binary tree is fully balanced. This method takes no parameters, and returns a boolean value: true if the tree is fully balanced, and false if it is not.
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.
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.
Turn in your solution to this exercise as directed by your instructor.
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 8, 2005 by Doug Baldwin