BinaryTree.
* Employ a dummy item rather than a null reference since it make
* many of the algorithms a easier.
*
* NB root.left refers to the tree of data itself.
*/ // Can't make this variable final as it is altered in clone. protected /*final*/ Node root = new Node (null, null, null, null) ; /** * TheNode of an AbstractBinaryTree.
* This may well be subclassed in subclasses of
* AbstractBinaryTree.
*
* Nodes know who their parent is as well as who
* their children are in order to make editing and traversal
* easier. Clearly not all binary trees need a parent reference,
* traditionally trees and tree algorithms have had only
* uni-directional references from parent to children. However,
* such trees only really support applicators (via recursive
* procedures) and not iterators. Since ADS is iterator oriented,
* we need to properly support iterators. Therefore, the links in
* the tree are made bi-directional by having a reference between
* child and parent.
Node.
*/
protected Object datum ;
/**
* The left sub-tree of this Node.
*/
protected Node left ;
/**
* The right sub-tree of this Node.
*/
protected Node right ;
/**
* The parent of this Node.
*/
protected Node parent ;
/**
* Constructor of a Node.
*/
public Node (final Object o,
final Node l,
final Node r,
final Node p) {
datum = o ;
left = l ;
right = r ;
parent = p ;
}
/**
* Remove ourself from the tree.
*/
protected void remove() {
final Node newThis = mergeChildren() ;
if (newThis != null) {
newThis.parent = parent ;
}
if (parent.left == this) {
parent.left = newThis ;
} else if (parent.right == this) {
parent.right = newThis ;
} else
throw new InvalidOperationException () ;
}
/**
* Support method for the tree editing. Usual algorithm: If
* there is only one sub-tree then deliver it up. If there are
* two sub-trees but the right sub-tree has no left sub-tree,
* link the left sub-tree as the left child of the right sub-tree
* and deliver it up. Otherwise find the left-most node of the
* right sub-tree and cut it out to replace the current node.
*/
private final Node mergeChildren() {
if (left == null)
return right ;
if (right == null)
return left ;
if (right.left == null) {
right.left = left ;
left.parent = right ;
return right ;
}
Node newRootParent = right ;
Node newRoot = newRootParent.left ;
while (newRoot.left != null) {
newRootParent = newRoot ;
newRoot = newRoot.left ;
}
newRootParent.left = newRoot.right ;
if (newRoot.right != null) {
newRoot.right.parent = newRootParent ;
}
newRoot.right = right ;
newRoot.left = left ;
left.parent = newRoot ;
right.parent = newRoot ;
return newRoot ;
}
/**
* Cloning means copying not just this item but both sub-trees
* rooted here. This is a shallow copy in the sense that
* although new Nodes are created the data items are
* not cloned.
*/
protected Object clone() {
// In supporting the OrderedBinaryTree we need to provide a
// parent for the first Node in the tree. There are two
// options to implementing clone in this circumstance, make the
// parent attribute accessible to OrderedBinaryTree or provide
// a clone method that takes a parameter. For safety's sake we
// do the latter. This means we can implement clone without a
// parameter as a delegated call to this other clone method
// with a parent of null.
return clone(null) ;
}
/**
* Cloning means copying not just this item but both sub-trees
* rooted here. This is a shallow copy in the sense that
* although new Nodes are created the data items are
* not cloned.
*/
protected Object clone(final Node parent) {
try {
Node n = (Node)super.clone() ;
n.parent = parent ;
if (left != null){
n.left = (Node)left.clone(n) ;
}
if (right != null) {
n.right = (Node)right.clone(n) ;
}
return n ;
} catch (CloneNotSupportedException e) {
throw new InternalError () ;
}
}
/**
* Print out the tree on the standard output.. This method was
* used during debugging and it not really part of the API for
* this class. Leave it in since it doesn't hurt and it may
* again prove useful.
*/
protected void printTree(final int level) {
if (right != null) right.printTree(level + 1) ;
for (int i = 0 ; i <= level ; ++i) System.out.print("\t") ;
System.out.println(datum) ;
if (left != null) left.printTree(level + 1) ;
}
}
/**
* Disconnect the tree of Nodes to make the tree and
* empty one.
*/
public void makeEmpty() {
root.left = null ;
}
/**
* Check the BinaryTree for emptiness.
*/
public boolean isEmpty() {
return root.left == null ;
}
/**
* Equality means equality of the values in this
* BinaryTree.
*/
public boolean equals(final Object o) {
if ((o == null) || ! (o instanceof BinaryTree))
return false ;
return super.equals(o) ;
}
//
// There are a number of different ways of traversing a BinaryTree,
// provide an Iterator for each of them. Initial inspiration for
// these algorithms from the the C++ code to be found in:
//
// Budd T (1998) Data Structures in C++: Using the Standard
// Template Library , Addison Wesley.
/**
* Deliver an iterator over the elements contained in the
* BinaryTree. Provides in-order traversal.
*/
public Iterator iterator() {
return inorderTraversal() ;
}
/**
* The basic iterator template for post-order, pre-order and
* in-order traversals. This is an abstract class defining the
* common elements. The parameter is the queueing method.
*/
protected abstract class AbstractIterator implements Iterator {
/**
* The item to be delivered up by the iterator.
*/
protected Node theItem = root.left ;
/**
* Deliver up the current item in the iteration.
*/
public Object get() {
if (atEnd())
throw new InvalidIteratorException () ;
return theItem.datum ;
}
/**
* Move the iterator on one.
*/
public abstract void advance() ;
/**
* Move the iterator on n.
*/
public void advance(int increment) {
for ( ; increment > 0 ; --increment) {
if (atEnd())
break ;
advance() ;
}
}
/**
* Determine whether we are positioned at the beginning of the
* tree.
*/
public boolean atBegin() {
return isEmpty() || theItem == root.left ;
}
/**
* Determine whether we have iterated over all the elements.
* This is when we have arrived back at the dummy root node since
* this is when we have been around all elements.
*/
public boolean atEnd() {
return isEmpty() || theItem == root ;
}
/**
* Are two iterators equal, i.e. do two iterators refer to the
* same item in the same data structure.
*/
public abstract boolean equals(final ADS.Iterator i) ;
/**
* Return a reference to the Container of this
* Iterator.
*/
public Container getContainer() {
return AbstractBinaryTree.this ;
}
/**
* Clone this Iterator.
*/
public Object clone() {
try {
return super.clone() ;
} catch (CloneNotSupportedException e) {
throw new InternalError () ;
}
}
}
/**
* Post-order traversal iterator. Post-order traversal of the
* BinaryTree visits the nodes in the order: left
* child, right child, current node.
*/
public final Iterator postorderTraversal() {
class PostOrderIterator extends AbstractIterator {
public PostOrderIterator() {
slideLeftGoRightRepeatedly() ;
}
public void advance() {
Node child = theItem ;
theItem = theItem.parent ;
if ((theItem != null) && !atEnd() &&
(theItem.right != null) &&
(theItem.right != child)) {
theItem = theItem.right ;
slideLeftGoRightRepeatedly() ;
}
}
public boolean equals(final ADS.Iterator i) {
if (!(i instanceof PostOrderIterator))
return false ;
return theItem == ((PostOrderIterator)i).theItem ;
}
private void slideLeftGoRightRepeatedly() {
while ((theItem != null) &&
((theItem.left != null) || (theItem.right != null))) {
while ((theItem != null) && (theItem.left != null)) {
theItem = theItem.left ;
}
if ((theItem != null) && (theItem.right != null)) {
theItem = theItem.right ;
}
}
}
}
return new PostOrderIterator () ;
}
/**
* Pre-order traversal iterator. Preorder traversal means visit
* nodes in the order: current node, left child, right child.
*/
public final Iterator preorderTraversal() {
class PreOrderIterator extends AbstractIterator {
public void advance() {
if (theItem.left != null) {
theItem = theItem.left ;
} else if (theItem.right != null) {
theItem = theItem.right ;
} else {
Node child = theItem ;
theItem = theItem.parent ;
while ((theItem != null) && !atEnd() &&
((theItem.right == child) ||
(theItem.right == null))) {
child = theItem ;
theItem = theItem.parent ;
}
if ((theItem != null) && !atEnd() &&
(theItem.right != null)) {
theItem = theItem.right ;
}
}
}
public boolean equals(final ADS.Iterator i) {
if (!(i instanceof PreOrderIterator))
return false ;
return theItem == ((PreOrderIterator)i).theItem ;
}
}
return new PreOrderIterator () ;
}
/**
* In-order traversal iterator. In-order traversal visits the
* nodes in the order: left child, current node, right child.
*/
public final Iterator inorderTraversal() {
class InOrderIterator extends AbstractIterator {
public InOrderIterator() {
while ((theItem != null) && (theItem.left != null)) {
theItem = theItem.left ;
}
}
public void advance() {
if (theItem.right != null) {
theItem = theItem.right ;
while ((theItem != null) && (theItem.left != null)) {
theItem = theItem.left ;
}
} else {
Node child = theItem ;
theItem = theItem.parent ;
while ((theItem != null) && !atEnd() &&
(theItem.right == child)) {
child = theItem ;
theItem = theItem.parent ;
}
}
}
public boolean equals(final ADS.Iterator i) {
if (!(i instanceof InOrderIterator))
return false ;
return theItem == ((InOrderIterator)i).theItem ;
}
}
return new InOrderIterator () ;
}
/**
* Level-order traversal iterator. Level-order traversal visits the
* nodes left-to-right, level-by-level. It is a breadth-first
* traversal rather than the depth-first traversal that the other
* basically are. For this reason we need the support of a queue.
*/
public final Iterator levelorderTraversal() {
class LevelOrderIterator extends AbstractIterator {
protected Queue itemQueue = new SLListQueue () ; {
theItem = root.left ;
if (theItem != null) {
if (theItem.left != null) {
itemQueue.add(theItem.left) ;
}
if (theItem.right != null) {
itemQueue.add(theItem.right) ;
}
}
}
public void advance() {
if (itemQueue.isEmpty()){
theItem = root ;
} else {
theItem = ((Node)itemQueue.remove()) ;
if (theItem != null) {
if (theItem.left != null) {
itemQueue.add(theItem.left) ;
}
if (theItem.right != null) {
itemQueue.add(theItem.right) ;
}
}
}
}
public boolean equals(final ADS.Iterator i) {
if (!(i instanceof LevelOrderIterator))
return false ;
// TODO: Determine whether we should test the Queues for
// equality as well.
return theItem == ((LevelOrderIterator)i).theItem ;
}
}
return new LevelOrderIterator () ;
}
/**
* The method to find a particular node in the tree. Each binary
* tree has to provide a mechanism for searching to allow the
* O(log(n)) searching behaviour to be accessed. If this mechanism
* is not made available then all searching is linear since only
* the traversal iterators are available. Unlike the other four
* iterators, this one is intended only for internal purposes since
* it has to provide access to the internal representation.
*/
protected abstract Iterator searchFor(Object o) ;
/**
* There are time during debugging when you have to print the tree
* out to see what is going on. Don't really need it after the
* class is built but leave it here just in case.
*/
public void printTree() {
if (isEmpty()) {
System.out.println("Tree is empty.") ;
} else {
root.left.printTree(0) ;
}
}
}