霍夫曼編碼是一種被廣泛應用而且非常有效的數據壓縮技術，根據待壓縮數據的特征，一個可壓縮掉20%~90%。這里考慮的數據指的是字符串序列。要理解霍夫曼編碼，先要理解霍夫曼樹，即最優二叉樹，是一類帶權路徑長度最短的樹。
路徑是指從樹中一個結點到另一個結點之間的通路，路徑上的分支數目稱為路徑長度。
樹的路徑長度是從樹根到每一個葉子之間的路徑長度之和。結點的帶權路徑長度為從該結點到樹根之間的路徑長度與該結點權的乘積，樹的帶權路徑長度為樹中所有葉子結點的帶權路徑長度之和.
霍夫曼樹是指所有葉子結點的二叉樹中帶權路徑長度最小的二叉樹.
當給定了n個葉子結點的權值后，構造出的最優二叉樹的結點數目m就確定了，即m=2n-1,所以可用一維結構數組來存儲最優二叉樹
#define MAXLEAFNUM 50 /*最優二叉樹中最大葉子樹目*/
struct node{
char ch; /*當前結點表示的字符，對于非葉子結點，此域不用*/
int weight; /*當前結點的權值*/
int parent; /*當前結點的父結點的下標，為0時表示無父結點*/
int lchild,rchild; /*當前結點的左，右孩子結點的下標，為0時表示無孩子結點*/
}HuffmanTree[2 * MAXLEAFNUM];
typedef char *HuffmanCode[MAXLEAFNUM + 1]；
/*創建最優二叉樹*/
void createHTree(HuffmanTree HT, char *c, int *w, int n)
{
/*數組c[0..n-1]和w[0..n-1]存放了n個字符及其概率，構造霍夫樹HT*/
int i, s1, s2;
if (n <= 1)
return;
/*根據n個權值構造n棵只有根結點的二叉樹*/
for (i=1; i<=n; i++)
{
HT[i].ch = c[i-1];
HT[i].weight = w[i-1];
HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
}
for (; i<2*n; ++i)
{
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
/*構造霍夫曼樹*/
for (i=n+1; i<2*n; i++)
{
/*從HT[1..i-1]中選擇parent為0且weight最小的兩棵樹，其序號為s1和s2*/
select(HT,i-1,s1,s2);
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
復制代碼
霍夫曼算法(構造靍夫曼樹)
對應于霍夫曼樹的算法也叫做霍夫曼算法。此算法的思想是：
（1）設給定的一組權值為{W1，W2，W3，……Wn}，據此生成森林F={T1，T2，T3，……Tn},F 中的每棵二叉樹只有一個帶權為W1的根節點（i=1，2，……n）。
?。?/span>2）在F中選取兩棵根節點的權值最小和次小的二叉樹作為左右構造一棵新的二叉樹，新二叉樹根節點的權值為其左、右子樹根節點的權值之和。
?。?/span>3）在F中刪除這兩棵最小和次小的二叉樹，同時將新生成的二叉樹并入森林中。
?。?/span>4）重復（2）（3）過程直到F中只有一棵二叉樹為止。
霍夫曼樹的應用非常廣，在不同的應用中葉子節點的權值可以作不同的解釋?；舴蚵鼧鋺糜谛畔⒕幋a中，權值可以看成某個符號出現的頻率；應用到判定過程中，權值可以看成某類數據出現的頻率；應用到排序過程中，權值可以看成是已排好次序而等待合并的序列長度等。
應用霍夫曼編碼
假設有一個包含100 000個字符的數據文件要壓縮存儲。各字符在該文件中的出現頻度見表1。僅有6種不同字符出現過，字符a出現了45000次。
a b c d e f
頻度（千字） 45 13 12 16 9 5
固定代碼字 000 001 010 011 100 101
變長代碼字 0 101 100 111 1101 1100
表1 一個字符編碼問題。大小為100 000個字符的一個數據文件僅包含字符a~f，每個字符出現的頻度如表中所示。如果對每個字符賦予一個三位的編碼，則該文件可被編碼為300000位。如果利用表中的可變長度編碼，該文件可被編碼為224000位。
可以用很多種方式來表示這樣一個文件。采用固定長度編碼，則需要三位二進制數字來表示六個字符：a=000，b=001，…，f=101。這種方法需要300 000來對整個原文件編碼。