哈夫曼树的构造(哈夫曼算法)
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 }