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

1 // Basic node in a Huffman coding tree.
2 class HuffNode implements Comparable<HuffNode>
3 {
4 public int value;
5 public int weight;
6
7 public int compareTo( HuffNode rhs )
8 {
9 return weight - rhs.weight;
10 }
11
12 HuffNode left;
13 HuffNode right;
14 HuffNode parent;
15
16 HuffNode( int v, int w, HuffNode lt, HuffNode rt, HuffNode pt )
17 { value = v; weight = w; left = lt; right = rt; parent = pt; }
18 }

figure 12.17
Node declaration for
the Huffman coding
tree

The HuffmanTree class provides the writeEncodingTable method to write the
tree out to an output stream (in a form suitable for a call to readEncodingTable ).
It also provides public methods to convert from a character to a code, and vice
versa. 1 Codes are represented by an int[] or String , as appropriate, in which
each element is either a 0 or 1.
Internally, root is a reference to the root node of the tree, and theCounts is a
CharCounter object that can be used to initialize the tree nodes. We also maintain
an array, theNodes , which maps each character to the tree node that contains it.
Figure 12.19 shows the constructors and the routine (public method and
private helper) to return the code for a given character. The constructors
start with empty trees, and the one-parameter constructor initializes the
CharCounter object, and immediately calls the private routine createTree . The
CharCounter object is initialized to be empty in the zero-parameter constructor.
For getCode , by consulting theNodes , we obtain the tree node that stores
the character whose code we are looking for. If the character is not repre-
sented, we signal an error by returning a null reference. Otherwise we use a
straightforward loop up the tree, following parent links, until we reach the
root (which has no parent). Each step prepends a 0 or 1 to a string, which is
converted to an array of int prior to returning (of course, this creates many
temporary strings; we leave it to the reader to optimize this step).

1. Technical alert: An int is used instead of byte to allow all characters and the EOF symbol.