这是我的第一篇博客，希望大神们批评指正。

首先介绍以下什么是哈夫曼树（来自百度百科）

哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。

构造哈夫曼树的主要思想：

构造哈夫曼树非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点（树根）。

这里用到了最小优先队列。

我这里用STL来实现。（这里有优先队列的介绍） 

  1. template<typename T>
  2. struct cmp
  3. {
  4.     bool operator()(TreeNode<T>* t1, TreeNode<T>*  t2)
  5.     {
  6.         return !(*t1 < *t2);
  7.     }
  8. };

优先队列的定义：

  1. priority_queue<TreeNode*,vector<TreeNode* >,cmp > pri_que;

哈夫曼树节点结构

  1. template<typename T>
  2. class TreeNode
  3. {
  4. public:
  5.     TreeNode():pfather(NULL),plchild(NULL),prchild(NULL)
  6.     {
  8.     }
  9.     T data;
  10.     TreeNode *pfather;
  11.     TreeNode *plchild;
  12.     TreeNode *prchild;
  14.     bool operator < (const TreeNode& rhs)
  15.     {
  16.         return data < rhs.data;
  17.     }
  19. };

构造哈夫曼树

每次从最小优先队列取头两个节点，合并后放回最小优先队列，如此重复。

  1. template<typename T>
  2. TreeNode<T>* MakeHuffmanTree(T* begin, T* end) //构造哈夫曼树
  3. {
  4.     priority_queue<TreeNode<T>*,vector<TreeNode<T>* >,cmp<T> > pri_que;
  5.     T *iter = begin;
  6.     TreeNode<T>* pNode;
  7.     TreeNode<T>* pf = NULL;
  8.     while(iter != end)
  9.     {
  10.         pNode = new TreeNode<T>;
  11.         pNode->data = *iter++;
  12.         pNode->pfather = pf;
  13.         pri_que.push(pNode);
  14.     }
  15.     TreeNode<T>* plchild;
  16.     TreeNode<T>* prchild;
  17.     while(pri_que.size() > 1)//取两个小的合并
  18.     {
  19.         plchild = pri_que.top();
  20.         pri_que.pop();
  21.         prchild = pri_que.top();
  22.         pri_que.pop();
  24.         pNode = new TreeNode<T>;
  25.         pNode->plchild = plchild;
  26.         pNode->prchild = prchild;
  27.         pNode->data = plchild->data + prchild->data;
  29.         pri_que.push(pNode);
  30.     }
  32.     pNode = pri_que.top();
  33.     pri_que.pop();
  34.     return pNode;
  35. }

构造哈夫曼树这个函数的参数是一个结构体，保存着对应字符，其频率，编码值。

重载它的+运算符，为了合并时的+运算（只是频率相加）。

 



到此为止，已经可以把哈夫曼树生成出来了。




  1. template<typename T>
  2. struct mydata
  3. {
  4.     mydata(){}
  5.     mydata(int i):freq(i)
  6.     {
  8.     }
  9.     string coded;
  10.     int freq;
  11.     T data;
  13.     bool operator<(const mydata& rhs)
  14.     {
  15.         return freq < rhs.freq;
  16.     }
  18.     mydata operator+(mydata& rhs)
  19.     {
  20.         return mydata(freq + rhs.freq);
  21.     }
  22. };




我们可以通过DFS将每个叶子节点的路径记录下来（用一个全局变量数组path），然后得到它的编码。


当发现当前节点是叶子节点，就把当前的路径赋值至该叶子节点的编码属性（coded）。




  1. const int MAXLEN = 20;
  2. char path[MAXLEN] = {0};
  3. template<typename T>
  4. void DFS(T* root,int deep = -1, char a = \'-\')  //DFS 得到叶子节点的编码
  5. {
  6.     if(root == NULL)
  7.         return;
  9.     if(a != \'-\')
  10.         path[deep] = a;
  12.     if(root->plchild == NULL || root->prchild == NULL)//leaf
  13.         (root->data).coded = string(path,path + deep + 1);
  15.     if(root->plchild != NULL)
  16.         DFS(root->plchild, deep + 1, \'0\');
  17.     if(root->prchild != NULL)
  18.         DFS(root->prchild, deep + 1, \'1\');
  19. }




这样整个哈夫曼编码工作已经完成，为了查看我们的编码结果，我们可以用BFS跟DFS来看到我们的结果。在这里我选择了BFS。


当遍历到叶子节点，就将其编码属性（coded）和其对应字符输出。




  1. template<typename T,typename U>
  2. void BFS(T* root, mydata<U>* data) //BFS 将叶子节点的编码，提到data指向的数据
  3. {
  4.     queue<T*> que;
  5.     que.push(root);
  7.     T* pT = NULL;
  8.     while(!que.empty())
  9.     {
  10.         pT = que.front();
  11.         //cout<<pT->data.freq<<endl;
  12.         que.pop();
  14.         if(pT->plchild != NULL)
  15.             que.push(pT->plchild);
  16.         if(pT->prchild != NULL)
  17.             que.push(pT->prchild);
  18.         if(pT->plchild == NULL || pT->prchild == NULL)// leaf 提取叶子节点的编码
  19.         {
  20.             //cout<<(pT->data).data<<":"<<(pT->data).coded<<endl;
  21.             mydata<U>* pd = data;
  22.             while((pT->data).data != pd->data)
  23.                 pd++;
  24.             assert(pd->data == (pT->data).data);
  25.             pd->coded = (pT->data).coded;
  26.         }
  27.     }
  28. }




 测试驱动代码




  1.     mydata<char> *pdata = new mydata<char>[4];
  2.     pdata[0].data = \'a\';
  3.     pdata[0].freq = 7;
  4.     pdata[1].data = \'b\';
  5.     pdata[1].freq = 5;
  6.     pdata[2].data = \'c\';
  7.     pdata[2].freq = 2;
  8.     pdata[3].data = \'d\';
  9.     pdata[3].freq = 4;
  10.     TreeNode<mydata<char> >* pihuffmanTree = MakeHuffmanTree(pdata, pdata + 4);
  12.     DFS(pihuffmanTree);
  13.     BFS(pihuffmanTree);





为了更方便的使用我将这些封装到一个类里面。




  1. template<typename T>
  2. class Huffman
  3. {
  4. public:
  5.     void Coded(string& coded);//传入待输出的编码
  6.     void DeCode(const string& codedstr,string& decodestr);//输入待解码字符串，输出解码字符串
  7.     void InputData(T* begin,T* end);//传入数据
  8.  
  9. private:
  10.     string FindVal(char c);
  11.     void m_CalcFreq(T* begin, T* end);//计算输入数据的频率
  12.     TreeNode<mydata<T> > *root;//huffman根节点
  13.     mydata<T>* data;
  14.     int data_size;
  15.     
  16.     T* m_begin;//保存原始数据的开始与结束的位置
  17.     T* m_end;
  18.     //string codedstr;
  20. };




输入数据并计算其频率。


用map容器来统计输入字符每个出现的个数。




  1. template<typename T>
  2. void Huffman<T>::InputData(T* begin, T* end)
  3. {
  4.     this->m_begin = begin;
  5.     this->m_end = end;
  6.         m_CalcFreq(begin, end);
  8. }
  10. template<typename T>
  11. void Huffman<T>::m_CalcFreq(T* begin, T* end)
  12. {
  14.     int len = end - begin;
  15.     //data_size = len;
  16.     if(len == 0)
  17.         return;
  19.     map<T,int> countMap;
  20.     map<T,int>::iterator mapIter = countMap.begin();
  21.     T *pT = begin;
  22.     while(pT != end)
  23.     {
  24.         mapIter = countMap.find(*pT);
  25.         if(mapIter != countMap.end())//在map里有没有字符*iter
  26.             ++mapIter->second;
  27.         else
  28.         {
  29.             countMap.insert(make_pair(*pT,1));
  30.         }
  31.         pT++;
  32.     }
  34.     data_size = countMap.size();
  35.     data = new mydata<T>[data_size];
  36.     int i = 0;
  37.     for (mapIter = countMap.begin(); mapIter != countMap.end(); ++mapIter)
  38.     {
  39.         data[i].data = mapIter->first;        
  40.         data[i].freq = mapIter->second;
  41.         i++;
  42.     }
  44. }




编码




  1. template<typename T>
  2. void Huffman<T>::Coded(string& coded)
  3. {
  4.     root = MakeHuffmanTree(data,data + data_size);
  5.     DFS(root);
  7.     BFS(root,data);
  9.     cout<<"code:"<<endl;
  10.     for (int i = 0; i < data_size; ++i)
  11.     {
  12.         cout<<data[i].data<<":"<<data[i].coded<<endl;
  13.     }
  15.     
  16.     T *begin = m_begin;
  17.     while (begin != m_end)
  18.     {
  19.         coded += FindVal(*begin);
  20.         begin++;
  21.     }
  22.     //string subcode = 
  23. }




 



解码




  1. template<typename T>
  2. void Huffman<T>::DeCode(const string& codedstr,string& decodestr)
  3. {
  4.     string::const_iterator iter = codedstr.begin();
  5.     TreeNode<mydata<T> >* curNode = root;
  6.     while (iter != codedstr.end())
  7.     {
  8.         if (curNode->plchild == NULL || curNode->prchild == NULL)
  9.         {
  10.             decodestr += (curNode->data).data;
  11.             curNode = root;
  12.             continue;
  13.         }
  14.         if (*iter == \'0\')
  15.             curNode = curNode->plchild;
  16.         
  17.         if(*iter == \'1\')
  18.             curNode = curNode->prchild;
  20.         iter++;
  21.     }
  22. }




测试驱动程序




  1.         char *pmystr = "cbcddddbbbbaaaaaaa";
  3.         Huffman<char> h;
  4.         h.InputData(pmystr, pmystr + 18);
  6.     cout<<"originstr: "<<pmystr<<endl;
  8.     string coded;
  9.     h.Coded(coded);
  11.     cout<<"coded: "<<coded<<endl;
  13.     string decode;
  14.     h.DeCode(coded,decode);
  15.     cout<<"decode: "<<decode<<endl;




完整程序(环境：VS2012)




  1. #include <iostream>
  2. //#include <algorithm>
  3. #include <queue>
  4. #include <string>
  5. #include <vector>
  6. #include <cassert>
  7. #include <map>
  8. using namespace std;
  11. template<typename T>
  12. class TreeNode
  13. {
  14. public:
  15.     TreeNode():pfather(NULL),plchild(NULL),prchild(NULL)
  16.     {
  19.     }
  20.     T data;
  21.     TreeNode *pfather;
  22.     TreeNode *plchild;
  23.     TreeNode *prchild;
  26.     bool operator < (const TreeNode& rhs)
  27.     {
  28.         return data < rhs.data;
  29.     }
  32. };
  35. template<typename T>
  36. struct cmp
  37. {
  38.     bool operator()(TreeNode<T>* t1, TreeNode<T>*  t2)
  39.     {
  40.         return !(*t1 < *t2);
  41.     }
  42. };
  47. template<typename T>
  48. TreeNode<T>* MakeHuffmanTree(T* begin, T* end) //构造哈夫曼树
  49. {
  50.     priority_queue<TreeNode<T>*,vector<TreeNode<T>* >,cmp<T> > pri_que;
  51.     T *iter = begin;
  52.     TreeNode<T>* pNode;
  53.     TreeNode<T>* pf = NULL;
  54.     while(iter != end)
  55.     {
  56.         pNode = new TreeNode<T>;
  57.         pNode->data = *iter++;
  58.         pNode->pfather = pf;
  59.         pri_que.push(pNode);
  60.     }
  61.     TreeNode<T>* plchild;
  62.     TreeNode<T>* prchild;
  63.     while(pri_que.size() > 1)//取两个小的合并
  64.     {
  65.         //cout<<static_cast<TreeNode<T>* >(pri_que.top())->data<<endl;
  66.         //pri_que.pop();
  67.         plchild = pri_que.top();
  68.         pri_que.pop();
  69.         prchild = pri_que.top();
  70.         pri_que.pop();
  73.         pNode = new TreeNode<T>;
  74.         pNode->plchild = plchild;
  75.         pNode->prchild = prchild;
  76.         pNode->data = plchild->data + prchild->data;
  79.         pri_que.push(pNode);
  80.     }
  83.     pNode = pri_que.top();
  84.     pri_que.pop();
  85.     return pNode;
  86. }
  89. template<typename T>
  90. struct mydata
  91. {
  92.     mydata(){}
  93.     mydata(int i):freq(i)
  94.     {
  97.     }
  98.     string coded;
  99.     int freq;
  100.     T data;
  103.     bool operator<(const mydata& rhs)
  104.     {
  105.         return freq < rhs.freq;
  106.     }
  109.     mydata operator+(mydata& rhs)
  110.     {
  111.         return mydata(freq + rhs.freq);
  112.     }
  113. };
  116. template<typename T,typename U>
  117. void BFS(T* root, mydata<U>* data) //BFS 将叶子节点的编码，提到data指向的数据
  118. {
  119.     queue<T*> que;
  120.     que.push(root);
  123.     T* pT = NULL;
  124.     while(!que.empty())
  125.     {
  126.         pT = que.front();
  127.         //cout<<pT->data.freq<<endl;
  128.         que.pop();
  131.         if(pT->plchild != NULL)
  132.             que.push(pT->plchild);
  133.         if(pT->prchild != NULL)
  134.             que.push(pT->prchild);
  135.         if(pT->plchild == NULL || pT->prchild == NULL)// leaf 提取叶子节点的编码
  136.         {
  137.             //cout<<(pT->data).data<<":"<<(pT->data).coded<<endl;
  138.             mydata<U>* pd = data;
  139.             while((pT->data).data != pd->data)
  140.                 pd++;
  141.             assert(pd->data == (pT->data).data);
  142.             pd->coded = (pT->data).coded;
  143.         }
  144.     }
  145. }
  148. const int MAXLEN = 20;
  149. char path[MAXLEN] = {0};
  150. template<typename T>
  151. void DFS(T* root,int deep = -1, char a = \'-\')  //DFS 得到叶子节点的编码
  152. {
  153.     if(root == NULL)
  154.         return;
  157.     if(a != \'-\')
  158.         path[deep] = a;
  161.     if(root->plchild == NULL || root->prchild == NULL)//leaf
  162.         (root->data).coded = string(path,path + deep + 1);
  165.     if(root->plchild != NULL)
  166.         DFS(root->plchild, deep + 1, \'0\');
  167.     if(root->prchild != NULL)
  168.         DFS(root->prchild, deep + 1, \'1\');
  169. }
  172. template<typename T>
  173. class Huffman
  174. {
  175. public:
  176.     void Coded(string& coded);
  177.     void DeCode(const string& codedstr,string& decodestr);
  178.     void InputData(T* begin,T* end);
  181. private:
  182.     string FindVal(char c);
  183.     void m_CalcFreq(T* begin, T* end);
  184.     TreeNode<mydata<T> > *root;
  185.     mydata<T>* data;
  186.     int data_size;
  187.     
  188.     T* m_begin;
  189.     T* m_end;
  190.     //string codedstr;
  193. };
  196. template<typename T>
  197. void Huffman<T>::InputData(T* begin, T* end)
  198. {
  199.     this->m_begin = begin;
  200.     this->m_end = end;
  201.     m_CalcFreq(begin, end);
  204. }
  207. template<typename T>
  208. void Huffman<T>::m_CalcFreq(T* begin, T* end)
  209. {
  212.     int len = end - begin;
  213.     //data_size = len;
  214.     if(len == 0)
  215.         return;
  218.     map<T,int> countMap;
  219.     map<T,int>::iterator mapIter = countMap.begin();
  220.     T *pT = begin;
  221.     while(pT != end)
  222.     {
  223.         mapIter = countMap.find(*pT);
  224.         if(mapIter != countMap.end())
  225.             ++mapIter->second;
  226.         else
  227.         {
  228.             countMap.insert(make_pair(*pT,1));
  229.         }
  230.         pT++;
  231.     }
  234.     data_size = countMap.size();
  235.     data = new mydata<T>[data_size];
  236.     int i = 0;
  237.     for (mapIter = countMap.begin(); mapIter != countMap.end(); ++mapIter)
  238.     {
  239.         data[i].data = mapIter->first;        
  240.         data[i].freq = mapIter->second;
  241.         i++;
  242.     }
  245. }
  248. template<typename T>
  249. void Huffman<T>::Coded(string& coded)
  250. {
  251.     root = MakeHuffmanTree(data,data + data_size);
  252.     DFS(root);
  255.     BFS(root,data);
  258.     cout<<"code:"<<endl;
  259.     for (int i = 0; i < data_size; ++i)
  260.     {
  261.         cout<<data[i].data<<":"<<data[i].coded<<endl;
  262.     }
  265.     
  266.     T *begin = m_begin;
  267.     while (begin != m_end)
  268.     {
  269.         coded += FindVal(*begin);
  270.         begin++;
  271.     }
  272.     //string subcode = 
  277. }
  280. template<typename T>
  281. void Huffman<T>::DeCode(const string& codedstr,string& decodestr)
  282. {
  283.     string::const_iterator iter = codedstr.begin();
  284.     TreeNode<mydata<T> >* curNode = root;
  285.     while (iter != codedstr.end())
  286.     {
  287.         if (curNode->plchild == NULL || curNode->prchild == NULL)
  288.         {
  289.             decodestr += (curNode->data).data;
  290.             curNode = root;
  291.             continue;
  292.         }
  293.         if (*iter == \'0\')
  294.             curNode = curNode->plchild;
  295.         
  296.         if(*iter == \'1\')
  297.             curNode = curNode->prchild;
  300.         iter++;
  301.     }
  302. }
  305. template<typename T>
  306. string Huffman<T>::FindVal(char c)
  307. {
  308.     for (int i = 0; i < data_size ; ++i)
  309.     {
  310.         if (c != data[i].data)
  311.             continue;
  312.         return data[i].coded;
  313.     }
  314.     return string();
  315. }
  318. int main()
  319. {
  320.     //mydata<char> *pdata = new mydata<char>[4];
  321.     //pdata[0].data = \'a\';
  322.     //pdata[0].freq = 7;
  323.     //pdata[1].data = \'b\';
  324.     //pdata[1].freq = 5;
  325.     //pdata[2].data = \'c\';
  326.     //pdata[2].freq = 2;
  327.     //pdata[3].data = \'d\';
  328.     //pdata[3].freq = 4;
  329.     ////int a[12]={14,10,56,7,83,22,36,91,3,47,72,0};
  330.     //TreeNode<mydata<char> >* pihuffmanTree = MakeHuffmanTree(pdata, pdata + 4);
  333.     //DFS(pihuffmanTree);
  336.     //BFS(pihuffmanTree);
  339.     //string str = "cbcddddbbbbaaaaaaa";
  340.     char *pmystr = "cbcddddbbbbaaaaaaa";
  343.     Huffman<char> h;
  344.     h.InputData(pmystr, pmystr + 18);
  347.     cout<<"originstr: "<<pmystr<<endl;
  350.     string coded;
  351.     h.Coded(coded);
  354.     cout<<"coded: "<<coded<<endl;
  357.     string decode;
  358.     h.DeCode(coded,decode);
  359.     cout<<"decode: "<<decode<<endl;
  362.     return 0;
  363. }




 





	













    































							

   
版权声明：本文为Honkee原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。



本文链接：https://www.cnblogs.com/Honkee/p/3780517.html