Solution for
Programming Exercise 11.2
THIS PAGE DISCUSSES ONE POSSIBLE SOLUTION to
the following exercise from this on-line
Java textbook.
Exercise 11.2:
Make a new version of the sample program WordList.java,
from Section 10.3, that stores words in a
binary sort tree instead of in an array.
Discussion
In WordList.java, an array is used
to store a list of (lower case) words in alphabetical order, and at the end of the
program the words are output to a file in order. Since a binary sort tree
is designed to store words in alphabetical order, it can be used as
a substitute for the array. At the end of the program, an inorder
traversal of the tree can be used to output the words to the file.
Using an inorder traversal guarantees that the words will be output in order.
Only a few changes are needed in the main() routine. They are
marked in red in the solution shown below. It uses a differnt type of
variable, and it calls a few different routines, but the logic is unchanged.
The code that we need in
order to implement the binary sort tree can be copied almost directly
from Section 11.4. The inorderPrint()
routine in that section prints its strings to standard output. In order
to print to a file, I have added a parameter of type PrintWriter.
The main() routine provides a stream for writing to the
output file.
The treeInsert() routine from Section 11.4 has been renamed
to insertWord() here, to be consistent with the subroutine call
in the main() routine. I have also made a few other changes
to adapt it to this program. The insertWord() routine coverts
its parameter to lower case. It also refuses to insert duplicate items
into the tree. That is, if it finds a copy of the parameter already in
the tree, it returns without adding anything to the tree.
All-in-all, the substitution of the binary tree for the array is
very straightforward.
The Solution
Changes in the main() routine are shown in red.
In the part of the program that implements binary sort trees, changes
from the versions in Section 11.4 are shown in red.
/*
This program lets the user specify a text file for input and a file
for output. All the words are read from the input file. Words are
converted to lower case. An alphabetical list of all the words that
were found, without repetition, is written to the output file, with
one word per line. A word in this program is defined to be any
sequence of letters.
In this version of the program, words are stored in a binary
sort tree.
This class depends on the non-standard classes TextIO and TextReader,
*/
import java.io.*;
public class WordListWithTree {
//------------------ The main program ------------------------------------
static TreeNode root; // Points to the root of the binary sort
// tree that holds the words. At the
// beginning of the program, when the tree
// is empty, root is null.
public static void main(String[] args) {
TextReader in; // A stream for reading from the input file.
PrintWriter out; // A stream for writing to the output file.
String inputFileName; // Input file name, specified by the user.
String outputFileName; // Output file name, specified by the user.
root = null; // Start with an empty tree. (Not really necessary,
// since null is the default initial value anyway.)
/* Get the input file name from the user and try to create the
input stream. If there is a FileNotFoundException, print
a message and terminate the program. */
TextIO.put("Input file name? ");
inputFileName = TextIO.getln().trim();
try {
in = new TextReader(new FileReader(inputFileName));
}
catch (FileNotFoundException e) {
TextIO.putln("Can't find file \"" + inputFileName + "\".");
return;
}
/* Get the output file name from the user and try to create the
output stream. If there is an IOException, print a message
and terminate the program. */
TextIO.put("Output file name? ");
outputFileName = TextIO.getln().trim();
try {
out = new PrintWriter(new FileWriter(outputFileName));
}
catch (IOException e) {
TextIO.putln("Can't open file \"" + outputFileName + "\" for output.");
TextIO.putln(e.toString());
return;
}
/* Read all the words from the input stream and insert them into
the array of words. Reading from a TextReader can result in
an error of type TextReader.Error. If one occurs, print an
error message and terminate the program. */
try {
while (true) {
// Skip past and non-letters in the input stream. If an
// end-of-stream has been reached, end the loop. Otherwise,
// read a word and insert it into the array of words.
while ( ! in.eof() && ! Character.isLetter(in.peek()) )
in.getAnyChar();
if (in.eof())
break;
insertWord(in.getAlpha());
}
}
catch (TextReader.Error e) {
TextIO.putln("An error occurred while reading from the input file.");
TextIO.putln(e.toString());
return;
}
/* Write all the words from the tree to the output stream. */
inorderPrint(root, out);
/* Finish up by checking for an error on the output stream and
printing either a warning message or a message that the words
have been output to the output file. */
if (out.checkError() == true) {
TextIO.putln("\nSome error occurred while writing output.");
TextIO.putln("Output might be incomplete or invalid.");
}
else {
TextIO.putln("\n" + countNodes(root) + " words from \"" + inputFileName +
"\" output to \"" + outputFileName + "\".");
}
} // end main()
//------------- A class and subroutines for the binary sort tree ----------
static class TreeNode {
// An object of type TreeNode represents one node
// in a binary tree of strings.
String item; // The data in this node.
TreeNode left; // Pointer to left subtree.
TreeNode right; // Pointer to right subtree.
TreeNode(String str) {
// Constructor. Make a node containing str.
item = str;
}
} // end class TreeNode
static void inorderPrint(TreeNode node, PrintWriter output) {
// Output the items in the tree to which node points.
// The items are listed, one to a line, on the specified
// output streams. An inorder listing is used, which
// will print the words in the binary sort tree in
// alphabetical order.
if (node != null) {
inorderPrint( node.left, output );
output.println(node.item);
inorderPrint( node.right, output );
}
} // end inorderPrint()
static int countNodes(TreeNode node) {
// Return the number of nodes in the tree to which node points.
if (node == null)
return 0;
else
return 1 + countNodes(node.left) + countNodes(node.right);
}
static void insertWord(String newItem) {
// Add the word to the binary sort tree to which the
// global variable "root" refers. Duplicate entries
// will be ignored! All words are converted to lower case.
newItem = newItem.toLowerCase();
if ( root == null ) {
// The tree is empty. Set root to point to a new node
// containing the new item.
root = new TreeNode( newItem );
return;
}
TreeNode runner; // Runs down the tree to find a place for newItem.
runner = root; // Start at the root.
while (true) {
if ( newItem.equals(runner.item) ) {
// The word is already in the tree. Don't insert
// another copy. Just return.
return;
}
if ( newItem.compareTo(runner.item) < 0 ) {
// Since the new item is less than the item in runner,
// it belongs in the left subtree of runner. If there
// is an open space at runner.left, add a node there.
// Otherwise, advance runner down one level to the left.
if ( runner.left == null ) {
runner.left = new TreeNode( newItem );
return; // New item has been added to the tree.
}
else
runner = runner.left;
}
else {
// Since the new item is greater than or equal to the
// item in runner, it belongs in the right subtree of
// runner. If there is an open space at runner.right,
// add a new node there. Otherwise, advance runner
// down one level to the right.
if ( runner.right == null ) {
runner.right = new TreeNode( newItem );
return; // New item has been added to the tree.
}
else
runner = runner.right;
}
} // end while
} // end insertWord()
} // end class WordListWithTree
[ Exercises
| Chapter Index
| Main Index
]
