1、基本概念
a、路徑和路徑長(zhǎng)度
若在一棵樹(shù)中存在著一個(gè)結(jié)點(diǎn)序列 k1，k2，……，kj， 使得 ki是ki+1 的雙親（1<=i<j），則稱(chēng)此結(jié)點(diǎn)序列是從 k1 到 kj 的路徑。
從 k1 到 kj 所經(jīng)過(guò)的分支數(shù)稱(chēng)為這兩點(diǎn)之間的路徑長(zhǎng)度，它等于路徑上的結(jié)點(diǎn)數(shù)減1.
b、結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長(zhǎng)度
在許多應(yīng)用中，常常將樹(shù)中的結(jié)點(diǎn)賦予一個(gè)有著某種意義的實(shí)數(shù)，我們稱(chēng)此實(shí)數(shù)為該結(jié)點(diǎn)的權(quán)，(如下面一個(gè)樹(shù)中的藍(lán)色數(shù)字表示結(jié)點(diǎn)的權(quán))
結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度規(guī)定為從樹(shù)根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)上權(quán)的乘積。
c、樹(shù)的帶權(quán)路徑長(zhǎng)度
樹(shù)的帶權(quán)路徑長(zhǎng)度定義為樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，公式為：
其中，n表示葉子結(jié)點(diǎn)的數(shù)目，wi 和 li 分別表示葉子結(jié)點(diǎn) ki 的權(quán)值和樹(shù)根結(jié)點(diǎn)到 ki 之間的路徑長(zhǎng)度。
如下圖中樹(shù)的帶權(quán)路徑長(zhǎng)度 WPL = 9 x 2 + 12 x 2 + 15 x 2 + 6 x 3 + 3 x 4 + 5 x 4 = 122
d、哈夫曼樹(shù)
哈夫曼樹(shù)又稱(chēng)最優(yōu)二叉樹(shù)。它是 n 個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中，帶權(quán)路徑長(zhǎng)度 WPL 最小的二叉樹(shù)。
如下圖為一哈夫曼樹(shù)示意圖。
2、構(gòu)造哈夫曼樹(shù)
假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹(shù)有n個(gè)葉子結(jié)點(diǎn)。 n個(gè)權(quán)值分別設(shè)為 w1、w2、…、wn，則哈夫曼樹(shù)的構(gòu)造規(guī)則為：
(1) 將w1、w2、…，wn看成是有n 棵樹(shù)的森林(每棵樹(shù)僅有一個(gè)結(jié)點(diǎn))；
(2) 在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹(shù)合并，作為一棵新樹(shù)的左、右子樹(shù)，且新樹(shù)的根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和；
(3)從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)加入森林；
(4)重復(fù)(2)、(3)步，直到森林中只剩一棵樹(shù)為止，該樹(shù)即為所求得的哈夫曼樹(shù)。
如：對(duì) 下圖中的六個(gè)帶權(quán)葉子結(jié)點(diǎn)來(lái)構(gòu)造一棵哈夫曼樹(shù)，步驟如下：
注意：為了使得到的哈夫曼樹(shù)的結(jié)構(gòu)盡量唯一，通常規(guī)定生成的哈夫曼樹(shù)中每個(gè)結(jié)點(diǎn)的左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)。
具體算法如下：
//2、根據(jù)數(shù)組 a 中 n 個(gè)權(quán)值建立一棵哈夫曼樹(shù)，返回樹(shù)根指針 struct BTreeNode* CreateHuffman(ElemType a[], int n) { int i, j; struct BTreeNode **b, *q; b = malloc(n*sizeof(struct BTreeNode)); for (i = 0; i < n; i++) //初始化b指針數(shù)組，使每個(gè)指針元素指向a數(shù)組中對(duì)應(yīng)的元素結(jié)點(diǎn) { b[i] = malloc(sizeof(struct BTreeNode)); b[i]->data = a[i]; b[i]->left = b[i]->right = NULL; } for (i = 1; i < n; i++)//進(jìn)行 n-1 次循環(huán)建立哈夫曼樹(shù) { //k1表示森林中具有最小權(quán)值的樹(shù)根結(jié)點(diǎn)的下標(biāo)，k2為次最小的下標(biāo) int k1 = -1, k2; for (j = 0; j < n; j++)//讓k1初始指向森林中第一棵樹(shù)，k2指向第二棵 { if (b[j] != NULL && k1 == -1) { k1 = j; continue; } if (b[j] != NULL) { k2 = j; break; } } for (j = k2; j < n; j++)//從當(dāng)前森林中求出最小權(quán)值樹(shù)和次最小 { if (b[j] != NULL) { if (b[j]->data < b[k1]->data) { k2 = k1; k1 = j; } else if (b[j]->data < b[k2]->data) k2 = j; } } //由最小權(quán)值樹(shù)和次最小權(quán)值樹(shù)建立一棵新樹(shù)，q指向樹(shù)根結(jié)點(diǎn) q = malloc(sizeof(struct BTreeNode)); q->data = b[k1]->data + b[k2]->data; q->left = b[k1]; q->right = b[k2]; b[k1] = q;//將指向新樹(shù)的指針賦給b指針數(shù)組中k1位置 b[k2] = NULL;//k2位置為空 } free(b); //刪除動(dòng)態(tài)建立的數(shù)組b return q; //返回整個(gè)哈夫曼樹(shù)的樹(shù)根指針 }
3、哈夫曼編碼
在電報(bào)通信中，電文是以二進(jìn)制的0、1序列傳送的，每個(gè)字符對(duì)應(yīng)一個(gè)二進(jìn)制編碼，為了縮短電文的總長(zhǎng)度，采用不等長(zhǎng)編碼方式，構(gòu)造哈夫曼樹(shù)，
將每個(gè)字符的出現(xiàn)頻率作為字符結(jié)點(diǎn)的權(quán)值賦予葉子結(jié)點(diǎn)，每個(gè)分支結(jié)點(diǎn)的左右分支分別用0和1編碼，從樹(shù)根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑上
所經(jīng)分支的0、1編碼序列等于該葉子結(jié)點(diǎn)的二進(jìn)制編碼。如上文所示的哈夫曼編碼如下：
a 的編碼為：00
b 的編碼為：01
c 的編碼為：100
d 的編碼為：1010
e 的編碼為：1011
f 的編碼為：11
4、哈夫曼樹(shù)的操作運(yùn)算
以上文的哈夫曼樹(shù)作為具體實(shí)例，用詳細(xì)的程序展示哈夫曼樹(shù)的操作運(yùn)算
#include<stdio.h> #include<stdlib.h> typedef int ElemType; struct BTreeNode { ElemType data; struct BTreeNode* left; struct BTreeNode* right; }; //1、輸出二叉樹(shù)，可在前序遍歷的基礎(chǔ)上修改。采用廣義表格式，元素類(lèi)型為int void PrintBTree_int(struct BTreeNode* BT) { if (BT != NULL) { printf("%d", BT->data); //輸出根結(jié)點(diǎn)的值 if (BT->left != NULL || BT->right != NULL) { printf("("); PrintBTree_int(BT->left); //輸出左子樹(shù) if (BT->right != NULL) printf(","); PrintBTree_int(BT->right); //輸出右子樹(shù) printf(")"); } } } //2、根據(jù)數(shù)組 a 中 n 個(gè)權(quán)值建立一棵哈夫曼樹(shù)，返回樹(shù)根指針 struct BTreeNode* CreateHuffman(ElemType a[], int n) { int i, j; struct BTreeNode **b, *q; b = malloc(n*sizeof(struct BTreeNode)); for (i = 0; i < n; i++) //初始化b指針數(shù)組，使每個(gè)指針元素指向a數(shù)組中對(duì)應(yīng)的元素結(jié)點(diǎn) { b[i] = malloc(sizeof(struct BTreeNode)); b[i]->data = a[i]; b[i]->left = b[i]->right = NULL; } for (i = 1; i < n; i++)//進(jìn)行 n-1 次循環(huán)建立哈夫曼樹(shù) { //k1表示森林中具有最小權(quán)值的樹(shù)根結(jié)點(diǎn)的下標(biāo)，k2為次最小的下標(biāo) int k1 = -1, k2; for (j = 0; j < n; j++)//讓k1初始指向森林中第一棵樹(shù)，k2指向第二棵 { if (b[j] != NULL && k1 == -1) { k1 = j; continue; } if (b[j] != NULL) { k2 = j; break; } } for (j = k2; j < n; j++)//從當(dāng)前森林中求出最小權(quán)值樹(shù)和次最小 { if (b[j] != NULL) { if (b[j]->data < b[k1]->data) { k2 = k1; k1 = j; } else if (b[j]->data < b[k2]->data) k2 = j; } } //由最小權(quán)值樹(shù)和次最小權(quán)值樹(shù)建立一棵新樹(shù)，q指向樹(shù)根結(jié)點(diǎn) q = malloc(sizeof(struct BTreeNode)); q->data = b[k1]->data + b[k2]->data; q->left = b[k1]; q->right = b[k2]; b[k1] = q;//將指向新樹(shù)的指針賦給b指針數(shù)組中k1位置 b[k2] = NULL;//k2位置為空 } free(b); //刪除動(dòng)態(tài)建立的數(shù)組b return q; //返回整個(gè)哈夫曼樹(shù)的樹(shù)根指針 } //3、求哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度 ElemType WeightPathLength(struct BTreeNode* FBT, int len)//len初始為0 { if (FBT == NULL) //空樹(shù)返回0 return 0; else { if (FBT->left == NULL && FBT->right == NULL)//訪問(wèn)到葉子結(jié)點(diǎn) return FBT->data * len; else //訪問(wèn)到非葉子結(jié)點(diǎn)，進(jìn)行遞歸調(diào)用，返回左右子樹(shù)的帶權(quán)路徑長(zhǎng)度之和，len遞增 return WeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1); } } //4、哈夫曼編碼（可以根據(jù)哈夫曼樹(shù)帶權(quán)路徑長(zhǎng)度的算法基礎(chǔ)上進(jìn)行修改） void HuffManCoding(struct BTreeNode* FBT, int len)//len初始值為0 { static int a[10];//定義靜態(tài)數(shù)組a，保存每個(gè)葉子的編碼，數(shù)組長(zhǎng)度至少是樹(shù)深度減一 if (FBT != NULL)//訪問(wèn)到葉子結(jié)點(diǎn)時(shí)輸出其保存在數(shù)組a中的0和1序列編碼 { if (FBT->left == NULL && FBT->right == NULL) { int i; printf("結(jié)點(diǎn)權(quán)值為%d的編碼：", FBT->data); for (i = 0; i < len; i++) printf("%d", a[i]); printf("/n"); } else//訪問(wèn)到非葉子結(jié)點(diǎn)時(shí)分別向左右子樹(shù)遞歸調(diào)用，并把分支上的0、1編碼保存到數(shù)組a { //的對(duì)應(yīng)元素中，向下深入一層時(shí)len值增1 a[len] = 0; HuffManCoding(FBT->left, len + 1); a[len] = 1; HuffManCoding(FBT->right, len + 1); } } } //主函數(shù) void main() { int n, i; ElemType* a; struct BTreeNode* fbt; printf("從鍵盤(pán)輸入待構(gòu)造的哈夫曼樹(shù)中帶權(quán)葉子結(jié)點(diǎn)數(shù)n："); while(1) { scanf("%d", &n); if (n > 1) break; else printf("重輸n值："); } a = malloc(n*sizeof(ElemType)); printf("從鍵盤(pán)輸入%d個(gè)整數(shù)作為權(quán)值：", n); for (i = 0; i < n; i++) scanf(" %d", &a[i]); fbt = CreateHuffman(a, n); printf("廣義表形式的哈夫曼樹(shù)："); PrintBTree_int(fbt); printf("/n"); printf("哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度："); printf("%d/n", WeightPathLength(fbt, 0)); printf("樹(shù)中每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼：/n"); HuffManCoding(fbt, 0); }
運(yùn)行結(jié)果：
下面來(lái)看一道ACM題目
題目描述：
哈夫曼樹(shù)，第一行輸入一個(gè)數(shù)n，表示葉結(jié)點(diǎn)的個(gè)數(shù)。需要用這些葉結(jié)點(diǎn)生成哈夫曼樹(shù)，根據(jù)哈夫曼樹(shù)的概念，這些結(jié)點(diǎn)有權(quán)值，即weight，題目需要輸出所有結(jié)點(diǎn)的值與權(quán)值的乘積之和。
輸入：
輸入有多組數(shù)據(jù)。
每組第一行輸入一個(gè)數(shù)n，接著輸入n個(gè)葉節(jié)點(diǎn)（葉節(jié)點(diǎn)權(quán)值不超過(guò)100，2<=n<=1000）。
輸出：
輸出權(quán)值。
樣例輸入：
5
1 2 2 5 9
樣例輸出：
37
ac代碼
鏈表構(gòu)建哈夫曼樹(shù)（插入排序）
#include <stdio.h> #include <stdlib.h> #define max 1001 struct htree { int weight; struct htree *lchild; struct htree *rchild; struct htree *next; }; void addNode(struct htree *, struct htree *); struct htree* createHfmtree(int *, int); int getWpl(struct htree *, int); int main() { int w[max]; int i, n, wpl; struct htree *ht; while(scanf("%d", &n) != EOF) { for(i = 0; i < n; i ++) { scanf("%d", &w[i]); } ht = createHfmtree(w, n); wpl = getWpl(ht, 0); printf("%d/n", wpl); } return 0; } struct htree* createHfmtree(int *w, int n) { int i; struct htree *head, *pl, *pr, *proot; head = (struct htree *)malloc(sizeof(struct htree)); head->next = NULL; for(i = 0; i < n; i ++) { struct htree *pnode = malloc(sizeof(struct htree)); pnode->weight = *(w + i); pnode->lchild = pnode->rchild = pnode->next = NULL; addNode(head, pnode); } while(head->next) { if(head->next->next == NULL) break; pl = head->next; pr = pl->next; head->next = pr->next; proot = (struct htree *)malloc(sizeof(struct htree)); proot->weight = pl->weight + pr->weight; proot->lchild = pl; proot->rchild = pr; addNode(head, proot); } return head->next; } void addNode(struct htree *head, struct htree *pnode) { struct htree *t = head; while(t->next && t->next->weight < pnode->weight) t = t->next; pnode->next = t->next; t->next = pnode; } int getWpl(struct htree *ht, int level) { if(ht == NULL) return 0; if(!ht->lchild && !ht->rchild) { return ht->weight * level; } return getWpl(ht->lchild, level + 1) + getWpl(ht->rchild, level + 1); } 新聞熱點(diǎn)
疑難解答
圖片精選
