Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

258 BINARY TREES [CHAP. 10

Fig. 10-30

(The circled number indicates the root of the new subtree in the step.) The treeTis drawn from Step (f) backward,

yielding Fig. 10-30(b). The path length ofTfollows:

P= 25 ( 2 )+ 4 ( 4 )+ 5 ( 4 )+ 8 ( 3 )+ 15 ( 2 )+ 16 ( 2 )

= 50 + 16 + 20 + 24 + 30 + 32

= 172

(The tree in Fig. 10-30(a) has path length 231.)

10.15. Suppose data itemsA,B,C,D,E,F,Goccur with the following probability distribution:

Data item: ABCDEFG

Probability: 10305 1520155

Find a Huffman code for the data items.

As in Fig. 10-31(a), apply the Huffman algorithm to find a 2-tree with a minimum weighted path lengthP.

(Again, the circled number indicates the root of the new subtree in the step.) The treeTis drawn from Step (g)

backward, yielding Fig. 10-31(b). Assign bit labels to the edges of the treeT, 0 to a left edge and 1 to a right edge, as

in Fig. 10-31(b). The treeTyields the following Huffman code:

A: 000 ; B: 11 ; C: 0010 ; D: 100 ; E: 01 ; F: 101 ; G: 0011

Fig. 10-31