4 
    template<class T>
    void huffman(MinHeap<TreeNode<T>*> heap, int n)
    {
      for(int i=0;i<n-1;i++)
      {
        TreeNode<T> *first = heap.pop();
        TreeNode<T> *second = heap.pop();
        TreeNode<T> *bt = new BinaryTreeNode<T>(first, second, first.data, second.data);
        heap.push(bt);
      }
    }

在我的 C++ 数据结构基础 教科书中，它给出了霍夫曼编码的 2 页定义，以及上面的代码。对我来说，这本书不够详细，所以我做了谷歌搜索，了解了霍夫曼编码的过程。教科书声称在上面的代码末尾，生成了一个霍夫曼树。但对我来说这似乎是错误的，因为霍夫曼树不一定是完整的树，但上面的代码似乎总是给出完整的树，因为heap.push(). 那么有人可以向我解释这段代码如何没有错吗？

4

2 回答 2

5

堆的树结构不一定与生成的 Huffman 树匹配——相反，堆包含部分 Huffman 树的森林，最初每个树都包含一个符号节点。然后循环重复取两个权重最小的节点，将它们组合成一个节点，并将得到的组合节点放回原处。在该过程结束时，堆包含一棵已完成的树。

于 2010-07-16T23:47:37.670 回答
0

霍夫曼编码通过在每一步取两个最低值项目来工作。当您第一次调用该函数时（因为您的 MinHeap 按值排序），两个最低值项目被弹出并“组合”到一个决策节点中，然后将其放回堆中。该节点通过其子分数的总和进行评分并放回堆中。将其重新插入堆中，根据其分数将其放入正确的位置；如果它仍然低于任何其他项目，它将是第一个，否则它将在其他地方。

所以这个算法是自下而上构建树，当你清空堆时，你将拥有一棵完整的树。不过，我不明白“n”是什么意思。循环应该是while (heap.size() > 1). 无论如何，树不是“满的”，不同的分支将有不同的长度，具体取决于初始堆中项目的频率如何评分。

于 2010-07-16T23:49:02.057 回答