【哈夫曼樹】

1.相關(guān)概念

1）葉結(jié)點(diǎn)的權(quán)值：對(duì)葉結(jié)點(diǎn)賦予的一個(gè)有意義的數(shù)值量

2）二叉樹的帶權(quán)路徑長(zhǎng)度(WPL)：設(shè)二叉樹具有 n 個(gè)帶權(quán)葉結(jié)點(diǎn)，從根結(jié)點(diǎn)到各葉結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)葉節(jié)點(diǎn)權(quán)值的乘積之和

即：，其中 Wk 為第 k 個(gè)葉結(jié)點(diǎn)的權(quán)值，Lk 為從根結(jié)點(diǎn)到第 k 個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度

如圖所示，WPL=2*2+3*2+4*2+7*2=4+6+8+14=32

3）哈夫曼樹：給定一組具有確定權(quán)值的葉結(jié)點(diǎn)，可以構(gòu)造出不同的二叉樹，其中 WPL 最小的二叉樹稱為哈夫曼樹。

2.哈夫曼樹特點(diǎn)

1）權(quán)值越小，離根越遠(yuǎn)；權(quán)值越大，離根越近。

2）只有度為 0 的葉結(jié)點(diǎn)和度為 2 的分支結(jié)點(diǎn)，不存在度為 1 的結(jié)點(diǎn)

3.哈夫曼算法

1）初始化：由給定的 n 個(gè)權(quán)值構(gòu)造 n 棵只有一個(gè)根節(jié)點(diǎn)的二叉樹，得到一個(gè)二叉樹集合 F

2）選取與合并：從二叉樹集合 F 中選取根節(jié)點(diǎn)權(quán)值最小的兩棵二叉樹分別作為左右子樹構(gòu)造一棵新的二叉樹，這棵新二叉樹的根節(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值和

3）刪除與加入：從 F 中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到 F 中

4）重復(fù) 2）、3）?步，當(dāng)集合中只剩下一棵二叉樹時(shí)，這棵二叉樹就是哈夫曼樹

4.計(jì)算WPL

給出 n 個(gè)葉結(jié)點(diǎn)的權(quán)值，計(jì)算構(gòu)成哈夫曼樹的 WPL

int main() {int n;cin>>n;priority_queue<int,vector<int>,greater<int> > huffman;for(int i=1;i<=n;i++){int x;cin>>x;huffman.push(x);}int res=0;for(int i=1;i<n;i++){int x=huffman.top();huffman.pop();int y=huffman.top();huffman.pop();int temp=x+y;res+=temp;huffman.push(temp);}cout<<res<<endl;return 0; }

【哈夫曼編碼】

1.編碼

在進(jìn)行程序設(shè)計(jì)時(shí)，通常給每一個(gè)字符標(biāo)記一個(gè)單獨(dú)的代碼來表示一組字符，即編碼。

在進(jìn)行二進(jìn)制編碼時(shí)，假設(shè)所有的代碼都等長(zhǎng)，那么表示 n 個(gè)不同的字符需要??位，這稱為等長(zhǎng)編碼。

如果每個(gè)字符的使用頻率相等，那么等長(zhǎng)編碼無疑是空間效率最高的編碼方法，而如果字符出現(xiàn)的頻率不同，則可以讓頻率高的字符采用盡可能短的編碼，頻率低的字符采用盡可能長(zhǎng)的編碼，來構(gòu)造出一種不等長(zhǎng)編碼，從而獲得更好的空間效率。

在設(shè)計(jì)不等長(zhǎng)編碼時(shí)，要考慮解碼的唯一性，如果一組編碼中任一編碼都不是其他任何一個(gè)編碼的前綴，那么稱這組編碼為前綴編碼，其保證了編碼被解碼時(shí)的唯一性。

2.哈夫曼編碼

哈夫曼樹可用于構(gòu)造最短的前綴編碼方案，即哈夫曼編碼，具體做法如下：

1）設(shè)需要編碼的字符集為：，他們?cè)谧址谐霈F(xiàn)的頻率為：

2）以??作為葉結(jié)點(diǎn)，?作為葉結(jié)點(diǎn)的權(quán)值，構(gòu)造一棵哈夫曼樹

3）規(guī)定哈夫曼編碼樹的左分支代表 0，右分支代表 1，則從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)所經(jīng)過的路徑組成的 0、1 序列即為該葉結(jié)點(diǎn)對(duì)應(yīng)字符的編碼

3.實(shí)現(xiàn)

struct Node{int weight;Node *lchild,*rchild; }; typedef Node *tree; tree create(int arr[],int n){tree forest[N];tree root=NULL;for (int i=0; i<n; i++){//將所有點(diǎn)存入森林tree temp;temp=(tree)malloc(sizeof(Node));temp->weight = arr[i];temp->lchild = temp->rchild = NULL;forest[i]=temp;}for(int i=1; i<n; i++) {//n-1次循環(huán)建哈夫曼樹int minn=-1,minnSub;//minn為最小值樹根下標(biāo),minnsub為次小值樹根下標(biāo)for(int j=0; j<n; j++) {if (forest[j]!=NULL && minn==-1) {minn=j;continue;}if (forest[j]!=NULL) {minnSub=j;break;}}for (int j=minnSub; j<n; j++){//根據(jù)minn與minnSub賦值if(forest[j]!=NULL){if(forest[j]->weight < forest[minn]->weight){minnSub=minn;minn=j;}else if(forest[j]->weight < forest[minnSub]->weight){minnSub=j;}}}//建新樹root = (tree)malloc(sizeof(Node));root->weight = forest[minn]->weight + forest[minnSub]->weight;root->lchild = forest[minn];root->rchild = forest[minnSub];forest[minn]=root;//指向新樹的指針賦給minn位置forest[minnSub]=NULL;//minnSub位置為空}return root; } int getWPL(tree &root,int len){//計(jì)算哈夫曼樹帶權(quán)路徑長(zhǎng)度WPLif(root==NULL)return 0;else {if(root->lchild==NULL&&root->rchild==NULL)//葉節(jié)點(diǎn)return root->weight*len;elsereturn getWPL(root->lchild,len+1)+getWPL(root->rchild,len+1);} } void HuffmanCoding(tree &root,int len,int arr[]){//哈夫曼樹編碼if(root!=NULL){if(root->lchild==NULL&&root->rchild==NULL){printf("結(jié)點(diǎn)為%d的字符的編碼為: ",root->weight);for(int i=0;i<len;i++)printf("%d", arr[i]);printf("\n");}else{arr[len]=0;HuffmanCoding(root->lchild,len+1,arr);arr[len]=1;HuffmanCoding(root->rchild,len+1,arr);}} } int main(){int n=6;//長(zhǎng)度int arr[]={3,9,5,12,6,15};//權(quán)值tree root=create(arr,n);int WPL=getWPL(root,0);printf("WPL=%d\n",WPL);printf("==========各節(jié)點(diǎn)的哈夫曼樹編碼==========\n");HuffmanCoding(root,0,arr);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的理论基础 —— 二叉树 —— 哈夫曼树与哈夫曼编码的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。