bst.java

从给定的字母矩阵中查找给定的字典所包含的字符串

import java.io.*;

/**
* This is a binary search tree.
* It is used to save the words found in the letter matrix
* and sort them in the right order.
*
* @author Ting Chen 0122070
* @version 1.0 2003/5/30
*/
public class BST 
{ 
  /** The root of the tree */
  private BinNode root;   

  /** Used to help printing out the nodes of the tree */
  private int count;

  /** The number of nodex in the tree */
  private int totalNumber;

  /** Used to print out the nodes of the tree */
  private PrintWriter out;  

  /**
  * The constructor for this class. <p>
  * It initializes root to null.
  * 
  */
  public BST() 
  { 
    root = null; totalNumber = 0;
  }     

   /**
  * Clear the tree. Throw the nodes away.
  * 
  */
  public void clear() 
  { 
    root = null; totalNumber = 0;
  }

  /**
  * Insert the val to the BST tree.
  * 
  * @param val The element to be inserted   
  */
  public void insert(String val) 
  { 
    root  = inserthelp(root, val); 
  }

  /**
  * look for the val in the BST tree.
  * 
  * @param val The element to be searched 
  */
  public String find(String key) 
  { 
    return findhelp(root, key); 
  }

  /**
  * Return true if the tree is empty.
  *   
  */
  public boolean isEmpty() 
  { 
    return root == null; 
  }
  

/** 
 * The private method for find. It does the recursive call
 * to look for the key in the child node of the root if it is
 * not contained in the root.
 *
 * @param rt The root node to be checked.
 * @param key The key val to be searched.
 */
private String findhelp(BinNode rt, String key) 
{
  if (rt == null) return null;
  String it = rt.element();

  if (it.compareTo(key) > 0)  return findhelp(rt.left(), key);

  else if (it.startsWith(key))  return it;

  else  return findhelp(rt.right(), key);
}

/** 
 * The private method for insert. It does the recursive call
 * to insert the val to the right position in the BST. 
 *
 * @param rt The root node to be checked.
 * @param val The key val to be inserted.
 */
private BinNode inserthelp(BinNode rt, String val) 
{
  if (rt == null) 
  {
  totalNumber++;
  return new BinNode(val);
  }
  String it = rt.element();
  if ( it.compareTo(val) > 0 )
  rt.setLeft(inserthelp(rt.left(), val));
  else
  rt.setRight(inserthelp(rt.right(), val));

  return rt;
}

/**
 * Return the number of nodes in the BST tree.
 *
 */
public int size()
{
  return totalNumber;
}

/**
 * Traverse the BST tree in the infix order and write the word visited
 * to the output file.
 *
 * @param rt The root of the subtree
 */
private void inorder(BinNode rt) 
{
  // Empty subtree
  if (rt == null) return; 
  inorder(rt.left());
    visit(rt);  
    inorder(rt.right());
}

/**
 * Out put the nodes in the lexdaisical order.
 *
 * @param rt The root of the subtree
 */
public void in ( String outFile ) throws IOException
{
  out = new PrintWriter( new FileWriter(outFile),true);
  count = 1;
  out.println("There are " + totalNumber + " words." );
  inorder(root);
}

/**
 * When visiting the node, out put the information of 
 * the word in this node.
 *
 * @param rt The visited node
 */
  private void visit(BinNode rt) 
  {
   out.println( count + ". " + rt.element()); 
   count++;
  }
}