Why do we need unsigned char for Huffman tree code

Question

I am trying to create a Huffman tree the question I read is very strange for me, it is as follows:

Given the following data structure:
struct huffman
{
    unsigned char sym;              /* symbol */
    struct huffman *left, *right;   /* left and right subtrees */
};
write a program that takes the name of a binary file as sole argument, builds the Huffman tree of that file assuming that atoms (elementary symbols) are 8-bit unsigned characters, and prints the tree as well as the dictionary.
allocations must be done using nothing else than malloc(), and sorting can be done using qsort().

Here the thing which confuses me is that to write a program to create a huffman tree we just need to do following things:

We need to take a frequency array (That could be Farray[]={.......})
Sort it and add the two smallest nodes to form a tree until it don't left 1 final node(which is head).

Now the question is here: why and where do we need those unsigned char data? (what type of unsigned char data this question want, I think only frequency is enough to display a Huffman tree)?

Notlikethat Notlikethat · Accepted Answer · 2014-01-09T22:48:26

If you purely want to display the shape of the tree, then yes, you just need to build it. However, for it to be of any use whatsoever you need to know what original symbol each node represents.

Imagine your input symbols are [ABCD]. An imaginary Huffman tree/dictionary might look like this:

         ( )
        /   \              A = 1
      ( )   (A)            B = 00
     /   \                 C = 010
   (B)   ( )               D = 011
        /   \
      (C)   (D)

If you don't store sym, it looks like this:

         ( )
        /   \              A = ?
      ( )   ( )            B = ?
     /   \                 C = ?
   ( )   ( )               D = ?
        /   \
      ( )   ( )

Not very useful, that, is it?

Edit 2: The missing step in the plan is step 0: build the frequency array from the file (somehow I missed that you don't need to actually encode the file too). This isn't part of the actual Huffman algorithm itself and I couldn't find a decent example to link to, so here's a rough idea:

FILE *input = fopen("inputfile", "rb");
int freq[256] = {0};
int c;
while ((c = fgetc(input)) != EOF)
    freq[c]++;
fclose(input);

/* do Huffman algorithm  */
...

Now, that still needs improving since it neither uses malloc() nor takes a filename as an argument, but it's not my homework ;)

Why do we need unsigned char for Huffman tree code

3 Answers