Thread: help for novice re: Huffman tree

I'm trying to code a Huffman tree header, with the ADT defined from an old on-line course in C programming. I'm stumped by the following instructions:

MAKING A CODE TABLE: Once the Huffman tree is built---
We need to make a code table from the tree that contains the bitcode for each character. We create this
table by traversing the tree and keeping track of the left branches we take (we designate this a 0) and the
right branches we take (the opposite bit sense - a 1) until we reach a leaf node. Once we reach a leaf, we
have a full code for the character at the leaf node which is simply the string of left and right moves which
we have strung together along with the code’s length. The output of this procedure is an array, indexed
by character (a number between 0 and 127 for a 7 bit ascii character), that contains an entry for the coded
bits and the code’s length.

I've already made a character-frequency array, and made the tree itself, but do not understand how to construct something such as:

Code:

for (int i = 0;i < 127; i++) {
path_table[i] = path;
}

where path would be the appropriate sequence of 1's and 0's.
For example, what type would the path_table array have? Do I need a special function to write successive bits into path, as opposed to chars?
I hope that my question is clear, and thus answerable.

Originally Posted by atlantis43

but what type of empty variable is needed to hold the bits?

Your problem says: "array, indexed by character (a number between 0 and 127 for a 7 bit ascii character), that contains an entry for the coded bits and the code’s length."

So, I'd use

Code:

typedef struct {
    unsigned int path;
    unsigned char length;
} huffman_code;

An unsigned int has (CHAR_BIT*sizeof (unsigned int)) bits, and an unsigned char can hold values between 0 and UCHAR_MAX, inclusive.

So, an array of huffman_code entries can describe any Huffman tree whose maximum depth does not exceed (CHAR_BIT*sizeof (unsigned int)) or UCHAR_MAX (whichever is smaller applies). These constants are defined in limits.h header file.

Let's assume you have a table of the above codes, and you initialize it to "no path/no code":

Code:

    #include <limits.h>

    huffman_code table[UCHAR_MAX + 1];
    int i;

    for (i = 0; i <= UCHAR_MAX; i++) {
        table[i].path = 0U; /* Same as (unsigned int)0 */
        table[i].length = 0U; /* The U just means unsigned */
    }

and you're working on tree

Consider the leaf specifying x: The path from root to it is right-left-left-right-left, or 10010, five steps long. Since 10010 in binary is 16+2=18 in decimal, you should have

Code:

    table['x'].path = 18;
    table['x'].length = 5;

Here's the trick: instead of looping over the 128 characters to fill the table, traverse your tree, keeping track of the path (left or right, and how many steps) taken to reach the current node from the root. Whenever you reach a leaf node, you fill in the corresponding table entry. As you traverse the entire tree, you fill the table.

Assuming your tree is correctly built, the entries that do not get defined while traversing the tree, will not be used at all. (Which is why it is a good idea to initialize them as "no path".)

Questions?