Comp Sci Creating Huffman Tree with Coding Frequency

[anonim]

Homework Statement

Taking a string, creating the Huffman coding tree and encrypting each character

Relevant Equations

-

First, I get the string and I find the frequency of the every character. My struct is:

typedef struct huffman_tree{
    char c;
    int freq; //unsigned?
    struct huffman_tree *left; // 0 (left)
    struct huffman_tree *right; // 1 (right)
}huffman_tree;

I write this to create Huffman tree:

huffman_tree *huffman_node_create(char data, unsigned int frequency)
{
    huffman_tree *node = malloc(sizeof(huffman_tree));

        node->data = data;
        node->frequency = frequency;
        node->left = NULL;
        node->right = NULL;

    return node;
}

But I do not know how can I add the frequency the tree, how can I know the number should be right or left?

 

[jedishrfu]

Review the wiki article, it has an example of a Huffman tree with frequency values shown for each node that should make it obvious How to proceed.

https://en.wikipedia.org/wiki/Huffman_coding

As you add each node to the tree, then you can update the freq values of parent nodes.

Alternatively, you can create the tree in one pass and then walk through it to update the noncharacter nodes frequency values in the next pass. A recursive algorithm would work here.

 

[rcgldr]

I'm wondering about creating an 256 array of frequencies, sorting the array (descending order), creating the tree as a sorted linked list using only the node->right pointers, then balancing the tree, using the vine to tree logic of the Day Stout Warren algorithm.

https://en.wikipedia.org/wiki/Day–Stout–Warren_algorithm

https://web.eecs.umich.edu/~qstout/pap/CACM86.pdf