Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)
The OrderedTree library class is a complete Java implementation
of the ordered binary tree class described in chapter 13 of Algorithms
and Data Structures: The Science of Computing. Source code for the class
is available in Java, so that students can use it as a starting point for exercises
related
to the chapter.
The OrderedTree class provides a set of primitives in terms of
which students (and instructors) can write Java code for tree algorithms, thus
gaining
hands-on experience with designing, coding, and using such algorithms. Students
will typically be assigned to develop these algorithms in laboratory or homework
exercises, although the algorithms could also be shown as demonstrations in
lectures.
Although the OrderedTree class nominally represents ordered binary trees,
it can be used to build unordered trees simply by avoiding the addNode, find,
and delete messages.
The easiest way to code new tree algorithms, and the way most consistent with
object oriented principles, is to make them methods of some subclass of OrderedTree.
Most exercises involving the OrderedTree class will thus ask students
to define such a subclass.
The OrderedTree class as implemented follows very closely the
class described in Algorithms and Data Structures: The Science of Computing.
Most of the code comes directly from section 13.4. Some methods (notably cutAndRaise)
are from later sections, and some are concrete implementations of algorithms
that are only sketched in the text (e.g., delete, the pre-order
and post-order printing traversals). All together, most of the class’s
design is described in the text. However, the implemented class does have some
features not in the text at all, including:
setRoot, setLeft, and setRight mutators,
which were added so that code in subclasses can make any changes to a tree’s
structure that the subclass requires.save and restore methods, which allow trees to be written to
and read from files. Two important reasons for providing these methods are
to allow
instructors to distribute prebuilt trees to students, and to allow students
to write programs
that save
trees before
stopping
and reload them upon starting, thus saving data structures from run to
run rather than having to build them from scratch in every run.toString method, which allows trees to be converted into strings, and
particularly allows println to print trees.A file named OrderedTree.java, which
defines the OrderedTree class,
can be downloaded from the Web. Documentation for the
class
is also available on the Web.
OrderedTree.java needs to be present in any program that uses lists.
The OrderedTree class is part of the geneseo.cs.sc package.
Source files that use the class thus usually import it.
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 9, 2005 by Doug Baldwin