一、簡介

哈夫曼樹又稱為最優樹。


1、路徑和路徑長度


在一棵樹中，從一個結點往下可以達到的孩子或子孫結點之間的通路，稱為路徑。通路中分支的數目稱為路徑長度。若規定根結點的層數為1，則從根結點到第L層結點的路徑長度為L-1。


2、結點的權及帶權路徑長度


若將樹中結點賦給一個有著某種含義的數值，則這個數值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。


3、樹的帶權路徑長度


樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL


二、哈夫曼樹的應用


1、哈夫曼編碼


在數據通信中，需要將傳送的文字轉換成二進制的字符串，用0，1碼的不同排列來表示字符。例如，需傳送的報文為“AFTER DATA EAR ARE ART AREA”，這里用到的字符集為“A，E，R，T，F，D”，各字母出現的次數為{8，4，5，3，1，1}。現要求為這些字母設計編碼。要區別6個字母，最簡單的二進制編碼方式是等長編碼，固定采用3位二進制，可分別用000、001、010、011、100、101對“A，E，R，T，F，D”進行編碼發送，當對方接收報文時再按照三位一分進行譯碼。顯然編碼的長度取決報文中不同字符的個數。若報文中可能出現26個不同字符，則固定編碼長度為5。然而，傳送報文時總是希望總長度盡可能短。在實際應用中，各個字符的出現頻度或使用次數是不相同的，如A、B、C的使用頻率遠遠高于X、Y、Z，自然會想到設計編碼時，讓使用頻率高的用短碼，使用頻率低的用長碼，以優化整個報文編碼。


為使不等長編碼為前綴編碼(即要求一個字符的編碼不能是另一個字符編碼的前綴)，可用字符集中的每個字符作為葉子結點生成一棵編碼二叉樹，為了獲得傳送報文的最短長度，可將每個字符的出現頻率作為字符結點的權值賦予該結點上，求出此樹的最小帶權路徑長度就等于求出了傳送報文的最短長度。因此，求傳送報文的最短長度問題轉化為求由字符集中的所有字符作為葉子結點，由字符出現頻率作為其權值所產生的哈夫曼樹的問題。利用哈夫曼樹來設計二進制的前綴編碼，既滿足前綴編碼的條件，又保證報文編碼總長最短。

哈夫曼靜態編碼：它對需要編碼的數據進行兩遍掃描：第一遍統計原數據中各字符出現的頻率，利用得到的頻率值創建哈夫曼樹，并必須把樹的信息保存起來，即把字符0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，（用4Bytes的長度存儲頻率值，頻率值的表示范圍為0--2^32-1，這已足夠表示大文件中字符出現的頻率了）以便解壓時創建同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，并把編碼后得到的碼字存儲起來。


哈夫曼動態編碼：動態哈夫曼編碼使用一棵動態變化的哈夫曼樹，對第t+1個字符的編碼是根據原始數據中前t個字符得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字符，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字符所需的時間與該字符的編碼長度成正比，所以動態哈夫曼編碼可實時進行。


2、哈夫曼譯碼

在通信中，若將字符用哈夫曼編碼形式發送出去，對方接收到編碼后，將編碼還原成字符的過程，稱為哈夫曼譯碼。

三、二叉樹實現哈夫曼編碼


/*************************
? ? ? ? Filename :Linkqueue.h
? ? ? ? **************************/


typedef struct _tree_
? ? ? ? {
? ? ? ? ? ? ? ? char ch;
? ? ? ? ? ? ? ? int weight;
? ? ? ? ? ? ? ? char code[10];
? ? ? ? ? ? ? ? struct _tree_ *next, *lchild, *rchild;
? ? ? ? } bitree;


typedef bitree *datatype;


typedef struct _node_
? ? ? ? {
? ? ? ? ? ? ? ? datatype data;
? ? ? ? ? ? ? ? ?struct _node_ *next;
? ? ? ? } listnode;


typedef struct
? ? ? ? ?{
? ? ? ? ? ? ? ? listnode *front;
? ? ? ? ? ? ? ? ?listnode *rear;
? ? ? ? } linkqueue;


linkqueue *CreateEmptyLinkqueue();


int EmptyLinkqueue(linkqueue *q);


void EnQueue(linkqueue *q, datatype x);


datatype DeQueue(linkqueue *q);


/*************************
? ? ? ? Filename :Huffman.c
? ? ? ? **************************/


＃i nclude
? ? ? ? ＃i nclude
? ? ? ? ＃i nclude
? ? ? ? ＃i nclude "linkqueue.h"


bitree *CreateEmptyList()
? ? ? ? {
? ? ? ? bitree *h;
? ? ? ? h = (bitree *)malloc(sizeof(bitree));
? ? ? ? h->next = h->lchild = h->rchild = NULL;
? ? ? ? return h;
? ? ? ? }


void InsertList(bitree *h, bitree *q)
? ? ? ? {
? ? ? ? ? ? ? ? while (h->next && (h->next->weight < q->weight))
? ? ? ? {
? ? ? ? ? ? ? ? h = h->next;
? ? ? ? }
? ? ? ? ? ? ? ? q->next = h->next;
? ? ? ? ? ? ? ? h->next = q;
? ? ? ? ? ? ? ? return;
? ? ? ? ?}


void VisitList(bitree *h)
? ? ? ? {
? ? ? ? ? ? ? ? h = h->next;
? ? ? ? ? ? ? ? while ( h )
? ? ? ? {
? ? ? ? ? ? ? ? printf("%d ", h->weight);
? ? ? ? ? ? ? ? h = h->next;
? ? ? ? }
? ? ? ? ? ? ? ? printf("n");
? ? ? ? ? ? ? ? return;
? ? ? ? }


void CreateHaffmanTree(bitree *h)
? ? ? ? {
? ? ? ? ? ? ? ? bitree *p;
? ? ? ? ? ? ? ? ?while (h->next && h->next->next)
? ? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ? ? ? p = (bitree *)malloc(sizeof(bitree));
? ? ? ? ? ? ? ? ? ? ? ? p->lchild = h->next;
? ? ? ? ? ? ? ? ? ? ? ? ?p->rchild = h->next->next;
? ? ? ? ? ? ? ? ? ? ? ? ?p->weight = p->lchild->weight + p->rchild->weight;
? ? ? ? ? ? ? ? ? ? ? ? ?h->next = p->rchild->next;
? ? ? ? ? ? ? ? ? ? ? ? ?InsertList(h, p);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? return;
? ? ? ? }


void NoOrder(bitree *root)
? ? ? ? {
? ? ? ? ? ? ? ? bitree *p;
? ? ? ? ? ? ? ? ?linkqueue *queue;
? ? ? ? ? ? ? ? queue = CreateEmptyLinkqueue();
? ? ? ? ? ? ? ? EnQueue(queue, root);
? ? ? ? ? ? ? ? while ( !EmptyLinkqueue(queue) )
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ?p = DeQueue(queue);
? ? ? ? ? ? ? ? ? ? ? ? if ((p->lchild == NULL) && (p->rchild == NULL))
? ? ? ? ? ? ? ? ? ? ? ? {?
? ? ? ? ? ? ? ? ? ? ? ? printf("%c[%2d] : %sn", p->ch, p->weight, p->code);
? ? ? ? ? ? ? ? ? ? ? ? ?continue;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if (p->lchild)?
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ?strcpy(p->lchild->code, p->code);
? ? ? ? ? ? ? ? ? ? ? ? strcat(p->lchild->code, "0");
? ? ? ? ? ? ? ? ? ? ? ? ?EnQueue(queue, p->lchild);
? ? ? ? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? ? ? ? ? if (p->rchild)?
? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? strcpy(p->rchild->code, p->code);
? ? ? ? ? ? ? ? ? ? ? ? strcat(p->rchild->code, "1");
? ? ? ? ? ? ? ? ? ? ? ? ?EnQueue(queue, p->rchild);
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? return;
? ? ? ? }


int main(int argc, char *argv[])
? ? ? ? {
? ? ? ? ? ? ? ? int i, value;
? ? ? ? ? ? ? ? char ch;
? ? ? ? ? ? ? ? bitree *h, *p;
? ? ? ? ? ? ? ? h = CreateEmptyList();
? ? ? ? ? ? ? ? while (scanf("%c %dn", &ch, &value) == 2)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? p = (bitree *)malloc(sizeof(bitree));
? ? ? ? ? ? ? ? ? ? ? ? ?p->ch = ch;
? ? ? ? ? ? ? ? ? ? ? ? p->weight = value;
? ? ? ? ? ? ? ? ? ? ? ? p->code[0] = '';
? ? ? ? ? ? ? ? ? ? ? ? p->lchild = p->rchild = NULL;
? ? ? ? ? ? ? ? ? ? ? ? InsertList(h, p);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? VisitList(h);
? ? ? ? ? ? ? ? CreateHaffmanTree(h);
? ? ? ? ? ? ? ? NoOrder(h->next);
? ? ? ? ? ? ? ? return 0;
? ? ? ? }


/*************************
? ? ? ? Filename :Linkqueue.c
? ? ? ? **************************/


＃i nclude
? ? ? ? ?＃i nclude
? ? ? ? ?＃i nclude "linkqueue.h"
? ? ? ? linkqueue *CreateEmptyLinkqueue()
? ? ? ? {
? ? ? ? ? ? ? ? linkqueue *q;
? ? ? ? ? ? ? ? q = (linkqueue *)malloc(sizeof(linkqueue));
? ? ? ? ? ? ? ? q->front = q->rear = (listnode *)malloc(sizeof(listnode));
? ? ? ? ? ? ? ? ?q->front->next = NULL;
? ? ? ? ? ? ? ? return q;
? ? ? ? }


int EmptyLinkqueue(linkqueue *q)
? ? ? ? ?{
? ? ? ? ? ? ? ? ?return (q->front == q->rear);
? ? ? ? }


void EnQueue(linkqueue *q, datatype r)
? ? ? ? {
? ? ? ? ? ? ? ? listnode *p;
? ? ? ? ? ? ? ? p = (listnode *)malloc(sizeof(listnode));
? ? ? ? ? ? ? ? p->data = r;
? ? ? ? ? ? ? ? p->next = NULL;
? ? ? ? ? ? ? ? q->rear->next = p;
? ? ? ? ? ? ? ? q->rear = p;
? ? ? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? datatype DeQueue(linkqueue *q)
? ? ? ? {
? ? ? ? ? ? ? ?listnode *p;
? ? ? ? ? ? ? ? p = q->front;
? ? ? ? ? ? ? ? q->front = p->next;
? ? ? ? ? ? ? ? free(p);
? ? ? ? ? ? ? ? return q->front->data;
? ? ? ? }