package jds.util;
import java.util.Enumeration;
import jds.Stack;
import jds.collection.Vector;
/**
* PreorderTreeTraversal - traverse a binary tree in preorder fashion;
* for use with book
* Classic Data Structures
* in Java
* by Timothy A Budd,
* published by Addison-Wesley, 2001.
*
* @author Timothy A. Budd
* @version 1.1 September 1999
* @version 1.2 November 2001 (fixed slideLeft error, nearly correct in book,
* but needs a guard on the recursive call)
*/
public class PostorderTreeTraversal implements Enumeration {
/**
* initialize a traversal rooted at given node
*
* @param root start of traversal
*/
public PostorderTreeTraversal (BinaryNode root)
{ slideLeft(root); }
private Stack stk = new Vector();
private void slideLeft (BinaryNode current) {
while (current != null) {
stk.addLast(current);
current = current.leftChild;
}
if (stk.isEmpty()) return;
current = (BinaryNode) stk.getLast();
if (current.rightChild != null)
slideLeft(current.rightChild);
}
/**
* see if enumeration has at least one more element
*/
public boolean hasMoreElements () { return ! stk.isEmpty(); }
/**
* return the next element in the enumeration
*
* @return the value of the current element
*/
public Object nextElement () {
BinaryNode current = (BinaryNode) stk.getLast();
stk.removeLast();
if (! stk.isEmpty()) {
BinaryNode parent = (BinaryNode) stk.getLast();
if (parent.rightChild != current)
slideLeft (parent.rightChild);
}
return current.value;
}
}