[TOC]
# 前綴碼
對每一個字符規定一個0,1串作為其代碼，并要求任一字符的代碼都不是其他字符的前綴。這種編碼稱為前綴碼。
譯碼過程需要方便地取出編碼的前綴，因此需要一種表示前綴碼的合適的數據結構。為此，我們選用了二叉樹。
# 哈夫曼樹
在一般的數據結構的書中，樹的那章后面，著者一般都會介紹一下哈夫曼(HUFFMAN)樹和哈夫曼編碼。哈夫曼是哈夫曼樹的一個應用。哈夫曼編碼應用廣泛，如JPEG中就應用了哈夫曼編碼。
首先介紹什么是哈夫曼樹。哈夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度
為葉結點的層數）。樹的帶權路徑長度記為WPL= (W1\*L1+W2\*L2+W3\*L3+...+Wn\*Ln)，N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li(i=1,2,...n)。可以證明哈夫曼樹的WPL是最小的。
* **哈夫曼編碼步驟**：
1. 對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉樹Ti中只有一個權值為Wi的根結點，它的左右子樹均為空。（為方便在計算機上實現算法，一般還要求以Ti的權值Wi的升序排列。）
2. 在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。
3. 從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。
4. 重復二和三兩步，直到集合F中只有一棵二叉樹為止。
簡易的理解就是，假如我有A,B,C,D,E五個字符，出現的頻率（即權值）分別為5,4,3,2,1,那么我們第一步先取兩個最小權值作為左右子樹構造一個新樹，即取1，2構成新樹，其結點為1+2=3，如圖：
虛線為新生成的結點，第二步再把新生成的權值為3的結點放到剩下的集合中，所以集合變成{5,4,3,3}，再根據第二步，取最小的兩個權值構成新樹，如圖：
再依次建立哈夫曼樹，如下圖：
其中各個權值替換對應的字符即為下圖：
所以各字符對應的編碼為：A->11,B->10,C->00,D->011,E->010
# 分析
# 代碼實現-1
```
#include <stdio.h>
#include <string.h>
typedef struct node_t {
struct node_t *left,*right;
int freq;
char c;
} *node;
struct node_t pool[256] = {{0}};
node qqq[255],*q=qqq-1;
int n_nodes = 0,qend = 1;
char *code[128] = {0},buf[1024];
node new_node(int freq,char c,node a,node b) {
node n = pool + n_nodes++;
if(freq) n->c = c,n->freq = freq;
else {
n->left = a,n->right = b;
n->freq = a->freq + b->freq;
}
return n;
}
void qinsert(node n) {
int j,i=qend++;
while((j = i/2)) {
if(q[j]->freq <= n->freq) break;
q[i] = q[j],i=j;
}
q[i] = n;
}
node qremove() {
int i,l;
node n = q[i=1];
if(qend < 2) return 0;
qend--;
while((l=i*2) < qend) {
if(l+1 < qend && q[l+1]->freq < q[l]->freq) l++;
q[i] = q[l]; i = l;
}
q[i] = q[qend];
return n;
}
/* walk the tree and put 0s and 1s */
void build_code(node n, char *s, int len)
{
static char *out = buf;
if (n->c) {
s[len] = 0;
strcpy(out, s);
code[n->c] = out;
out += len + 1;
return;
}
s[len] = '0'; build_code(n->left, s, len + 1);
s[len] = '1'; build_code(n->right, s, len + 1);
}
void init(const char *s) {
int i,freq[128] = {0};
char c[16];
while(*s) freq[(int)*s++]++;
for(i = 0; i < 128 ; i++) {
if(freq[i]) qinsert(new_node(freq[i],i,0,0));
}
while(qend > 2) {
qinsert(new_node(0,0,qremove(),qremove()));
}
build_code(q[1],c,0);
}
void encode(const char *s, char *out)
{
while (*s) {
strcpy(out, code[*s]);
out += strlen(code[*s++]);
}
}
void decode(const char *s, node t)
{
node n = t;
while (*s) {
if (*s++ == '0') n = n->left;
else n = n->right;
if (n->c) putchar(n->c), n = t;
}
putchar('\n');
if (t != n) printf("garbage input\n");
}
int main(void)
{
int i;
const char *str = "thisis", buf[1024];
init(str);
for (i = 0; i < 128; i++)
if (code[i]) printf("'%c': %s\n", i, code[i]);
encode(str, buf);
printf("encoded: %s\n", buf);
printf("decoded: ");
decode(buf, q[1]);
return 0;
}
```
