Problem A
Huffman Tree Tables
You are given a paragraph of text. Count the different
characters in the text to develop a Huffman tree for the given
input text. You should then output the table of symbols,
followed by the Huffman tree itself.
When selecting nodes to construct your tree, use the follwing
criteria to select nodes:
-
Lowest Frequency first.
-
Inner nodes before leaves.
-
Lower Ascii order first. …
Below is an example of a proper order selection.
![\includegraphics[width=.8\textwidth ]{tree}](/problems/ryerson.huffmantables/file/statement/en/img-0001.png)
Input
Input will contain a single line of text with less than 10000 characters. All characters are alphanumeric with the addition of " ", "." and ",".
Output
Your output should consist of two lists seprated by an empty line. The first list will contain all of the symbols, along with their respective frequency and Huffman code, sorted first by increasing frequency, then alphabetically. The second list will contain each inner node of the Huffman tree ordered by creation time.
When outputting the symbol list, output an index, symbol, frequency and Huffman code on each line, separated by spaces. Prefix the index of each symbol with a capital L.
When outputting the Huffman tree, output an index, frequency, Left node index and Right node index. Prefix the index of each tree with a capital N.
| Sample Input 1 | Sample Output 1 |
|---|---|
HIGH FEE TO FEED MOM ON MOON |
L0 D 1 10000 L1 G 1 10001 L2 I 1 10010 L3 T 1 10011 L4 F 2 1010 L5 H 2 1011 L6 N 2 1110 L7 M 3 1111 L8 E 4 110 L9 O 5 00 L10 6 01 N0 2 L0 L1 N1 2 L2 L3 N2 4 N0 N1 N3 4 L4 L5 N4 5 L6 L7 N5 8 N2 N3 N6 9 L8 N4 N7 11 L9 L10 N8 17 N5 N6 N9 28 N7 N8 |
| Sample Input 2 | Sample Output 2 |
|---|---|
A MAN A PLAN A CANAL, PANAMA. |
L0 , 1 00110 L1 . 1 00111 L2 C 1 0010 L3 L 2 1000 L4 M 2 1001 L5 P 2 000 L6 N 4 101 L7 6 01 L8 A 10 11 N0 2 L0 L1 N1 3 L2 N0 N2 4 L3 L4 N3 5 L5 N1 N4 8 N2 L6 N5 11 N3 L7 N6 18 N4 L8 N7 29 N5 N6 |
