TreeTest.java Builds a binary tree and prints the contents of the nodes. Uses the following classes:

Treetest.java
/** A NodeOperator that prints each node.
 *
 *  Taken from Core Web Programming from
 *  Prentice Hall and Sun Microsystems Press,
 *  .
 *  © 2001 Marty Hall and Larry Brown;
 *  may be freely used or adapted.
 */

class PrintOperator implements NodeOperator {
  public void operateOn(Node node) {
    System.out.println(node.getNodeValue());
  }
}

/** A sample tree representing a parse tree of
 *  the sentence "Java hackers hack Java", using
 *  some simple context-free grammar.
 */

public class TreeTest {
  public static void main(String[] args) {
    Node adjective =
      new Node("  Adjective", new Leaf("   Java"));
    Node noun1 =
      new Node("  Noun", new Leaf("   hackers"));
    Node verb =
      new Node("  TransitiveVerb", new Leaf("   hack"));
    Node noun2 =
      new Node("  Noun", new Leaf("   Java"));
    Node np = new Node(" NounPhrase", adjective, noun1);
    Node vp = new Node(" VerbPhrase", verb, noun2);
    Node sentence = new Node("Sentence", np, vp);
    PrintOperator printOp = new PrintOperator();
    System.out.println("Depth first traversal:");
    sentence.depthFirstSearch(printOp);
    System.out.println("\nBreadth first traversal:");
    sentence.breadthFirstSearch(printOp);
  }
}

Leaf.java
A leaf node with no children.
/** Leaf node: a node with no subtrees.
 *
 *  Taken from Core Web Programming from
 *  Prentice Hall and Sun Microsystems Press,
 *  .
 *  © 2001 Marty Hall and Larry Brown;
 *  may be freely used or adapted.
 */

public class Leaf extends Node {
  public Leaf(Object value) {
    super(value, null, null);
  }
}

Node.java A data structure representing a node in a binary tree. 


import java.util.Vector;

/** A data structure representing a node in a binary tree.
 *  It contains a node value and a reference (pointer) to
 *  the left and right subtrees.
 *
 *  Taken from Core Web Programming from
 *  Prentice Hall and Sun Microsystems Press,
 *  .
 *  © 2001 Marty Hall and Larry Brown;
 *  may be freely used or adapted.
 */

public class Node {
  private Object nodeValue;
  private Node leftChild, rightChild;

 /** Build Node with specified value and subtrees. */

  public Node(Object nodeValue, Node leftChild,
              Node rightChild) {
    this.nodeValue = nodeValue;
    this.leftChild = leftChild;
    this.rightChild = rightChild;
  }

  /** Build Node with specified value and L subtree. R child
   *  will be null. If you want both children to be null, use
   *  the Leaf constructor.
   */

  public Node(Object nodeValue, Node leftChild) {
    this(nodeValue, leftChild, null);
  }

  /** Return the value of this node. */

  public Object getNodeValue() {
    return(nodeValue);
  }

  /** Specify the value of this node. */

  public void setNodeValue(Object nodeValue) {
    this.nodeValue = nodeValue;
  }

 /** Return the L subtree. */

  public Node getLeftChild() {
    return(leftChild);
  }

  /** Specify the L subtree. */

  public void setLeftChild(Node leftChild) {
    this.leftChild = leftChild;
  }

  /** Return the R subtree. */

  public Node getRightChild() {
    return(rightChild);
  }

  /** Specify the R subtree. */

  public void setRightChild(Node rightChild) {
    this.rightChild = rightChild;
  }

  /** Traverse the tree in depth-first order, applying
   *  the specified operation to each node along the way.
   */

  public void depthFirstSearch(NodeOperator op) {
    op.operateOn(this);
    if (leftChild != null) {
      leftChild.depthFirstSearch(op);
    }
    if (rightChild != null) {
      rightChild.depthFirstSearch(op);
    }
  }

  /** Traverse the tree in breadth-first order, applying the
   *  specified operation to each node along the way.
   */

  public void breadthFirstSearch(NodeOperator op) {
    Vector nodeQueue = new Vector();
    nodeQueue.addElement(this);
    Node node;
    while(!nodeQueue.isEmpty()) {
      node = (Node)nodeQueue.elementAt(0);
      nodeQueue.removeElementAt(0);
      op.operateOn(node);
      if (node.getLeftChild() != null) {
        nodeQueue.addElement(node.getLeftChild());
      }
      if (node.getRightChild() != null) {
        nodeQueue.addElement(node.getRightChild());
      }
    }
  }
}

NodeOperator.java An interface used in the Node class to ensure that an object has an operateOn method. 

/** An interface used in the Node class to ensure that
 *  an object has an operateOn method.
 *
 *  Taken from Core Web Programming from
 *  Prentice Hall and Sun Microsystems Press,
 *  .
 *  © 2001 Marty Hall and Larry Brown;
 *  may be freely used or adapted.
 */

public interface NodeOperator {
  void operateOn(Node node);
}