Utilities - Data Structures and Problem Solving Using Java - page 487

generates an error. Otherwise, we return the value stored in the node (which
for nonleaf nodes turns out to be the symbol INCOMPLETE ).
In Figure 12.21 we have routines to read and write the encoding table. The
format that we use is simple and is not necessarily the most space-efficient.
For each character that has a code, we write it out (using one byte) and then
write out its character count (using four bytes). We signal the end of the table
by writing out an extra entry containing a null terminator character '\0' with a
count of zero. The count of zero is the special signal.
The readEncodingTable method initializes all the character counts to zero and
then reads the table, and updates the counts as they are read. It calls createTree ,
shown in Figure 12.22, to build the Huffman tree.
In that routine, we maintain a priority queue of tree nodes. To do so we
must provide a comparison function for tree nodes. Recall from Figure 12.17
that HuffNode implements Comparable<HuffNode> , ordering HuffNode objects on
the basis of node weight.
We then search for characters that have appeared at least once. When the test
at line 9 succeeds, we have such a character. We create a new tree node at lines
11 and 12, add it to theNodes at line 13, and then add it to the priority queue at
line 14. At lines 17 and 18 we add the end-of-file symbol. The loop that extends
from lines 20 to 28 is a line-for-line translation of the tree construction algorithm.
While we have two or more trees, we extract two trees from the priority queue,
merge the result, and put it back in the priority queue. At the end of the loop, only
one tree is left in the priority queue, and we can extract it and set root .

1 /**
2 * Get the character corresponding to code.
3 */
4 public int getChar( String code )
5 {
6 HuffNode p = root;
7 for( int i = 0; p != null && i < code.length( ); i++ )
8 if( code.charAt( i ) == '0' )
9 p = p.left;
10 else
11 p = p.right;
12
13 if( p == null )
14 return ERROR;
15
16 return p.value;
17 }

figure 12.20
A routine for decoding
(generating a
character, given the
code)