Introduction to Binary Trees - Advanced Topics in Java: Core Concepts in Data Structures - page 231

it is added to the tree, and its frequency count is set to 1. If the word is found, then its frequency count is incremented
by 1. At the end of the input, an in-order traversal of the tree gives the words in alphabetical order.
First, we must define the NodeData class. This will consist of two fields (a word and its frequency), a constructor,
a function to add 1 to the frequency, compareTo and visit . Here is the class:
class NodeData {
String word;
int freq;
public NodeData(String w) {
word = w;
freq = 0;
}
public void incrFreq() {
++freq;
}
public int compareTo(NodeData d) {
return this.word.compareTo(d.word);
}
public void visit() {
WordFrequencyBST.out.printf("%-15s %2d\n", word, freq);
}
} //end class NodeData
Note the method to increase the frequency by 1. In visit , we print the data at a node using the object
WordFrequencyBST.out . We will write the class WordFrequencyBST shortly, but, for now, note that we will let it
determine where the output should go, and out specifies the output stream. If you wanted, you could send the results
to the standard output stream using System.out.printf .
The gist of the algorithm for building the search tree is as follows:
create empty tree; set root to NULL
while (there is another word) {
get the word
search for word in tree; insert if necessary and set frequency to 0
add 1 to frequency //for an old word or a newly inserted one
}
print words and frequencies
For our program, we will define a word to be any consecutive sequence of uppercase or lowercase letters. In other
words, any nonletter will delimit a word. In particular, whitespace and punctuation marks will delimit a word. If in is a
Scanner object, we can specify this information with this statement:
in.useDelimiter("[^a-zA-Z]+"); // ^ means "not"
The part inside the square brackets means “any character that is not a lowercase or uppercase letter,” and the +
means one or more of those characters.