Huffman Tree
Huffman树是一种为了节省空间的更具字符的频率而构成的一种树。
| 字符 | a | b | c | d | e | f | g |
|---|---|---|---|---|---|---|---|
| 频率 | 5 | 4 | 2 | 1 | 2 | 1 | 4 |
| 编码 | 10 | 111 | 000 | 0010 | 110 | 0011 | 01 |
此树思路是利用优先队列和向后扩展节点来满足新增节点然后dfs对树进行遍历。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn=1e5+10;
4 int n,root;
5 int cnt=0;
6 struct node{
7 int num,dig; string str;
8 int left,right;
9 node():str(""),dig(0),left(NULL),right(NULL){}
10 bool operator <(const node &x)const{return x.dig<dig;}
11 }a[maxn];
12 priority_queue<node> que;
13 void print(int point,string ans)
14 {
15 if(!a[point].left&&!a[point].right){
16 cout<<a[point].str<<" "<<ans<<'\n';
17 return;
18 }
19 print(a[point].left,ans+"0");
20 print(a[point].right,ans+"1");
21 }
22 int main()
23 {
24 scanf("%d",&n);
25 for(int i=1;i<=n;i++){
26 cin>>a[i].str>>a[i].dig;
27 a[i].num=i;
28 que.push(a[i]);
29 }
30 while(!que.empty())
31 {
32 node temp1=que.top(); que.pop();
33 node temp2=que.top(); que.pop();
34 a[n+(++cnt)].num=n+(cnt); a[n+cnt].dig=temp1.dig+temp2.dig;
35 a[n+cnt].left=temp1.num; a[n+cnt].right=temp2.num;
36 if(que.empty()){root=n+cnt; break;}
37 que.push(a[n+cnt]);
38 }
39 print(root,"");
40 return 0;
41 }
