使用C語言詳解霍夫曼樹數(shù)據(jù)結(jié)構(gòu)
1、基本概念
a、路徑和路徑長度
若在一棵樹中存在著一個結(jié)點序列 k1，k2，……，kj， 使得 ki是ki+1 的雙親（1<=i<j），則稱此結(jié)點序列是從 k1 到 kj 的路徑。
從 k1 到 kj 所經(jīng)過的分支數(shù)稱為這兩點之間的路徑長度，它等于路徑上的結(jié)點數(shù)減1.
b、結(jié)點的權(quán)和帶權(quán)路徑長度
在許多應(yīng)用中，常常將樹中的結(jié)點賦予一個有著某種意義的實數(shù)，我們稱此實數(shù)為該結(jié)點的權(quán)，(如下面一個樹中的藍(lán)色數(shù)字表示結(jié)點的權(quán))
結(jié)點的帶權(quán)路徑長度規(guī)定為從樹根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點上權(quán)的乘積。
c、樹的帶權(quán)路徑長度
樹的帶權(quán)路徑長度定義為樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，公式為：
其中，n表示葉子結(jié)點的數(shù)目，wi 和 li 分別表示葉子結(jié)點 ki 的權(quán)值和樹根結(jié)點到 ki 之間的路徑長度。
如下圖中樹的帶權(quán)路徑長度 WPL = 9 x 2 + 12 x 2 + 15 x 2 + 6 x 3 + 3 x 4 + 5 x 4 = 122
d、哈夫曼樹
哈夫曼樹又稱最優(yōu)二叉樹。它是 n 個帶權(quán)葉子結(jié)點構(gòu)成的所有二叉樹中，帶權(quán)路徑長度 WPL 最小的二叉樹。
如下圖為一哈夫曼樹示意圖。
2、構(gòu)造哈夫曼樹
假設(shè)有n個權(quán)值，則構(gòu)造出的哈夫曼樹有n個葉子結(jié)點。 n個權(quán)值分別設(shè)為 w1、w2、…、wn，則哈夫曼樹的構(gòu)造規(guī)則為：
(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結(jié)點)；
(2) 在森林中選出兩個根結(jié)點的權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點權(quán)值為其左、右子樹根結(jié)點權(quán)值之和；
(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；
(4)重復(fù)(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。
如：對 下圖中的六個帶權(quán)葉子結(jié)點來構(gòu)造一棵哈夫曼樹，步驟如下：
注意：為了使得到的哈夫曼樹的結(jié)構(gòu)盡量唯一，通常規(guī)定生成的哈夫曼樹中每個結(jié)點的左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán)。
具體算法如下：
//2、根據(jù)數(shù)組 a 中 n 個權(quán)值建立一棵哈夫曼樹，返回樹根指針
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ù)組，使每個指針元素指向a數(shù)組中對應(yīng)的元素結(jié)點
{
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)建立哈夫曼樹
{
//k1表示森林中具有最小權(quán)值的樹根結(jié)點的下標(biāo)，k2為次最小的下標(biāo)
int k1 = -1, k2;
for (j = 0; j < n; j++)//讓k1初始指向森林中第一棵樹，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)值樹和次最小
{
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)值樹和次最小權(quán)值樹建立一棵新樹，q指向樹根結(jié)點
q = malloc(sizeof(struct BTreeNode));
q->data = b[k1]->data + b[k2]->data;
q->left = b[k1];
q->right = b[k2];
b[k1] = q;//將指向新樹的指針賦給b指針數(shù)組中k1位置
b[k2] = NULL;//k2位置為空
}
free(b); //刪除動態(tài)建立的數(shù)組b
return q; //返回整個哈夫曼樹的樹根指針
}
3、哈夫曼編碼
在電報通信中，電文是以二進(jìn)制的0、1序列傳送的，每個字符對應(yīng)一個二進(jìn)制編碼，為了縮短電文的總長度，采用不等長編碼方式，構(gòu)造哈夫曼樹，
將每個字符的出現(xiàn)頻率作為字符結(jié)點的權(quán)值賦予葉子結(jié)點，每個分支結(jié)點的左右分支分別用0和1編碼，從樹根結(jié)點到每個葉子結(jié)點的路徑上
所經(jīng)分支的0、1編碼序列等于該葉子結(jié)點的二進(jìn)制編碼。如上文所示的哈夫曼編碼如下：
a 的編碼為：00
b 的編碼為：01
c 的編碼為：100
d 的編碼為：1010
e 的編碼為：1011
f 的編碼為：11
4、哈夫曼樹的操作運算
以上文的哈夫曼樹作為具體實例，用詳細(xì)的程序展示哈夫曼樹的操作運算
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
struct BTreeNode
{
ElemType data;
struct BTreeNode* left;
struct BTreeNode* right;
};
//1、輸出二叉樹，可在前序遍歷的基礎(chǔ)上修改。采用廣義表格式，元素類型為int
void PrintBTree_int(struct BTreeNode* BT)
{
if (BT != NULL)
{
printf("%d", BT->data); //輸出根結(jié)點的值
if (BT->left != NULL || BT->right != NULL)
{
printf("(");
PrintBTree_int(BT->left); //輸出左子樹
if (BT->right != NULL)
printf(",");
PrintBTree_int(BT->right); //輸出右子樹
printf(")");
}
}
}
//2、根據(jù)數(shù)組 a 中 n 個權(quán)值建立一棵哈夫曼樹，返回樹根指針
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ù)組，使每個指針元素指向a數(shù)組中對應(yīng)的元素結(jié)點
{
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)建立哈夫曼樹
{
//k1表示森林中具有最小權(quán)值的樹根結(jié)點的下標(biāo)，k2為次最小的下標(biāo)
int k1 = -1, k2;
for (j = 0; j < n; j++)//讓k1初始指向森林中第一棵樹，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)值樹和次最小
{
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)值樹和次最小權(quán)值樹建立一棵新樹，q指向樹根結(jié)點
q = malloc(sizeof(struct BTreeNode));
q->data = b[k1]->data + b[k2]->data;
q->left = b[k1];
q->right = b[k2];
b[k1] = q;//將指向新樹的指針賦給b指針數(shù)組中k1位置
b[k2] = NULL;//k2位置為空
}
free(b); //刪除動態(tài)建立的數(shù)組b
return q; //返回整個哈夫曼樹的樹根指針
}
//3、求哈夫曼樹的帶權(quán)路徑長度
ElemType WeightPathLength(struct BTreeNode* FBT, int len)//len初始為0
{
if (FBT == NULL) //空樹返回0
return 0;
else
{
if (FBT->left == NULL && FBT->right == NULL)//訪問到葉子結(jié)點
return FBT->data * len;
else //訪問到非葉子結(jié)點，進(jìn)行遞歸調(diào)用，返回左右子樹的帶權(quán)路徑長度之和，len遞增
return WeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
//4、哈夫曼編碼（可以根據(jù)哈夫曼樹帶權(quán)路徑長度的算法基礎(chǔ)上進(jìn)行修改）
void HuffManCoding(struct BTreeNode* FBT, int len)//len初始值為0
{
static int a[10];//定義靜態(tài)數(shù)組a，保存每個葉子的編碼，數(shù)組長度至少是樹深度減一
if (FBT != NULL)//訪問到葉子結(jié)點時輸出其保存在數(shù)組a中的0和1序列編碼
{
if (FBT->left == NULL && FBT->right == NULL)
{
int i;
printf("結(jié)點權(quán)值為%d的編碼：", FBT->data);
for (i = 0; i < len; i++)
printf("%d", a[i]);
printf("\n");
}
else//訪問到非葉子結(jié)點時分別向左右子樹遞歸調(diào)用，并把分支上的0、1編碼保存到數(shù)組a
{ //的對應(yīng)元素中，向下深入一層時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("從鍵盤輸入待構(gòu)造的哈夫曼樹中帶權(quán)葉子結(jié)點數(shù)n：");
while(1)
{
scanf("%d", &n);
if (n > 1)
break;
else
printf("重輸n值：");
}
a = malloc(n*sizeof(ElemType));
printf("從鍵盤輸入%d個整數(shù)作為權(quán)值：", n);
for (i = 0; i < n; i++)
scanf(" %d", &a[i]);
fbt = CreateHuffman(a, n);
printf("廣義表形式的哈夫曼樹：");
PrintBTree_int(fbt);
printf("\n");
printf("哈夫曼樹的帶權(quán)路徑長度：");
printf("%d\n", WeightPathLength(fbt, 0));
printf("樹中每個葉子結(jié)點的哈夫曼編碼：\n");
HuffManCoding(fbt, 0);
}
運行結(jié)果：
下面來看一道ACM題目
題目描述：
哈夫曼樹，第一行輸入一個數(shù)n，表示葉結(jié)點的個數(shù)。需要用這些葉結(jié)點生成哈夫曼樹，根據(jù)哈夫曼樹的概念，這些結(jié)點有權(quán)值，即weight，題目需要輸出所有結(jié)點的值與權(quán)值的乘積之和。
輸入：
輸入有多組數(shù)據(jù)。
每組第一行輸入一個數(shù)n，接著輸入n個葉節(jié)點（葉節(jié)點權(quán)值不超過100，2<=n<=1000）。
輸出：
輸出權(quán)值。
樣例輸入：
5
1 2 2 5 9
樣例輸出：
37
ac代碼
鏈表構(gòu)建哈夫曼樹（插入排序）
#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);
}
- c語言連接mysql數(shù)據(jù)庫的實現(xiàn)方法
- linux安裝mysql和使用c語言操作數(shù)據(jù)庫的方法 c語言連接mysql
- C語言讀取BMP圖像數(shù)據(jù)的源碼
- 詳解C語言中的char數(shù)據(jù)類型及其與int類型的轉(zhuǎn)換
- php讀取二進(jìn)制流(C語言結(jié)構(gòu)體struct數(shù)據(jù)文件)的深入解析
- linux c語言操作數(shù)據(jù)庫(連接sqlite數(shù)據(jù)庫)
- c語言讀取obj文件轉(zhuǎn)換數(shù)據(jù)的小例子
- 使用C語言構(gòu)建基本的二叉樹數(shù)據(jù)結(jié)構(gòu)
- 用C語言操作MySQL數(shù)據(jù)庫的通用方法
- 深入解析C語言中常數(shù)的數(shù)據(jù)類型
- C語言中經(jīng)socket接收數(shù)據(jù)的相關(guān)函數(shù)詳解
- C語言實現(xiàn)txt數(shù)據(jù)讀入內(nèi)存/CPU緩存實例詳解
相關(guān)文章
本篇文章是對SVN源碼服務(wù)器搭建進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-06-06
這篇文章主要介紹了C++ Primer注解之引用和指針的相關(guān)知識，本文通過實例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價值,需要的朋友可以參考下2020-02-02
這篇文章主要給大家介紹了關(guān)于C++11基于范圍的for循環(huán)的相關(guān)資料,范圍for循環(huán)(也稱為C++11的基于范圍的for循環(huán))是一種簡化迭代容器（如數(shù)組、向量、列表等）元素的方式,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2024-06-06
CStdioFile 不支持Duplicate，LockRange，和UnlockRange 這幾個CFile 函數(shù)。如果在CStdioFile 中調(diào)用了這幾個函數(shù)，將會出現(xiàn)CNoSupported 異常2013-09-09
C語言實現(xiàn)將字符串轉(zhuǎn)換為數(shù)字的方法
這篇文章主要介紹了C語言實現(xiàn)將字符串轉(zhuǎn)換為數(shù)字的方法,涉及系統(tǒng)函數(shù)atoi()函數(shù)的使用技巧,需要的朋友可以參考下2014-12-12
這篇文章主要介紹了C/C++ 的*和&的相關(guān)知識，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-11-11
最近因為項目原因需要解析JSON格式數(shù)據(jù),所以這篇文章主要給大家介紹了關(guān)于C++操作.json文件的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-08-08
這篇文章主要介紹了在C語言編程中使用變量的基礎(chǔ)教程,特別需要注意C語言中的指針變量,需要的朋友可以參考下2016-02-02
棧和隊列，嚴(yán)格意義上來說，也屬于線性表，因為它們也都用于存儲邏輯關(guān)系為?"一對一"?的數(shù)據(jù)，但由于它們比較特殊，因此將其單獨作為一章，做重點講解2022-03-03
這篇文章主要介紹了安裝OpenMPI來配合C語言程序進(jìn)行并行計算的例子,MPI的全稱是Message Passing Interface即標(biāo)準(zhǔn)消息傳遞界面,可以用于并行計算,需要的朋友可以參考下2015-11-11