1.txt

二叉树算法(java)

import java.util.Vector;

// This appears in Core Web Programming from
// Prentice Hall Publishers, and may be freely used
// or adapted. 1997 Marty Hall, [e-mail].

/** 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.
 */

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.
   *
   * @see Leaf
   */
  
  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());
    }
  }
}