Java Reference
In-Depth Information
306
0
1
120
186
0
1
E
79
107
0
1
0
1
37
U
42
42
65
0
1
D
L
33
32
0
1
C
24
9
0
1
M
2
Z
7
K
Figure5.26
A Huffman tree for the letters of Figure 5.24.
Example5.8
Figure 5.25 illustrates part of the Huffman tree construction
process for the eight letters of Figure 5.24. Ranking D and L arbitrarily by
alphabetical order, the letters are ordered by frequency as
Letter
Z
K
M
C
U
D
L
E
Frequency
2
7
24
32
37
42
42
120
Because the first two letters on the list are Z and K, they are selected to
be the first trees joined together.
6
They become the children of a root node
with weight 9. Thus, a tree whose root has weight 9 is placed back on the
list, where it takes up the first position. The next step is to take values 9
and 24 off the list (corresponding to the partial tree with two leaf nodes
built in the last step, and the partial tree storing the letter M, respectively)
and join them together. The resulting root node has weight 33, and so this
tree is placed back into the list. Its priority will be between the trees with
values 32 (for letter C) and 37 (for letter U). This process continues until a
tree whose root has weight 306 is built. This tree is shown in Figure 5.26.
Figure 5.27 shows an implementation for Huffman tree nodes. This implemen-
tation is similar to the
VarBinNode
implementation of Figure 5.10. There is an
abstract base class, named
HuffNode
, and two subclasses, named
LeafNode
6
For clarity, the examples for building Huffman trees show a sorted list to keep the letters ordered
by frequency.
But a real implementation would use a heap to implement the priority queue for
efficiency.
