PRE_ORDER, IN_ORDER,
* POST_ORDER, or EULER_TOUR,
* possibly combined using the + operator
* (e.g. PRE_ORDER + POST_ORDER). Note however, that
* EULER_TOUR != PRE_ORDER + IN_ORDER + POST_ORDER,
* since it visits leafs only once (in a traversal order specified
* by the right hand side each leaf is returned three times when applied to
* InspectableBinaryTree and two times when applied to
* InspectableTree).
*
* The class implements the PositionIterator-Interface
* and iterates over the positions present in the tree at the time
* it is passed to the constructor. The class requires space linear
* in the size of the tree, construction takes time lineat in the size
* size of the tree, and advancing the iterator takes constant time.
*
* Construction is performed using the template method pattern.
* Several (empty) methods can be overriden to carry out additional
* computations during the traversal.
*
* @author Ulrik Brandes
* @version 1.0, 08/14/99
* @see jdsl.core.ref.PreOrderIterator
* @see jdsl.core.ref.InOrderIterator
* @see jdsl.core.ref.PostOrderIterator
* @see jdsl.core.algo.traversals.EulerTour
**/
public class TreeTraversal implements PositionIterator {
// for the convenience of specifiying, e.g., PRE_ORDER + POST_ORDER
public static final int PRE_ORDER = 1;
public static final int IN_ORDER = 2;
public static final int POST_ORDER = 4;
public static final int EULER_TOUR = 8 + PRE_ORDER + IN_ORDER + POST_ORDER;
protected InspectableTree tree_ = null;
protected boolean preorder_ = false;
protected boolean inorder_ = false;
protected boolean postorder_ = false;
protected boolean eulertour_ = false;
protected boolean traversing_ = false;
protected Position[] traversedPositions_ = null;
protected int currentIndex_ = -1;
protected int lastIndex_ = -1;
/**
* Constructor generating a sequence of positions to iterate over,
* starting with the root.
* The order is specified using class constants PRE_ORDER, etc.
* Template hooks firstVisit(Position), etc.
* are called during construction.
**/
public TreeTraversal(InspectableTree tree, int traversal)
{ this(tree, traversal, tree.root()); }
/**
* Constructor generating a sequence of positions to iterate over,
* starting with the specified node and traversing only its subtree.
* The order is specified using class constants PRE_ORDER, etc.
* Template hooks firstVisit(Position), etc.
* are called during construction.
*
* @exception InvalidAccessorException
* if the specified node is not contained in the specified tree
**/
public TreeTraversal(InspectableTree tree, int traversal, Position root)
throws InvalidAccessorException
{
if(!tree.contains(root))
throw new InvalidAccessorException("Initial position not in tree.");
tree_ = tree;
preorder_ = ((traversal & PRE_ORDER) == PRE_ORDER);
inorder_ = ((traversal & IN_ORDER) == IN_ORDER);
postorder_ = ((traversal & POST_ORDER) == POST_ORDER);
eulertour_ = ((traversal & EULER_TOUR) == EULER_TOUR);
if(!(preorder_ || inorder_ || postorder_))
currentIndex_ = 0; // -> fail immediately (currentIndex_ > lastIndex_ )
else {
/* The following seems inefficient,
* yet NodeTree.size() is O(n) anyway.
* A different implementation could use a sequence instead of the array
* to store traversed positions, or drop snapshot semantics
* to advance only when nextPosition() is called,
* and thus not store positions at all.
*/
traverse(root); // once for counting [size() is O(n) anyway]
lastIndex_ = currentIndex_;
traversedPositions_ = new Position[lastIndex_ + 1];
reset();
init(tree_);
traversing_ = true;
traverse(root); // now for real
finished(tree_);
reset();
}
}
// -------------------------------- hooks for customization via subclassing
/**
* Empty method called from within the constructor
* before traversing the (sub)tree
* (override for customized behavior).
*
* @param tree the traversed tree
**/
protected void init(InspectableTree tree) {}
/**
* Empty method called from within the constructor
* when a node is visited for the first time
* (override for customized behavior).
*
* @param node the node visited
**/
protected void firstVisit(Position node) {}
/**
* Empty method called from within the constructor
* when a node is visited for at least the second, but not the last time
* (override for customized behavior).
*
* @param node the node visited
* @param count number of times it has been visited minus one
* (1: first intermediate visit, 2: second intermediate visit, ...)
**/
protected void intermediateVisit(Position node, int count) {}
/**
* Empty method called from within the constructor
* when a node is visited for the last time
* (override for customized behavior).
*
* @param node the node visited
**/
protected void lastVisit(Position node) {}
/**
* Called by the constructor after traversal is completed
* (override for customized behavior).
*
* @param tree the traversed tree
**/
protected void finished(InspectableTree tree) {}
// ------------------------------- the actual traversal
// either just count the node or also store it for the iterator
private void register(Position node) {
currentIndex_++;
if(traversing_)
traversedPositions_[currentIndex_] = node;
}
private void traverse(Position node) {
if(traversing_) firstVisit(node);
if(tree_.isExternal(node)) {
if(eulertour_)
register(node);
else {
if(preorder_) register(node);
if(inorder_ && tree_ instanceof InspectableBinaryTree) register(node);
if(postorder_) register(node);
}
} else {
if(preorder_) register(node);
if(tree_ instanceof InspectableBinaryTree) {
// JDSL binary tree non-leafs always have two children
traverse(((InspectableBinaryTree)tree_).leftChild(node));
if(inorder_) register(node);
if(traversing_) intermediateVisit(node, 1);
traverse(((InspectableBinaryTree)tree_).rightChild(node));
} else {
int intermediates = 0;
PositionIterator children = tree_.children(node);
while(children.hasNext()) {
traverse(children.nextPosition());
if(children.hasNext() && inorder_) {
register(node);
if(traversing_) intermediateVisit(node, ++intermediates);
}
}
}
if(postorder_) register(node);
}
if(traversing_) lastVisit(node);
}
// -------------------------------- implement interface of PositionIterator
public void reset() { currentIndex_ = -1; }
public boolean hasNext() { return (currentIndex_ < lastIndex_); }
public Object nextObject() { return nextPosition(); }
public Accessor nextAccessor() { return nextPosition(); }
public Position nextPosition() {
if(hasNext())
return traversedPositions_[++currentIndex_];
else
throw new NoSuchElementException("Traversal is already finished.");
}
public Object object() throws NoSuchElementException { return position(); }
public Accessor accessor() throws NoSuchElementException { return position(); }
public Position position() throws NoSuchElementException {
checkValid();
return traversedPositions_[currentIndex_];
}
public Object element() throws NoSuchElementException {
checkValid();
return traversedPositions_[currentIndex_].element();
}
// make sure position() and element() have something to report
private void checkValid() throws NoSuchElementException {
if(currentIndex_ < 0)
throw new NoSuchElementException("Traversal iterator has not yet been advanced for the first time.");
// the following shouldn't happen, because we advance only when more positions are present
if(currentIndex_ >= lastIndex_)
throw new NoSuchElementException("Iterator beyond traversed postions. Internal error, please report.");
}
// -------------------------------- static bonus methods for single steps
/**
* Determines whether a node is a rightmost child.
*
* @return true if and only if the node has a parent
* and is its rightmost child
**/
private static boolean rightmost(InspectableTree T, Position node) {
return !T.isRoot(node) && (node == T.lastChild(T.parent(node)));
}
/**
* Returns the successor of the second argument in a pre-order traversal of the tree.
**/
public static Position preOrderNext(InspectableTree T, Position node) {
if(!T.contains(node))
throw new InvalidAccessorException("Node " + node + " is not contained in tree "+ T);
if(T.isInternal(node))
return T.firstChild(node);
else {
Position next = node;
while(rightmost(T, next)) next = T.parent(next);
return (T.isRoot(next)) ? next : T.siblingAfter(next);
}
}
/**
* Returns the successor of the second argument
* in a in-order traversal of the tree.
* Note that this method applies only to InspectableBinaryTrees.
**/
public static Position inOrderNext(InspectableBinaryTree T, Position node) {
if(!T.contains(node))
throw new InvalidAccessorException("Node " + node + " is not contained in tree "+ T);
if(T.isExternal(node)) {
while(rightmost(T, node)) node = T.parent(node);
if(!T.isRoot(node)) {
node = T.parent(node);
return node;
}
} else
node = T.rightChild(node);
while(T.isInternal(node)) node = T.leftChild(node);
return node;
}
/**
* Returns the successor of the second argument
* in a post-order traversal of the tree.
**/
public static Position postOrderNext(InspectableTree T, Position node) {
if(!T.contains(node))
throw new InvalidAccessorException("Node " + node + " is not contained in tree "+ T);
if(rightmost(T, node))
return T.parent(node);
else {
Position next = (node == T.root()) ? node : T.siblingAfter(node);
while(T.isInternal(next)) next = T.firstChild(next);
return next;
}
}
private static void test(InspectableTree tree, int order, String orderStr) {
System.out.print("\n" + orderStr + ":\t");
PositionIterator nodes = new TreeTraversal(tree, order);
while(nodes.hasNext())
System.out.print(nodes.nextPosition().element() + " ");
System.out.println();
}
public static void main(String[] args) {
System.out.println("\nConstructing the following tree:\n");
System.out.println(" null");
System.out.println(" / \\");
System.out.println(" 1 2");
System.out.println(" / | \\ |");
System.out.println(" 3 4 5 6");
Tree tree = new NodeTree();
Position node = tree.insertFirstChild(tree.root(), new Integer(1));
tree.insertLastChild(node, new Integer(3));
tree.insertLastChild(node, new Integer(4));
tree.insertLastChild(node, new Integer(5));
node = tree.insertLastChild(tree.root(), new Integer(2));
tree.insertLastChild(node, new Integer(6));
test(tree, PRE_ORDER, "preorder");
System.out.print("\npre/steps:\t");
node = tree.root();
for(int i = 0; i < 7; i++)
System.out.print((node = preOrderNext(tree, node)).element() + " ");
System.out.println();
test(tree, IN_ORDER, "inorder");
test(tree, POST_ORDER, "postorder");
System.out.print("\npost/steps:\t");
node = tree.root();
for(int i = 0; i < 7; i++)
System.out.print((node = postOrderNext(tree, node)).element() + " ");
System.out.println();
test(tree, PRE_ORDER+IN_ORDER, "(pre+in)");
test(tree, IN_ORDER+POST_ORDER, "(in+post)");
test(tree, PRE_ORDER+POST_ORDER, "(pre+post)");
test(tree, PRE_ORDER+IN_ORDER+POST_ORDER, "(pre+in+post)");
test(tree, EULER_TOUR, "eulertour");
System.out.println("\nAnd now for a binary tree:\n");
System.out.println(" null");
System.out.println(" / \\");
System.out.println(" 1 2");
System.out.println(" / \\ / \\");
System.out.println(" 3 4 5 6");
BinaryTree binTree = new NodeBinaryTree();
binTree.expandExternal(binTree.root());
node = binTree.leftChild(binTree.root());
binTree.replaceElement(node, new Integer(1));
binTree.expandExternal(node);
binTree.replaceElement(binTree.leftChild(node), new Integer(3));
binTree.replaceElement(binTree.rightChild(node), new Integer(4));
node = binTree.rightChild(binTree.root());
binTree.replaceElement(node, new Integer(2));
binTree.expandExternal(node);
binTree.replaceElement(binTree.leftChild(node), new Integer(5));
binTree.replaceElement(binTree.rightChild(node), new Integer(6));
test(binTree, PRE_ORDER, "preorder");
test(binTree, IN_ORDER, "inorder");
System.out.print("\nin/steps:\t");
node = binTree.root();
for(int i = 0; i < 7; i++)
System.out.print((node = inOrderNext(binTree, node)).element() + " ");
System.out.println();
test(binTree, POST_ORDER, "postorder");
test(binTree, PRE_ORDER+IN_ORDER, "(pre+in)");
test(binTree, IN_ORDER+POST_ORDER, "(in+post)");
test(binTree, PRE_ORDER+POST_ORDER, "(pre+post)");
test(binTree, PRE_ORDER+IN_ORDER+POST_ORDER, "(pre+in+post)");
test(binTree, EULER_TOUR, "eulertour");
}
}