4.9.1 Huffman Coding

1.

Problem: Given a set of alphabets and their relative frequencies, find the Huffman binary code using binary trees and an optimal ternary code using ternary trees.

2.

Reading: Read pages 94-102 of "Data Structures and Algorithms" by Aho, Hopcroft, and Ullman.

3.

Input: The number of alphabets and relative frequencies of those, for example,

8 .2 .02 .3 .05 .03 .15 .22 .03

Assume the alphabets as 1, 2, 3, ..., without loss of generality.

4.

Output: For each alphabet, print the Huffman binary code and an optimal ternary code. Also print the average length of code.

5.

Data structures: For binary trees, use the data structures suggested by Aho, Hopcroft, and Ullman. For ternary trees, use similar data structures based on leftmostchild-right sibling representation with nodes organized into cellspace.

6.

Programming language: Use C or C++or Java. Best practices in programming should be adhered to.