Huffman coding tree(最小堆实现）
#include <iostream>#include <string>#include <algorithm>#include <cstdio>#include <cstring>#define maxn 10000using namespace std;int path[100];int l = 0;typedef struct heap_factor { int val; int flag ; //represent the leaf struct btnode *me;}heap_factor;typedef struct btnode { int v; int bit; char data; struct btnode *lchild; struct btnode *rchild;}btnode;heap_factor p[maxn];int len = 0, n;void heap_insert(heap_factor k) { int t = ++len; p[t] = k; while(t>1) { if(p[t/2].val > p[t].val) { swap(p[t], p[t/2]); t = t/2; } else { break; } }}void heap_pop() { int t = 1; p[t] = p[len--]; while(t*2 <= len) { int k = t * 2; if(k < len && p[k].val > p[k+1].val) { ++k; } if(p[t].val > p[k].val) { swap(p[t], p[k]); t = k; } else { break; } }}btnode *new_btnode(int x){ btnode *p = (btnode *)malloc(sizeof(btnode)); if(p) { p->v = x; p->lchild = NULL; p->rchild = NULL; } return p;}void init() { for(int i = 1; i <= n; i++) { p[i].flag = 0; } memset(path, -1, sizeof(path));}int pre_order(btnode *root) { if(root->lchild== NULL && root->rchild == NULL) { path[l++] = root->bit; printf("%d: ", root->v); for(int k = 1; k < l; k++) { printf("%d", path[k]); } printf("\n"); l = l-1; return 0; } path[l++] = root->bit; pre_order(root->lchild); pre_order(root->rchild); if(root->lchild != NULL & root->rchild != NULL) { l = l-1; } return 0;}int main(){ init(); scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &p[i].val); heap_insert(p[i]); } btnode *pp, *q, *root; heap_factor a, b; while(len >= 2) { a = p[1]; heap_pop(); b = p[1]; heap_pop(); if(a.flag == 0) { pp= new_btnode(a.val); pp-> bit = 0; } else if(a.flag == 1) { pp = a.me; pp->bit = 0; } if(b.flag == 0) { q = new_btnode(b.val); q->bit = 1; } else if(b.flag == 1) { q = b.me; q->bit = 1; } root = new_btnode(a.val+b.val); root -> lchild = pp; root ->rchild = q; a.flag = 1; a.val = a.val + b.val; a.me = root; heap_insert(a); } pre_order(root); return 0;}/************************input:83 4 2 8 7 5 9 10*************************/