Section 6.4 Huffman Codes
543
When this algorithm terminates, L consists of just one node, which is the root
of the final binary tree. Codes can then be assigned to each leaf of the tree by tracing the path from the root to the leaf and accumulating 0s for left branches and
1s for right branches. By the way the tree is constructed, every internal node will
have exactly two children.
ExamplE 39
We’ll use algorithm HuffmanTree to build the tree of Figure 6.57, which is based
on the data of Example 37. L initially contains the six nodes, ordered by frequency:
4
9
10
12
17
48
Following the algorithm, we enter the for loop for the first time. The x and y nodes
are those with frequencies 4 and 9, respectively. A new node z with frequency
4 + 9 = 13 is created and inserted in order into L, with the x node as its left child
and the y node as its right child The new L looks like the following:
This process is repeated four more times. The resulting L at each stage follows:
13
17
4
9
22
48
10
12
4
9
30
48
13
17
22
10
12
4
9
30
22
52
48
13
17
0
1
2
1
52
30
22
48 (a)
10 (?)
1 3
17 (p)
12 (g)
4 (k) 9 (c)
100
and then
At this point the tree is complete and the codes can be assigned. The code for c, for
example, is 1101 (right branch, right branch, left branch, right branch).