Huffman Encoding tree

Question

I am trying to build an Huffman encoding tree.

main:

int main()
{
    // Read frequency table and build Huffman tree.
    NodePtr huffman = build_tree();
    print_tree(huffman);

    // Free the allocated memory.
    free_memory(huffman);

    return 0;
}

The input should be on the form:

number of letters
"letter" number of occurrences
"letter2" number of occurrences

So far I have not got it to work. Any ideas what might be wrong?

build_tree function:

NodePtr build_tree()
{
    int characters;//number of characters
    cin >> characters;
    char letter;
    int freq;
    HuffmanPriorityQueue queue;
    NodePtr p;
    for (int i = 0 ; i < characters; i++)
    {
        cin >> letter;
        cin >> freq;
        NodePtr temp = new HuffmanNode(freq, letter);
        queue.push(temp);
    }
    for (int i = 0 ; i < characters - 1 ; i++)
    {
        NodePtr a = queue.top();
        queue.pop();
        NodePtr b = queue.top();
        NodePtr p = new HuffmanNode (a->frequency + b->frequency, NULL);
        queue.push(p);
    }
    return p;
}

The print function: Which was supplied so I assume it is correct.

void print_tree(NodePtr root, int indent = 0, string prefix = "")
{
    // External nodes are not printed.
    if (root == NULL) {
        return;
    }

    char letter = ' ';
    if (root->is_leaf()) {
        letter = root->letter;
    }

    cout << string(indent, ' ') << prefix << "(" << letter << " [" << root->frequency << "]";
    if (root->is_leaf()) {
        cout << ")" << endl;
    } else {
        cout << endl;
        // Print left and right subtrees with the appropriate prefix, and
        // increased indent (by INDENT_SIZE).
        print_tree(root->left, indent + INDENT_SIZE, "0");
        print_tree(root->right, indent + INDENT_SIZE, "1");
        cout << string(indent, ' ') << ")" << endl;
    }
}

Answer 1

You have several problems:

• The outer NodePtr p is never assigned.
• There is no pop for NodePtr b
• New node doesn't refer to its children a and b
• You don't return the root.

So following may help:

for (int i = 0 ; i < characters - 1 ; i++)
{
    NodePtr a = queue.top();
    queue.pop();
    NodePtr b = queue.top();
    queue.pop();
    NodePtr p = new HuffmanNode (a, b); // The new node has two children `a` and `b`.
    queue.push(p);
}
return queue.top(); // Return root.