c++ - 来自 Cormen 的霍夫曼算法

Question

我正在尝试编写Huffman 编码树，使用multimap<int, NODE*>where NODEis just a classic tree node。所以我写了这个方法：

this->CreateMapTree();
int n = (int)tree.size();
pair<int, NODE*> x, y, z;

for (int i = 0; i < n-1; ++i)
{
    x = *tree.begin(); tree.erase(tree.begin());
    y = *tree.begin(); tree.erase(tree.begin());

    z.second = new NODE;

    z.second->left = y.second;
    z.second->right = x.second;
    z.first = x.first + y.first;

    tree.insert(z);
}//after loop there is only one element in the tree


head = tree.begin()->second;

方法CreateMapTree工作完美，结果我有tree。我使用了创建 Huffman 树的经典算法（来自 Cormen）。我多次检查此代码，但我找不到我的错误。代码三是错误的，我无法为编码和解码创建正确的字典。

怎么了？

Answer 1

我建议你看看从树中删除 x 和 y 后它们会发生什么。指向它们的指针可能不再有效。