Algorithm
Development Kit 1.0

algs.model.tree
Class BinaryTree<T extends java.lang.Comparable>

java.lang.Object
  extended by algs.model.tree.BinaryTree<T>
Type Parameters:
T - the base type of the values stored by the BinaryTree. Must be Comparable.
All Implemented Interfaces:
java.lang.Iterable<T>

public class BinaryTree<T extends java.lang.Comparable>
extends java.lang.Object
implements java.lang.Iterable<T>

Standard unbalanced binary tree. Duplicates are allowed. The right child of a node in the tree is guaranteed to have its value be greater than or equal to its parent.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Constructor Summary
BinaryTree()
          Default BinaryTree constructor.
 
Method Summary
 BinaryNode<T> getRoot()
          Expose the root of the tree.
 java.util.Iterator<T> inorder()
          Use in-order traversal over the tree.
 void insert(T value)
          Insert the value into its proper location in the Binary tree.
 java.util.Iterator<T> iterator()
          Provide useful in-order iteration over the values of the Binary Tree.
 boolean member(T value)
          Determine if the given value occurs in the tree
 java.util.Iterator<T> postorder()
          Use post-order traversal over the tree.
 java.util.Iterator<T> preorder()
          Use pre-order traversal over the tree.
 boolean remove(T value)
          Remove the value from the tree.
protected  void setRoot(BinaryNode<T> newRoot)
          Helper method to properly set the root for the tree.
 java.lang.String toString()
          Create string representation of the Tree.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

BinaryTree

public BinaryTree()
Default BinaryTree constructor.

Method Detail

setRoot

protected void setRoot(BinaryNode<T> newRoot)
Helper method to properly set the root for the tree.

Parameters:
newRoot -

getRoot

public BinaryNode<T> getRoot()
Expose the root of the tree.


member

public boolean member(T value)
Determine if the given value occurs in the tree

Parameters:
value - non-null desired value to search for
Returns:
true if the value is stored in the Binary Tree
Throws:
java.lang.IllegalArgumentException - if value is null
java.lang.ClassCastException - if the specified object's type prevents it from being compared to this object.

remove

public boolean remove(T value)
Remove the value from the tree.

Parameters:
value - non-null value to be removed
Returns:
true if the value existed and was removed; otherwise return false
Throws:
java.lang.IllegalArgumentException - if value is null
java.lang.ClassCastException - if the specified object's type prevents it from being compared to this object.

insert

public void insert(T value)
Insert the value into its proper location in the Binary tree. No balancing is performed.

Parameters:
value - non-null value to be added into the tree.
Throws:
java.lang.IllegalArgumentException - if value is null
java.lang.ClassCastException - if the specified object's type prevents it from being compared to this object.

toString

public java.lang.String toString()
Create string representation of the Tree. Really only useful for debugging and testCase validation.

Overrides:
toString in class java.lang.Object

inorder

public java.util.Iterator<T> inorder()
Use in-order traversal over the tree.


preorder

public java.util.Iterator<T> preorder()
Use pre-order traversal over the tree.


postorder

public java.util.Iterator<T> postorder()
Use post-order traversal over the tree.


iterator

public java.util.Iterator<T> iterator()
Provide useful in-order iteration over the values of the Binary Tree.

Specified by:
iterator in interface java.lang.Iterable<T extends java.lang.Comparable>

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.