Homework 18: Huffman Coding
Your task is to create a program which takes, as input, a description of a binary tree and a binary string, and produces as output the message which was encoded.
Example input:
*a**!*dc*rb
0111110010110101001111100100
The first line of the input will be a preorder traversal of a binary tree. The character “*” represents an internal tree node, and any other character (except the newline character) represents a leaf node.
So, decoding the above, we get this tree:
-*-
/ \
a -*-
/ \
* *
/ \ / \
! * r b
/ \
d c
Next, we decode the binary string using the general Huffman coding rules, where “0” is the left branch and “1” is the right branch.
Once you decode the binary string, print the resulting character string to stdout.
Here is another example for you to try:
** b*a*d*yo
1110100101100011010010110001101111111100
Bring your solution to our October meeting.
Feel free to discuss the problem or any other topics you are interested in on our mailing list (accessible via our Meetup Group).