c++ - 霍夫曼编码树

Question

我正在尝试构建霍夫曼编码树。

主要内容:

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;
}

输入应该在表单上:

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

到目前为止我还没有让它工作。有什么想法可能是错的吗？

build_tree 函数:

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;
}

打印功能:已提供，所以我认为它是正确的。

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

你有几个问题:

• 永远不会分配外部 NodePtr p。
• NodePtr b 没有pop
• 新节点不引用其子节点 a 和 b
• 您不返回根。

因此以下内容可能会有所帮助:

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.