一、簡(jiǎn)介

哈夫曼樹又稱為最優(yōu)樹。


1、路徑和路徑長(zhǎng)度


在一棵樹中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或子孫結(jié)點(diǎn)之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長(zhǎng)度。若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)-1。


2、結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長(zhǎng)度


若將樹中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積。


3、樹的帶權(quán)路徑長(zhǎng)度


樹的帶權(quán)路徑長(zhǎng)度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記為WPL


二、哈夫曼樹的應(yīng)用


1、哈夫曼編碼


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


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

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


哈夫曼動(dòng)態(tài)編碼：動(dòng)態(tài)哈夫曼編碼使用一棵動(dòng)態(tài)變化的哈夫曼樹，對(duì)第t+1個(gè)字符的編碼是根據(jù)原始數(shù)據(jù)中前t個(gè)字符得到的哈夫曼樹來(lái)進(jìn)行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個(gè)字符，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒(méi)有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個(gè)字符所需的時(shí)間與該字符的編碼長(zhǎng)度成正比，所以動(dòng)態(tài)哈夫曼編碼可實(shí)時(shí)進(jìn)行。


2、哈夫曼譯碼

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

三、二叉樹實(shí)現(xiàn)哈夫曼編碼


/*************************
? ? ? ? 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;
? ? ? ? }