DataStructures
Class SearchTree

java.lang.Object
  |
  +--DataStructures.SearchTree

public abstract class SearchTree

extends java.lang.Object

A class implementing binary search trees.

Trees are created using the empty and add methods, for example:

   SearchTree t = SearchTree.empty();
   t = t.add(item);
 

where item belongs to a class implementing the Comparable interface.

Elements can be removed by

   t = t.remove(item);
 

Trees can be traversed using an enumeration, for example:

   for (Enumeration e = t.elementsInOrder(); e.hasMoreElements();) {
       System.out.println(e.nextElement());
   }
 

Author:

Peter Williams

See Also:

Enumeration

Constructor Summary

SearchTree()

Method Summary

abstract SearchTree	add(java.lang.Comparable item) Adds an item into the tree, preserving the ordering property.
abstract boolean	contains(java.lang.Comparable item) Tests whether the item is present in the tree.
abstract java.util.Enumeration	elementsInOrder() Provides an enumeration of the elements of the tree in order.
abstract java.util.Enumeration	elementsLevelOrder() Provides an enumeration of the elements of the tree in level order.
static SearchTree	empty() Returns an empty tree.
abstract boolean	isEmpty() Tests if the tree is empty.
abstract int	nrNodes() Counts the number of nodes in the tree.
abstract SearchTree	remove(java.lang.Comparable item) Removes an item from the tree, preserving the ordering property.
abstract java.lang.String	toString() Converts the tree to a string.

Methods inherited from class java.lang.Object

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

Constructor Detail

SearchTree

public SearchTree()

Method Detail

empty

public static SearchTree empty()

Returns an empty tree.

isEmpty

public abstract boolean isEmpty()

Tests if the tree is empty.

Returns:

the status of the tree.

nrNodes

public abstract int nrNodes()

Counts the number of nodes in the tree.

Returns:

the number of nodes in the tree.

contains

public abstract boolean contains(java.lang.Comparable item)

Tests whether the item is present in the tree.

Parameters:

item - the item to search for.

add

public abstract SearchTree add(java.lang.Comparable item)

Adds an item into the tree, preserving the ordering property.

Parameters:

item - the item to add.

Returns:

a tree with the item added

remove

public abstract SearchTree remove(java.lang.Comparable item)

Removes an item from the tree, preserving the ordering property.

Parameters:

item - the item to remove.

Returns:

a tree with the item removed

elementsInOrder

public abstract java.util.Enumeration elementsInOrder()

Provides an enumeration of the elements of the tree in order.

Returns:

the enumeration

elementsLevelOrder

public abstract java.util.Enumeration elementsLevelOrder()

Provides an enumeration of the elements of the tree in level order.

Returns:

the enumeration

toString

public abstract java.lang.String toString()

Converts the tree to a string.

Overrides:

toString in class java.lang.Object

Returns:

the string representation.