哈夫曼树的构造(哈夫曼算法)
1.根据给定的n个权值{w1,w2,…,wn}构成二叉树集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树为空.
2.在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为左右子树根结点的权值之和.
3.在F中删除这两棵树,同时将新的二叉树加入F中.
4.重复2、3,直到F只含有一棵树为止.(得到哈夫曼树)

 

每次选取最小的两个值可以通过优先队列实现，使用优先队列可以使得代码非常简洁。

 

建立了哈夫曼树后，可以直接在哈夫曼树上跑一遍得到哈夫曼编码

 

 1 #include <iostream>
 2 #include <queue>
 3 
 4 using namespace std;
 5 const int maxn = 1e3 + 7;
 6 int n, code[maxn], ans[maxn][maxn];
 7 typedef struct node {
 8     int weight, id;
 9     struct node *lson, *rson;
10 } *pnode;
11 
12 struct cmp {
13     bool operator()(pnode f1, pnode f2) // 重载括号
14     {
15         return (*f1).weight > (*f2).weight; // 等同于less
16     }
17 };
18 
19 priority_queue<pnode, vector<pnode>, cmp> que;
20 
21 pnode get_head() {
22     for (int i = 1; i <= n; ++i) {
23         pnode temp = NULL;
24         temp = (pnode) malloc(sizeof(node));
25         temp->id = -1;
26         temp->lson = que.top();
27         que.pop();
28         temp->rson = que.top();
29         que.pop();
30         temp->weight = temp->lson->weight + temp->rson->weight;
31         printf("temp->lson->weight = %d temp->rson->weight = %d\n", temp->lson->weight, temp->rson->weight);
32         if (que.empty()) return temp;
33         que.push(temp);
34     }
35 }
36 
37 void get_ans(pnode h, int dep) {
38     if (h->lson == NULL && h->rson == NULL) {
39         int idx = h->id;
40         for (int i = 0; i < dep; ++i)
41             ans[idx][i] = code[i];
42         ans[idx][maxn - 1] = dep;
43         printf("dep = %d h->weight = %d\n", dep, h->weight);
44         return;
45     }
46     printf("h->lson->weight = %d h->rson->weight = %d\n", h->lson->weight, h->rson->weight);
47     code[dep] = 0;
48     get_ans(h->lson, dep + 1);
49     code[dep] = 1;
50     get_ans(h->rson, dep + 1);
51 }
52 
53 int main() {
54     freopen("../in.txt", "r", stdin);
55     while (!que.empty()) que.pop();
56     for (int i = 0; i < maxn; ++i) code[i] = 1;
57     cin >> n;
58     for (int i = 1; i <= n; ++i) {
59         pnode cnt = NULL;
60         cnt = (pnode) malloc(sizeof(node));
61         cnt->lson = cnt->rson = NULL;
62         cnt->id = i;
63         cin >> cnt->weight;
64         que.push(cnt);
65     }
66     pnode head = get_head();
67     printf("total = %d\n", head->weight);
68     get_ans(head, 0);
69     for (int i = 1; i <= n; ++i) {
70         for (int j = 0; j < ans[i][maxn - 1]; ++j)
71             printf("%d", ans[i][j]);
72         printf("\n");
73     }
74     return 0;
75 }

View Code