DataStructures
Class SearchTree<E extends java.lang.Comparable<? super E>>

java.lang.Object
  DataStructures.SearchTree<E>

Type Parameters:

E - the type of elements held in this tree

All Implemented Interfaces:

java.lang.Iterable<E>

public class SearchTree<E extends java.lang.Comparable<? super E>>
extends java.lang.Object
implements java.lang.Iterable<E>

A class implementing binary search trees for elements of type E.

Elements of type E must implement the Comparable interface in their defining class or in some superclass.

Trees are created empty using

   SearchTree<Integer> t = new SearchTree<Integer>();
 

Items can be added by

   t.add(item);
 

where item is an element of type E .

Elements of type E can be removed by

   t.remove(item);
 

Trees can be traversed in order using an iteration, for example for an Integer tree:

   for (Integer i : t) {
       System.out.println(i);
   }
 

Author:

Peter Williams

See Also:

Comparable, Iterable, Iterator, Enumeration

Constructor Summary

SearchTree()
Constructs an empty tree suitable for holding comparable elements of type E

Method Summary

void	add(E item) Adds an item into the tree, preserving the ordering property.
boolean	contains(E item) Tests whether the item is present in the tree.
java.util.Enumeration<E>	elementsLevelOrder() Provides an enumeration of the elements of the tree in level order.
boolean	isEmpty() Tests if the tree is empty.
java.util.Iterator<E>	iterator() Iterates over the items in the tree using the in-order sequence.
int	nrNodes() Counts the number of nodes in the tree.
void	remove(E item) Removes an item from the tree, preserving the ordering property.
java.lang.String	toString() Converts the tree to a string.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

SearchTree

public SearchTree()

Constructs an empty tree suitable for holding comparable elements of type E

Method Detail

isEmpty

public boolean isEmpty()

Tests if the tree is empty.

Returns:

the status of the tree.

nrNodes

public int nrNodes()

Counts the number of nodes in the tree.

Returns:

the number of nodes in the tree.

contains

public boolean contains(E item)

Tests whether the item is present in the tree.

Parameters:

item - the item to search for.

Returns:

true if the tree contains this item, false otherwise

add

public void add(E item)

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

Parameters:

item - the item to add.

remove

public void remove(E item)

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

Parameters:

item - the item to remove.

elementsLevelOrder

public java.util.Enumeration<E> elementsLevelOrder()

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

Returns:

the enumeration

Throws:

java.util.NoSuchElementException - if the nextElement method is called when there is no next element

iterator

public java.util.Iterator<E> iterator()

Iterates over the items in the tree using the in-order sequence.

Specified by:

iterator in interface java.lang.Iterable<E extends java.lang.Comparable<? super E>>

Returns:

the iterator.

Throws:

java.util.NoSuchElementException - if the next method is called when there is no next element

java.lang.IllegalStateException - if the next method has not yet been called, or the remove method has already been called after the last call to the next method.

toString

public java.lang.String toString()

Converts the tree to a string.

Overrides:

toString in class java.lang.Object

Returns:

the string representation.