Hw17 Build Huffman Code Book from Post-Order Description Solution

Learning Goals
==============

* Understand Huffman Compression

* Understand the description of the compression tree using post-order description

Post-Order Description of Huffman Compress Tree
===============================================

The compression tree can be expressed by post-order traversal.  When a
leaf node is encountered, 1 is printed before printing the character
stored in the node. When a non-leaf node is encountered, 0 is printed.
If the tree has `n` leaf nodes, the tree has `n-1` non-leaf nodes.
Thus, there are `n` 1 printed (not counting the characters) and `n-1`
0 printed.  A final 0 is added to indicate the end of the description.

To rebuild the compression tree, we need to separate the control
from the data. Consider this example:



Control or Data | C | D | C | D | C | D | C | D  
----------------|---|---|---|---|---|---|---|---
Input           | 1 | A | 1 | m | 1 | # | 1 | G

When control `1` is seen, the next must be data. Create a tree node to
hold the data and append the node to the end of a list.  The input so
far should produce the following list of four tree nodes:


When control `0` is seen, take the latest two tree nodes and make them the left and right child of a new tree
node. Insert this tree node back to the list.

The following input 

Control or Data | C | D | C | D | C | D | C | D | C | C 
----------------|---|---|---|---|---|---|---|---|---|---
Input           | 1 | A | 1 | m | 1 | # | 1 | G | 0 | 0

will create this result:


The following input 

Control or Data | C | D | C | D | C | D | C | D | C | C | C | C | D | C | D | C
----------------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Input           | 1 | A | 1 | m | 1 | # | 1 | G | 0 | 0 | 0 | 1 | c | 1 | s | 0

will create this result:


The following input 

Control or Data | C | D | C | D | C | D | C | D | C | C | C | C | D | C | D | C | C | C
----------------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Input           | 1 | A | 1 | m | 1 | # | 1 | G | 0 | 0 | 0 | 1 | c | 1 | s | 0 | 0 | 0

will create this result:


Please check the `inputs` directory for sample inputs.  Please notice
that the input does *not* have space or new line separating them. This
requirement allows space or new line to be part of the data.

You can assume that the input is a valid post-order traversal of a
Huffman compression tree.  Your program does not need to check whether
the input is valid.

Your Program's Output
=====================

Your program will the characters, its ASCII value (in decimal), and the codes 

```
A 65 00
m 109 010
# 35 0110
G 71 0111
c 99 10
s 115 11
```

The order of your output does not matter because the output will be sorted before comparison with
the expected output.

Submission
==========

Please submit all necessary files. These are the requirements:

* You must include `Makefile`. Without `Makefile`, it is not possible building your program.

* The executable must be called `hw17` and must not be called anything else.

* Your program should take one argument (`argv[1]`) as the input file name.

* The program's output should be printed to the computer screen (using
  `printf`). The output will be redirected to a file, sorted, and
  compared with the expected output.

* Your program must not have any unwanted output. Unwanted output will
  be treated as errors.

Upload a zip file to Brightspace.