Chapter 8: FrequencyList.java

//----------------------------------------------------------------------------
// FrequencyList.java            by Dale/Joyce/Weems                 Chapter 8
//
// Displays a word frequency list of the words listed in the input file.
// Prompts user for minSize and minFreq.
// Does not process words less than minSize in length.
// Does not output words unless their frequency is at least minFreq.
//----------------------------------------------------------------------------

import java.io.*;
import java.util.*;
import ch08.trees.*;
import ch08.wordFreqs.*;

public class FrequencyList
{
  public static void main(String[] args) throws IOException 
  {
    String word;
    WordFreq wordToTry;
    WordFreq wordInTree;
    WordFreq wordFromTree;

    BinarySearchTree tree = new BinarySearchTree();
    String skip;        // skip end of line after reading integer

    int numWords = 0;
    int numValidWords = 0;
    int numValidFreqs = 0;
    int minSize;
    int minFreq;
    int treeSize;

    // Set up file reading
    FileReader fin = new FileReader("words.dat");
    Scanner wordsIn = new Scanner(fin);
    wordsIn.useDelimiter("[^a-zA-Z0-9]");  // delimiters are nonletters-digits

    // Set up console reading
    Scanner conIn = new Scanner(System.in);

    //Get word and frequency limits from user
    System.out.print("Minimum word size: ");
    minSize = conIn.nextInt();
    skip = conIn.nextLine();      
    System.out.print("Minimum word frequency: ");
    minFreq = conIn.nextInt();
    skip = conIn.nextLine();      

    while (wordsIn.hasNext())      // while more words to process
    {
      word = wordsIn.next();          
      numWords++;
      if (word.length() >= minSize)
      {
        numValidWords++;
        word = word.toLowerCase();
        wordToTry = new WordFreq(word);
        wordInTree = tree.get(wordToTry);
        if (wordInTree == null)
        {
          // insert new word into tree
          wordToTry.inc();               // set frequency to 1
          tree.add(wordToTry);
        }
        else
        {
          // word already in tree, just increment frequency
          wordInTree.inc();
        }
      }
    }
  
    treeSize = tree.reset(BinarySearchTree.INORDER);
    System.out.println("The words of length " + minSize + " and above,");
    System.out.println("with frequency counts of " + minFreq + " and above:");
    System.out.println();
    System.out.println("Freq  Word");
    System.out.println("----- -----------------");
    for (int count = 1; count <= treeSize; count++)
    {
      wordFromTree = tree.getNext(BinarySearchTree.INORDER);
      if (wordFromTree.freqIs() >= minFreq)
      {
        numValidFreqs++;
        System.out.println(wordFromTree);
      }
    }

    System.out.println();  
    System.out.println(numWords + " words in the input file.  ");
    System.out.println(numValidWords + " of them are at least " + minSize + " characters.");
    System.out.println(numValidFreqs + " of these occur at least " + minFreq + " times.");
    System.out.println("Program completed.");
  } 
} 

Chapter 8: GolfApp2.java

//---------------------------------------------------------------------
// GolfApp2.java           by Dale/Joyce/Weems                Chapter 8
//
// Allows user to enter golfer name and score information.
// Displays information ordered by score.
//----------------------------------------------------------------------

import java.util.Scanner;
import ch08.trees.*;
import support.*;       // Golfer

public class GolfApp2 
{
  public static void main(String[] args)
  {
    Scanner conIn = new Scanner(System.in);

    String name;          // golfer's name
    int score;            // golfer's score
    
    BSTInterface golfers = new BinarySearchTree();
    Golfer golfer;
    int numGolfers;
    
    String skip;  // Used to skip rest of input line after reading integer

    System.out.print("Golfer name (press Enter to end): ");
    name = conIn.nextLine();
    while (!name.equals(""))
    {
      System.out.print("Score: ");
      score = conIn.nextInt();
      skip = conIn.nextLine();      
      
      golfer = new Golfer(name, score);
      golfers.add(golfer);
      
      System.out.print("Golfer name (press Enter to end): ");
      name = conIn.nextLine();
    }
    System.out.println();
    System.out.println("The final results are");

    numGolfers = golfers.reset(BinarySearchTree.INORDER);
    for (int count = 1; count <= numGolfers; count++)
    {
      System.out.println(golfers.getNext(BinarySearchTree.INORDER));
    }
  }
}

Chapter 8: ITDBinarySearchTree.java

//----------------------------------------------------------------------------
// ITDBinarySearchTree.java         by Dale/Joyce/Weems               Chapter 8
//
// Interactive Test Driver for the BinarySearchTree class
//----------------------------------------------------------------------------

import java.util.*;
import ch08.trees.*;

public class ITDBinarySearchTree
{
  public static void main(String[] args) 
  {
    Scanner conIn = new Scanner(System.in);

    String skip;       // skip end of line after reading an integer
    boolean keepGoing; // flag for "choose operation" loop
    int operation;     // user's choice of operation
	 int order;         // user's choice of traversal order

    String testName;
    BinarySearchTree tree = new BinarySearchTree();

    String element;
	 String target;
	 int treeSize;      
	 
    // Handle test name  
    System.out.println("What is the name of this test?");
    testName = conIn.nextLine();
    System.out.println("\nThis is test " + testName + ".");

    // Handle test cases
    keepGoing = true;  
    while (keepGoing)
    {
      System.out.println("\nChoose an operation:");
      System.out.println("1: isEmpty");
      System.out.println("2: size");
      System.out.println("3: size2");
	   System.out.println("4: contains (string)");
      System.out.println("5: remove (string)");
      System.out.println("6: get (string)");
      System.out.println("7: add (string)");
      System.out.println("8: print (traversal order)");
      System.out.println("9: stop Testing \n");
		System.out.print("Enter choice: ");
      if (conIn.hasNextInt())
        operation = conIn.nextInt();
      else
      {
        System.out.println("Error: you must enter an integer.");
        System.out.println("Terminating test.");
        return;
      } 
      skip = conIn.nextLine();
		
		switch (operation)
      {
        case 1:  // isEmpty
        System.out.println("isEmpty returns " + tree.isEmpty());
        break;
        
        case 2:  // size
        System.out.println("size returns " + tree.size());
        break;
        
        case 3:  // size2
        System.out.println("size2 returns " + tree.size2());
        break;
        
        case 4:  // contains
        System.out.print("Enter string to search for: ");
        target = conIn.nextLine();
        System.out.println("contains(" + target + ") returns " + tree.contains(target));
        break;
        
        case 5:  // remove
        System.out.print("Enter string to remove: ");
        target = conIn.nextLine();
        System.out.println("remove(" + target + ") returns " + tree.remove(target));
        break;
            
        case 6:  // get
        System.out.print("Enter string to get: ");
        target = conIn.nextLine();
        System.out.println("get(" + target + ") returns " + tree.get(target));
        break;
  
        case 7:  // add
        System.out.print("Enter string to add: ");
        element = conIn.nextLine();
        tree.add(element);
		  break;
  
        case 8:  // print tree
        System.out.println("Choose a traversal order:");
        System.out.println("1: Preorder");
        System.out.println("2: Inorder");
        System.out.println("3: Postorder");
        if (conIn.hasNextInt())
           order = conIn.nextInt();
        else
        {
          System.out.println("Error: you must enter an integer.");
          System.out.println("Terminating test.");
          return;
        }
        skip = conIn.nextLine();

        switch (order)
        {
          case 1:
          treeSize = tree.reset(BinarySearchTree.PREORDER);
          System.out.println("The tree in Preorder is:");
          for (int count = 1; count <= treeSize; count++)
          {
            element = (String) tree.getNext(BinarySearchTree.PREORDER);
            System.out.println(element);
          }
          break;
          
          case 2:
          treeSize = tree.reset(BinarySearchTree.INORDER);
          System.out.println("The tree in Inorder is:");
          for (int count = 1; count <= treeSize; count++)
          {
            element = (String) tree.getNext(BinarySearchTree.INORDER);
            System.out.println(element);
          }
          break;

          case 3:
          treeSize = tree.reset(BinarySearchTree.POSTORDER);
          System.out.println("The tree in Postorder is:");
          for (int count = 1; count <= treeSize; count++)
          {
            element = (String) tree.getNext(BinarySearchTree.POSTORDER);
            System.out.println(element);
          }
          break;

          default:
          System.out.println("Error in order choice. Terminating test.");
          return;
        }
        break;
		  
        case 9:  // stop testing
        keepGoing = false;
        break;
        
        default:
        System.out.println("Error in operation choice. Terminating test.");
        return;
      }
    }
  System.out.println("End of Interactive Test Driver");
  }
}

Chapter 8: tree1.out

Results Test Case for TextBook

The tree is instantiated
The number of nodes in the tree is 0
The (iterative) number of nodes in the tree is 0
The tree is empty is true
L was inserted into the tree
D was inserted into the tree
P was inserted into the tree
C was inserted into the tree
H was inserted into the tree
J was inserted into the tree
The number of nodes in the tree is 6
The (iterative) number of nodes in the tree is 6
J is on the tree: true
J was deleted from the tree
The tree in Inorder is:
1. C
2. D
3. H
4. L
5. P
The tree in Preorder is:
1. L
2. D
3. C
4. H
5. P

Chapter 8: /trees/ BinarySearchTree.java

//----------------------------------------------------------------------------
// BinarySearchTree.java          by Dale/Joyce/Weems                Chapter 8
//
// Defines all constructs for a reference-based BST
//----------------------------------------------------------------------------

package ch08.trees;

import ch05.queues.*;
import ch03.stacks.*;
import support.BSTNode;      

public class BinarySearchTree> 
             implements BSTInterface
{
  protected BSTNode root;      // reference to the root of this BST

  boolean found;   // used by remove
  
  // for traversals
  protected LinkedUnbndQueue inOrderQueue;    // queue of info
  protected LinkedUnbndQueue preOrderQueue;   // queue of info
  protected LinkedUnbndQueue postOrderQueue;  // queue of info

  public BinarySearchTree()
  // Creates an empty BST object.
  {
    root = null;
  }

  public boolean isEmpty()
  // Returns true if this BST is empty; otherwise, returns false.
  {
    return (root == null);
  }

  private int recSize(BSTNode tree)
  // Returns the number of elements in tree.
  {
    if (tree == null)    
      return 0;
    else
      return recSize(tree.getLeft()) + recSize(tree.getRight()) + 1;
  }

  public int size()
  // Returns the number of elements in this BST.
  {
    return recSize(root);
  }

  public int size2()
  // Returns the number of elements in this BST.
  {
    int count = 0;
    if (root != null)
    {
      LinkedStack> hold = new LinkedStack>();
      BSTNode currNode;
      hold.push(root);
      while (!hold.isEmpty())
      {
        currNode = hold.top();
        hold.pop();
        count++;
        if (currNode.getLeft() != null)
          hold.push(currNode.getLeft());
        if (currNode.getRight() != null)
          hold.push(currNode.getRight());
      }
    }
    return count;
  }

  private boolean recContains(T element, BSTNode tree)
  // Returns true if tree contains an element e such that 
  // e.compareTo(element) == 0; otherwise, returns false.
  {
    if (tree == null)
      return false;       // element is not found
    else if (element.compareTo(tree.getInfo()) < 0)
      return recContains(element, tree.getLeft());   // Search left subtree
    else if (element.compareTo(tree.getInfo()) > 0)
      return recContains(element, tree.getRight());  // Search right subtree
    else
      return true;        // element is found
  }

  public boolean contains (T element)
  // Returns true if this BST contains an element e such that 
  // e.compareTo(element) == 0; otherwise, returns false.
  {
    return recContains(element, root);
  }
  
  private T recGet(T element, BSTNode tree)
  // Returns an element e from tree such that e.compareTo(element) == 0;
  // if no such element exists, returns null.
  {
    if (tree == null)
      return null;             // element is not found
    else if (element.compareTo(tree.getInfo()) < 0)
      return recGet(element, tree.getLeft());          // get from left subtree
    else
    if (element.compareTo(tree.getInfo()) > 0)
      return recGet(element, tree.getRight());         // get from right subtree
    else
      return tree.getInfo();  // element is found
  }

  public T get(T element)
  // Returns an element e from this BST such that e.compareTo(element) == 0;
  // if no such element exists, returns null.
  {
    return recGet(element, root);
  }

  private BSTNode recAdd(T element, BSTNode tree)
  // Adds element to tree; tree retains its BST property.
  {
    if (tree == null)
      // Addition place found
      tree = new BSTNode(element);
    else if (element.compareTo(tree.getInfo()) <= 0)
      tree.setLeft(recAdd(element, tree.getLeft()));    // Add in left subtree
    else
      tree.setRight(recAdd(element, tree.getRight()));   // Add in right subtree
    return tree;
  }

  public void add (T element)
  // Adds element to this BST. The tree retains its BST property.
  {
    root = recAdd(element, root);
  }

  private T getPredecessor(BSTNode tree)
  // Returns the information held in the rightmost node in tree
  {
    while (tree.getRight() != null)
      tree = tree.getRight();
    return tree.getInfo();
  }

  private BSTNode removeNode(BSTNode tree)
  // Removes the information at the node referenced by tree.
  // The user's data in the node referenced by tree is no
  // longer in the tree.  If tree is a leaf node or has only
  // a non-null child pointer, the node pointed to by tree is
  // removed; otherwise, the user's data is replaced by its
  // logical predecessor and the predecessor's node is removed.
  {
    T data;

    if (tree.getLeft() == null)
      return tree.getRight();
    else if (tree.getRight() == null) 
      return tree.getLeft();
    else
    {
      data = getPredecessor(tree.getLeft());
      tree.setInfo(data);
      tree.setLeft(recRemove(data, tree.getLeft()));  
      return tree;
    }
  }

  private BSTNode recRemove(T element, BSTNode tree)
  // Removes an element e from tree such that e.compareTo(element) == 0
  // and returns true; if no such element exists, returns false. 
  {
    if (tree == null)
      found = false;
    else if (element.compareTo(tree.getInfo()) < 0)
      tree.setLeft(recRemove(element, tree.getLeft()));
    else if (element.compareTo(tree.getInfo()) > 0)
      tree.setRight(recRemove(element, tree.getRight()));
    else  
    {
      tree = removeNode(tree);
      found = true;
	 }
    return tree;
  }

  public boolean remove (T element)
  // Removes an element e from this BST such that e.compareTo(element) == 0
  // and returns true; if no such element exists, returns false. 
  {
    root = recRemove(element, root);
    return found;
  }

  private void inOrder(BSTNode tree)
  // Initializes inOrderQueue with tree elements in inOrder order.
  {
    if (tree != null)
    {
      inOrder(tree.getLeft());
      inOrderQueue.enqueue(tree.getInfo());
      inOrder(tree.getRight());
    }
  }

  private void preOrder(BSTNode tree)
  // Initializes preOrderQueue with tree elements in preOrder order.
  {
    if (tree != null)
    {
      preOrderQueue.enqueue(tree.getInfo());
      preOrder(tree.getLeft());
      preOrder(tree.getRight());
    }
  }

  private void postOrder(BSTNode tree)
  // Initializes postOrderQueue with tree elements in postOrder order.
  {
    if (tree != null)
    {
      postOrder(tree.getLeft());
      postOrder(tree.getRight());
      postOrderQueue.enqueue(tree.getInfo());
    }
  }

  public int reset(int orderType)
  // Initializes current position for an iteration through this BST
  // in orderType order. Returns current number of nodes in the BST.
  {
    int numNodes = size();

    if (orderType == INORDER)
    {
      inOrderQueue = new LinkedUnbndQueue();
      inOrder(root);
    }
    else
    if (orderType == PREORDER)
    {
      preOrderQueue = new LinkedUnbndQueue();
      preOrder(root);
    }
    if (orderType == POSTORDER)
    {
      postOrderQueue = new LinkedUnbndQueue();
      postOrder(root);
    }
    return numNodes;
  }

  public T getNext (int orderType)
  // Preconditions: The BST is not empty
  //                The BST has been reset for orderType
  //                The BST has not been modified since the most recent reset
  //                The end of orderType iteration has not been reached
  //
  // Returns the element at the current position on this BST for orderType
  // and advances the value of the current position based on the orderType. 
  {
    if (orderType == INORDER)
      return inOrderQueue.dequeue();
    else
    if (orderType == PREORDER)
      return preOrderQueue.dequeue();
    else
    if (orderType == POSTORDER)
      return postOrderQueue.dequeue();
    else return null;
  }
}

Chapter 8: /trees/ BSTInterface.java

//----------------------------------------------------------------------------
// BSTInterface.java            by Dale/Joyce/Weems                  Chapter 8
//
// Interface for a class that implements a binary search tree (BST).
//
// The trees are unbounded and allow duplicate elements, but do not allow null
// elements. As a general precondition, null elements are not passed as 
// arguments to any of the methods.
//
// The tree supports iteration through its elements in INORDER, PREORDER,
// and POSTORDER.
//----------------------------------------------------------------------------

package ch08.trees;

public interface BSTInterface>
{
  // used to specify traversal order
  static final int INORDER = 1;
  static final int PREORDER = 2;
  static final int POSTORDER = 3;

  boolean isEmpty();
  // Returns true if this BST is empty; otherwise, returns false.
  
  int size();
  // Returns the number of elements in this BST.

  boolean contains (T element);
  // Returns true if this BST contains an element e such that 
  // e.compareTo(element) == 0; otherwise, returns false.
    
  boolean remove (T element);
  // Removes an element e from this BST such that e.compareTo(element) == 0
  // and returns true; if no such element exists, returns false. 
  
  T get(T element);
  // Returns an element e from this BST such that e.compareTo(element) == 0;
  // if no such element exists, returns null.

  void add (T element);
  // Adds element to this BST. The tree retains its BST property.
  
  int reset(int orderType);
  // Initializes current position for an iteration through this BST
  // in orderType order. Returns current number of nodes in the BST.

  T getNext (int orderType);
  // Preconditions: The BST is not empty
  //                The BST has been reset for orderType
  //                The BST has not been modified since the most recent reset
  //                The end of orderType iteration has not been reached
  //
  // Returns the element at the current position on this BST for orderType
  // and advances the value of the current position based on the orderType. 
}

Chapter 8: /wordFreqs/ WordFreq.java

//----------------------------------------------------------------------------
// WordFreq.java              by Dale/Joyce/Weems                    Chapter 8
//
// Defines word-frequency pairs
//----------------------------------------------------------------------------

package ch08.wordFreqs;

import java.text.DecimalFormat;

public class WordFreq implements Comparable
{
  private String word;
  private int freq;

  DecimalFormat fmt = new DecimalFormat("00000");


  public WordFreq(String newWord)
  {
    word = newWord;
    freq = 0;
   }

  public void inc()
  {
    freq++;
  }

  public int compareTo(WordFreq other)
  {
    return this.word.compareTo(other.word); 
  }

  public String toString()
  {
    return(fmt.format(freq) + " " + word);
  }

  public String wordIs()
  {
    return word;
  }

  public int freqIs()
  {
    return freq;
  }
}