SUNY Geneseo, Department of Computer Science

Lab 11

CSci 141, Fall 2003

Prof. Doug Baldwin

Due Wednesday, November 12

Purpose

Background

A binary tree can be defined recursively as

• A record (the root) associated with two smaller trees (the left and right subtrees), or
• Empty

This definition suggests a small set of primitive operations for binary trees, namely

root

Returns the root record in a binary tree

left

Returns a binary tree's left subtree

right

Returns a binary tree's right subtree

setRoot

Replaces the value at the root of a binary tree

setLeft

Replaces a binary tree's left subtree

setRight

Replaces a binary tree's right subtree

isEmpty

Returns True if a binary tree is empty, False if not

A constructor with no parameters

Initializes a binary tree to be empty

A constructor whose parameters are a record, a, and two other binary trees, l and r

Initializes a binary tree so that its root is a, its left subtree is l, and its right subtree is r

I have written a Java class, BinaryTree, that implements these operations (and a few more). You can find this class in file "BinaryTree.java" in our folder of the Course Materials file server, or you can Download it from the Web at http://cs.geneseo.edu/~baldwin/sc/BinaryTree.java. You can also find Full Documentation for the class on the Web, at http://cs.geneseo.edu/~baldwin/sc/doc/ (This URL documents several classes I have written for this course; to see the documentation for a specific class, click on its name in the table of contents on the left side of the window.)

One of the things the BinaryTree class allows is saving trees to files and retrieving them from files. I have provided several files with trees in them. File names and descriptions are as follows:

EmptyTree

A file that contains the empty tree

AnimalTree

A file that contains a tree made up of the names of some animals.

ColorTree

A file that contains a tree containing the names of some colors.

InstrumentTree

A file that contains a tree containing the names of some musical instruments.

You can find these files in our folder on the Course Materials server. These trees are not search trees, so don't be surprised to find that the words in them are in no particular order.

Another thing BinaryTree objects do is provide a printed representation. In printed trees, angle brackets indicate the nesting of smaller trees inside larger ones. For example, the printed form

<<< > a < >> aa << > aal < >>>

denotes a tree containing "aa" as its root; the left subtree is "<<> a <>>", i.e., a tree that contains "a" and two empty sub-subtrees (denoted by empty pairs of angle brackets); the right subtree is "<<> aal <>>", which contains "aal" and two more empty sub-subtrees. As you can see, this printed form is almost unreadable, but it does concisely yet precisely show a tree's structure and content.

Exercise

Write a subclass of BinaryTree that provides the additional operations described below. I call this class ExtendedTree, although you can name it anything you like in your own program. Each operation should be implemented as a recursive method in your subclass. Also give a correctness proof for each method, and derive the number of primitive BinaryTree messages each sends as a function of tree size.

Constructor

A constructor that takes an ordinary binary tree (i.e., a BinaryTree object) as its only parameter, and that initializes an ExtendedTree that contains the same items as the parameter (and no other items), in the same relative positions within the tree.

display

The display message writes all the items in an extended binary tree to System.out in a more readable format than you get if you just use println. For example, you might write each item on a line by itself.

equals

The equals message takes a BinaryTree as its parameter, and compares that tree to the one receiving the equals message. If the two trees are equal (i.e., contain the same values in the same relative positions), then equals returns true, otherwise it returns false.

Follow-Up