geneseo.cs.sc
Class OrderedTree

java.lang.Object
  geneseo.cs.sc.OrderedTree

All Implemented Interfaces:

java.io.Serializable

public class OrderedTree

extends java.lang.Object

implements java.io.Serializable

Represents ordered binary trees containing arbitrary objects. These trees conform to a recursive definition of "tree" as a structure that is either

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

These trees are "ordered" in the sense that the objects in the trees are required to support a "less than" relation (Java interface Comparable), and objects are placed in a tree in such a way that all object's in the tree's left subtree are less than the root object, and all objects in the right subtree are greater than or equal to the root object.

The messages these trees handle are generally standard ones for any ordered tree class. Some are destructive, and therefore do not require assignments within client code when modifying trees.

This class was created as a support tool for the text Algorithms & Data Structures: The Science of Computing by Doug Baldwin and Greg Scragg. All references herein to "the text" refer to that book. Trees are described in Chapter 13 of the text. Some of the methods of this class are ones "left to an exercise" in the text.

See Also:

Comparable, Serialized Form

Constructor Summary

OrderedTree()
Initialize a new ordered tree to be empty.

Method Summary

void	addNode(java.lang.Comparable newValue) Adds a new value to the tree in a leaf position that maintains the tree's order.
protected void	cutAndRaise() Removes a tree's root node.
void	delete(java.lang.Comparable target) Removes one occurrence of a value from a tree.
boolean	find(java.lang.Comparable target) Determines whether a tree contains a value.
OrderedTree	getLeft() Extracts the left subtree of a tree.
OrderedTree	getRight() Extracts the right subtree of a tree.
java.lang.Comparable	getRoot() Extracts the root of a tree.
void	insertValue(java.lang.Comparable newValue) Replaces a tree with a leaf -- i.e., replaces any value at the root of the tree, and makes both subtrees empty.
boolean	isEmpty() Determines whether a tree is empty.
OrderedTree	makeNewTree() Create a new tree that is an instance of the same class as this tree.
void	printTree() Prints the contents of a tree in order.
void	printTreePostOrder() Prints the contents of a tree in postorder (i.e., subtrees before roots).
void	printTreePreOrder() Prints the contents of a tree in preorder (i.e., roots before the contents of their subtrees).
void	restore(java.lang.String fileName) Restores a binary tree from a file.
void	save(java.lang.String fileName) Writes a tree to a file, replacing any previous data in that file.
protected void	setLeft(OrderedTree newLeft) Replaces the left subtree of a tree.
protected void	setRight(OrderedTree newRight) Replaces the right subtree of a tree.
protected void	setRoot(java.lang.Comparable newValue) Replaces the root value in a tree.
java.lang.String	toString() Generates a string representation of a tree.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

OrderedTree

public OrderedTree()

Initialize a new ordered tree to be empty. For example

OrderedTree tree = new OrderedTree();

Method Detail

makeNewTree

public OrderedTree makeNewTree()

Create a new tree that is an instance of the same class as this tree. This message is used, for example, when adding an item to a tree requires creating new subtrees for that tree. The new subtrees should be instances of the same class as the tree itself, even if that tree is an instance of a subclass of OrderedTree. Every subclass of OrderedTree must therefore provide a method for handling this message that returns a new instance of that subclass. Clients are unlikely to ever invoke this method directly, but it is essential to the correct functioning of other methods defined for trees.

getRoot

public java.lang.Comparable getRoot()

Extracts the root of a tree. The tree itself remains unchanged. For example

Comparable r = someTree.getRoot();

Returns:

The value at the root of the tree.

getLeft

public OrderedTree getLeft()

Extracts the left subtree of a tree. The tree itself remains unchanged. For example

OrderedTree subtree = someTree.getLeft();

Returns:

The left subtree of the tree.

getRight

public OrderedTree getRight()

Extracts the right subtree of a tree. The tree itself remains unchanged. For example

OrderedTree subtree = someTree.getRight();

Returns:

The right subtree of the tree

setRoot

protected void setRoot(java.lang.Comparable newValue)

Replaces the root value in a tree. For example

someTree.setRoot( "new" );

Most clients should not use this message, but methods in subclasses that need to construct trees in unusual ways may find it helpful.

Parameters:

newValue - The new root value.

setLeft

protected void setLeft(OrderedTree newLeft)

Replaces the left subtree of a tree. For example

someTree.setLeft( otherTree );

Most clients should not use this message, but methods in subclasses that need to construct trees in unusual ways may find it helpful.

Parameters:

newLeft - The tree that should replace the left subtree.

setRight

protected void setRight(OrderedTree newRight)

Replaces the right subtree of a tree. For example

someTree.setRight( otherTree );

Most clients should not use this message, but methods in subclasses that need to construct trees in unusual ways may find it helpful.

Parameters:

newRight - The tree that should replace the right subtree.

isEmpty

public boolean isEmpty()

Determines whether a tree is empty. For example

if ( someTree.isEmpty() ) ...

Returns:

True if the tree is empty, false otherwise.

find

public boolean find(java.lang.Comparable target)

Determines whether a tree contains a value. The value is considered to be in the tree if any subtree's root is equal to the value according to the equals message. For example

if ( someTree.find("Hello") ) ...

Parameters:

target - The value to seek.

Returns:

True if the value is contained somewhere within the tree, false otherwise.

delete

public void delete(java.lang.Comparable target)

Removes one occurrence of a value from a tree. Searches the tree for a node containing the value, using the equals message to determine whether the target value matches the node's value, and removes that occurrence. This message alters the tree. For example

someTree.delete( "Goodbye" );

Parameters:

target - The value to remove from the tree.

insertValue

public void insertValue(java.lang.Comparable newValue)

Replaces a tree with a leaf -- i.e., replaces any value at the root of the tree, and makes both subtrees empty. For example

someTree.insertValue( "replacement" );

Parameters:

newValue - The new root value.

addNode

public void addNode(java.lang.Comparable newValue)

Adds a new value to the tree in a leaf position that maintains the tree's order. For example

someTree.addValue( "new" );

Parameters:

newValue - The value to insert into the tree.

cutAndRaise

protected void cutAndRaise()

Removes a tree's root node. Replaces the root, if necessary, with a value from one of the subtrees, so that all values originally in the tree except the root remain in the tree, and the tree remains ordered. For example

someTree.cutAndRaise();

printTree

public void printTree()

Prints the contents of a tree in order. For example

someTree.printTree();

printTreePreOrder

public void printTreePreOrder()

Prints the contents of a tree in preorder (i.e., roots before the contents of their subtrees). For example

someTree.printTreePreOrder();

printTreePostOrder

public void printTreePostOrder()

Prints the contents of a tree in postorder (i.e., subtrees before roots). For example

someTree.printTreePostOrder();

save

public void save(java.lang.String fileName)

Writes a tree to a file, replacing any previous data in that file. For example

someTree.save( "TreeFile" );

Parameters:

fileName - The name of the file to write the tree to.

restore

public void restore(java.lang.String fileName)

Restores a binary tree from a file. For example

someTree.restore( "TreeFile" );

After restoring a tree, the contents of the tree are replaced by the contents of the file, if possible. If for some reason the file couldn't be read, the contents of the tree are unchanged.

Parameters:

fileName - The name of the file to restore the tree from.

toString

public java.lang.String toString()

Generates a string representation of a tree. For example

String text = someTree.toString();

Returns:

The string representation of the tree. An empty tree is represented as "< >", and a non-empty tree as a bracket ("<"), the left subtree, the root value, the right subtree, and finally a closing bracket (">").