Algorithm
Development Kit 1.0

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

java.lang.Object
  extended by algs.model.tree.RightThreadedBinaryTree<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 RightThreadedBinaryTree<T extends java.lang.Comparable>
extends java.lang.Object
implements java.lang.Iterable<T>

Unbalanced right-threaded 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. There is an artificial 'root' node whose left child is the real root of the tree. The reason for this artificial node is to simplify the algorithm and to enable the right-most node of the tree to have something to point to!

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

Constructor Summary
RightThreadedBinaryTree()
          Default BinaryTree constructor.
 
Method Summary
 void accept(IVisitor visitor)
          Accept a visitor for a inorder traversal.
 RightThreadedBinaryNode<T> getRoot()
          Return 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(RightThreadedBinaryNode<T> newRoot)
          Helper method to properly set the root for the tree.
 java.lang.String toString()
          Create string representation of the Tree.
 boolean validateArtificialRoot()
          Placed here for the purpose of testing.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

RightThreadedBinaryTree

public RightThreadedBinaryTree()
Default BinaryTree constructor.

Method Detail

setRoot

protected void setRoot(RightThreadedBinaryNode<T> newRoot)
Helper method to properly set the root for the tree. Note that setting the root properly links the node into the artificial root node.

Parameters:
newRoot -

getRoot

public RightThreadedBinaryNode<T> getRoot()
Return the root of the tree.


member

public boolean member(T value)
Determine if the given value occurs in the tree. Identical to BinaryTree::member(T) since searching in a ThreadedTree is identical.

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. The key is to find the predecessor-value (pv) to the target-value (tv). You can set the value of 'tv' to be 'pv' and then delete the original 'pv' node by considering the following two cases (note that the original pv node cannot have a right child because it is the predecessor to tv). The two cases are: 1. If pv has no children just delete it 2. If pv has a left child, then have pv's parent's right child become the left child of pv. Must properly manage deletions

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

accept

public void accept(IVisitor visitor)
Accept a visitor for a inorder traversal.


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>

validateArtificialRoot

public boolean validateArtificialRoot()
Placed here for the purpose of testing.


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.