Class TreeIterator<K extends java.lang.Comparable<? super K>,V>

java.lang.Object

TreeIterator<K,V>

Type Parameters:

K - This is the type of the Key being used by the BinarySearchTree to position TreeItems in the tree

V - This is the type of the Value associated with the Key

All Implemented Interfaces:

java.util.Iterator<TreeItem<K,V>>

public class TreeIterator<K extends java.lang.Comparable<? super K>,V>
extends java.lang.Object
implements java.util.Iterator<TreeItem<K,V>>

The TreeIterator allows a user of a BinarySearchTree to iterate through the TreeItems currently in the tree in one of the following Key orders:

1. preOrder
2. inOrder
3. postOrder

Users will set the desired order and access the TreeItems using the Iterator interface.

Author:

Sameh Fakhouri

Field Summary

Fields

Modifier and Type	Field and Description
private BinarySearchTree<K,V>	bst
private java.util.Vector<TreeNode<K,V>>	treeNodes

Constructor Summary

Constructors

Constructor and Description
TreeIterator(BinarySearchTree<K,V> binarySearchTree) This is the constructor for the TreeIterator.

Method Summary

Modifier and Type	Method and Description
boolean	hasNext() This method is used to verify that the TreeIterator has more elements to return.
private void	inorder(TreeNode<K,V> treeNode) A recursive method that traverses the binary search tree rooted at the specified treeNode in in-order, adding the visited nodes to the treeNodes Vector.
boolean	isEmpty() This method is used to check if the iterator is empty.
TreeItem<K,V>	next() This method is used to retrieve the next element from the TreeIterator.
private void	postorder(TreeNode<K,V> treeNode) A recursive method that traverses the binary search tree rooted at the specified treeNode in post-order, adding the visited nodes to the treeNodes Vector.
private void	preorder(TreeNode<K,V> treeNode) A recursive method that traverses the binary search tree rooted at the specified treeNode in pre-order, adding the visited nodes to the treeNodes Vector.
void	setInorder() This method sets the order of retrieval from the TreeIterator to be Inorder.
void	setPostorder() This method sets the order of retrieval from the TreeIterator to be Postorder.
void	setPreorder() This method sets the order of retrieval from the TreeIterator to be Preorder.
int	size() This method is used to obtain the number of elements available in the iterator.

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Iterator

forEachRemaining, remove

Field Detail

bst

private BinarySearchTree<K extends java.lang.Comparable<? super K>,V> bst

treeNodes

private java.util.Vector<TreeNode<K extends java.lang.Comparable<? super K>,V>> treeNodes

Constructor Detail

TreeIterator

public TreeIterator(BinarySearchTree<K,V> binarySearchTree)

This is the constructor for the TreeIterator.

Parameters:

binarySearchTree - The BinaryTreeBasis that this iterator will operate on.

Method Detail

size

public int size()

This method is used to obtain the number of elements available in the iterator.

Returns:

Returns the number of TreeNode's available in the iterator.

isEmpty

public boolean isEmpty()

This method is used to check if the iterator is empty.

Returns:

Returns true if the iterator is emtpy, false otherwise.

hasNext

public boolean hasNext()

This method is used to verify that the TreeIterator has more elements to return.

Specified by:

hasNext in interface java.util.Iterator<TreeItem<K extends java.lang.Comparable<? super K>,V>>

Returns:

Returns true if there are more elements to return, false otherwise.

next

public TreeItem<K,V> next()
                   throws java.util.NoSuchElementException

This method is used to retrieve the next element from the TreeIterator.

Specified by:

next in interface java.util.Iterator<TreeItem<K extends java.lang.Comparable<? super K>,V>>

Returns:

Returns the next element from the TreeIterator.

Throws:

java.util.NoSuchElementException

setPreorder

public void setPreorder()

This method sets the order of retrieval from the TreeIterator to be Preorder. This method will call the private method preorder() in order to populate the queue.

setInorder

public void setInorder()

This method sets the order of retrieval from the TreeIterator to be Inorder. This method will call the private method inorder() in order to populate the queue.

setPostorder

public void setPostorder()

This method sets the order of retrieval from the TreeIterator to be Postorder. This method will call the private method postorder() in order to populate the queue.

preorder

private void preorder(TreeNode<K,V> treeNode)

A recursive method that traverses the binary search tree rooted at the specified treeNode in pre-order, adding the visited nodes to the treeNodes Vector.

Parameters:

treeNode - The node specifying the root of the binary search tree being traversed.

inorder

private void inorder(TreeNode<K,V> treeNode)

A recursive method that traverses the binary search tree rooted at the specified treeNode in in-order, adding the visited nodes to the treeNodes Vector.

Parameters:

treeNode - The node specifying the root of the binary search tree being traversed.

postorder

private void postorder(TreeNode<K,V> treeNode)

A recursive method that traverses the binary search tree rooted at the specified treeNode in post-order, adding the visited nodes to the treeNodes Vector.

Parameters:

treeNode - The node specifying the root of the binary search tree being traversed.