哈夫曼树
给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
哈夫曼编码(Huffman Coding)
又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。
应用举例
哈夫曼树─即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩。 在计算机信息处理中,“哈夫曼编码”是一种一致性编码法(又称“熵编码法”),用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。这张编码表的特殊之处在于,它是根据每一个源字符出现的估算概率而建立起来的(出现概率高的字符使用较短的编码,反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的)。
构造Huffman tree
过程:
1、输入字符关键字以及对应的频率。
2、根据关键字的频率构造最优二叉树
(1)借助于STL的优先队列 :priority_queue
(2)构造最优二叉搜索树:在有了最优二叉搜索树的帮助之后,对于构建搜索树很容易。上面的图很清楚的讲解了构造的过程,每次取出频率最小的两个形成一个子树,将其频率相加之后再放入优先队列之中,直到队列中元素个数为0。在操作过程中需要遵守最优二叉搜索树的定义,左孩子小于父节点,右孩子大于父节点。
(3)递归遍历二叉树:遍历中只需要记住,向左遍历那么前缀码为0,向右为1.
亲测代码:
1 #include <bits/stdc++.h>
2 #define max_size 10010
3 char c[max_size];
4 double f[max_size];
5
6 using namespace std;
7 typedef struct node
8 {
9 char ch;
10 double freq;
11 node *lchild;
12 node *rchild;
13 node(char c=0,double f=0,node *l=NULL,node *r=NULL):
14 ch(c),freq(f),lchild(l),rchild(r) {}
15 };
16 typedef struct cmp
17 {
18 bool operator()(node*&a,node*&b)
19 {
20 return a->freq>b->freq;
21 }
22 };
23 node* createTree(int n)
24 {
25 priority_queue<node*,vector<node*>,cmp>que;
26 for(int i=1; i<=n; i++)
27 {
28 cin>>c[i]>>f[i];
29 que.push(new node(c[i],f[i]));
30 }
31 while(que.size()>1)
32 {
33 node *l=que.top();
34 que.pop();
35 node *r=que.top();
36 que.pop();
37 node *newnode=new node(0,l->freq+r->freq,l,r);
38 que.push(newnode);
39 }
40 return que.top();
41 }
42
43 void printInfo(const node *tree,string code)
44 {
45 if(tree->lchild==NULL&&tree->rchild==NULL)
46 {
47 cout<<tree->ch<<":"<<code<<" ";
48 return;
49 }
50 if(tree->lchild!=NULL)printInfo(tree->lchild,code+'0');
51 if(tree->rchild!=NULL)printInfo(tree->rchild,code+'1');
52 }
53 void deleteTree(node *tree)
54 {
55 if(tree->lchild!=NULL)deleteTree(tree->lchild);
56 if(tree->rchild!=NULL)deleteTree(tree->rchild);
57 delete(tree);
58 }
59 int main()
60 {
61 int n;
62 priority_queue<node*,vector<node*>,greater<node*> >que;
63 while(~scanf("%d",&n))
64 {
65 node *tree=createTree(n);
66 printf("Huffman code:n");
67 printInfo(tree,"");
68 }
69 }
View Code
输入数据以及运行结果:
原文链接: https://www.cnblogs.com/zpfbuaa/p/4957691.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/224376
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!