我不明白这霍夫曼算法的实现 [英] I don't understand this Huffman algorithm implementation

查看:207
本文介绍了我不明白这霍夫曼算法的实现的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

    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页定义哈夫曼编码,和code以上。对我来说,这本书是不够详细,所以我已经做了google搜索,我学到哈夫曼编码工作的过程中是如何。教科书声称在的code以上年底,哈夫曼树制成。但对我来说似乎是错误的,因为一个哈夫曼树,是没有必要的一棵完整的树,但code以上似乎总是给的,因为一个完整的树 heap.push()。因此,有人可以向我解释如何这片code是不是错了?

In my Fundamentals of Data Structures in C++ textbook, it gave a 2 page definition of Huffman coding, and the code above. To me, the book wasn't enough detailed, so I've done the googling and I learned how the process of Huffman coding works. The textbook claims that at the end of the code above, a Huffman tree is made. But to me it seems wrong, because a Huffman tree, is not necessary a complete tree, but the code above seems to always give a complete tree because of the heap.push(). So can someone explain to me how this piece of code is not wrong?

推荐答案

堆的树状结构不一定匹配产生的哈夫曼树 - 相反,堆载部分哈夫曼树的森林,最初分别由单一的符号节点。环路然后反复开出两个节点具有最小加权值,将它们合并到一个节点,并把所得到的组合节点回。在该过程结束时,堆包含​​一个成品树

The heap's tree structure does not necessarily match the resulting Huffman tree -- rather, the heap contains a forest of partial Huffman trees, initially each consisting of a single symbol node. The loop then repeatedly takes the two nodes with the least weight, combines them into one node, and puts the resulting combined node back. At the end of the process, the heap contains one finished tree.

这篇关于我不明白这霍夫曼算法的实现的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆