BINARY SEARCH TREES - Introduction to Java Programming: Comprehensive Version - page 955

The coding tree is also used for decoding a sequence of bits into characters. To do so, start
with the first bit in the sequence and determine whether to go to the left or right branch of the
tree's root based on the bit value. Consider the next bit and continue to go down to the left or
right branch based on the bit value. When you reach a leaf, you have found a character. The
next bit in the stream is the first bit of the next character. For example, the stream 011001 is
decoded to sip , with 01 matching s , 1 matching i , and 001 matching p .
To construct a Huffman coding tree , use an algorithm as follows:

decoding

construct coding tree

1. Begin with a forest of trees. Each tree contains a node for a character. The weight of the
node is the frequency of the character in the text.

2. Repeat the following action to combine trees until there is only one tree: Choose two
trees with the smallest weight and create a new node as their parent. The weight of the
new tree is the sum of the weight of the subtrees.

3. For each interior node, assign its left edge a value 0 and right edge a value 1 . All leaf
nodes represent characters in the text.

Here is an example of building a coding tree for the text Mississippi . The frequency
table for the characters is shown in Figure 25.20b. Initially the forest contains single-node
trees, as shown in Figure 25.21a. The trees are repeatedly combined to form large trees until
only one tree is left, as shown in Figure 25.21b-d.

weight: 3 weight: 4

's'

weight: 4
'i'

weight: 1
'M'

weight: 4
's'

weight: 4
'i'

weight: 2
'p'

weight: 1
'M'

weight: 2
'p'

(a) (b)

weight: 11

0 1

weight: 7 weight: 4

'i'

weight: 7 weight: 4

'i'

0 1

weight: 3 weight: 4

's'

weight: 3 weight: 4

's'

0 1

weight: 1
'M'

weight: 2
'p'

weight: 1
'M'

weight: 2
'p'

(c) (d)

F IGURE 25.21

The coding tree is built by repeatedly combining the two smallest-weighted

trees.

It is worth noting that no code is a prefix of another code. This property ensures that the
streams can be decoded unambiguously.

prefix property

Pedagogical Note
For an interactive GUI demo to see how Huffman coding works, go to www.cs.armstrong
.edu/liang/animation/HuffmanCodingAnimation.html , as shown in Figure 25.22.

Huffman coding animation on
Companion Website