赫夫曼编码树（图解+完整代码）
在我學(xué)習(xí)離散數(shù)學(xué)的時候，就已經(jīng)接觸了赫夫曼樹與赫夫曼編碼，于是在數(shù)據(jù)結(jié)構(gòu)的課程中，竟然直接跳過了！但我仍記得構(gòu)造赫夫曼樹，是當(dāng)時離散數(shù)學(xué)期末考試的12分大題，足以見其重要性！那這次不僅要把其構(gòu)造算法講清楚，還要把代碼給理清楚。
目錄
?1.相關(guān)概念?
?🏐2.赫夫曼樹?
🏀3.赫夫曼編碼
🥎4.完整代碼
4.1存儲結(jié)構(gòu)
4.2創(chuàng)建赫夫曼樹
4.3創(chuàng)建赫夫曼編碼
4.4完整代碼
?1.相關(guān)概念?
在介紹赫夫曼樹之前，我們先介紹4個相關(guān)概念，幫助我們更好的來定義哈夫曼樹
- 結(jié)點(diǎn)的路徑長度：從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的數(shù)目
- 樹的路徑長度：樹中每個結(jié)點(diǎn)的路徑長度之和
- 結(jié)點(diǎn)的帶權(quán)路徑長度：從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑長度與 結(jié)點(diǎn)上權(quán)的乘積
- 樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和
🏐2.赫夫曼樹?
定義：在所有含 n 個葉子結(jié)點(diǎn)、并且葉子結(jié)點(diǎn)帶相同權(quán)值的二叉樹中，其帶權(quán)路徑長度WPL最小的那棵二叉樹稱為赫夫曼樹，也叫最優(yōu)二叉樹。
那如何構(gòu)造赫夫曼樹呢？
輸入：n 和n 個權(quán)值 {w1 , w2 , …, wn }
輸出：赫夫曼樹
步驟：
我們以例子說明，輸入：已知n=5，權(quán)值集合 W={ 5, 6, 2, 9, 7 }。
?就這樣，一棵赫夫曼樹就構(gòu)建好了，我們可以發(fā)現(xiàn)：
- 赫夫曼算法采用的是貪心策略，貪心策略不是對所有問題都能得到最優(yōu)解，但赫夫曼算法得到的是最優(yōu)解
- n個葉子結(jié)點(diǎn)的赫夫曼樹共有2n-1個結(jié)點(diǎn)
- 赫夫曼樹中不會有度為1的結(jié)點(diǎn)
此時，有同學(xué)就要問了，哈夫曼樹有啥用呢？別著急，下面接著講。
🏀3.赫夫曼編碼
背景：在數(shù)據(jù)膨脹、信息爆炸的今天，數(shù)據(jù)壓縮的意義不言而喻。談到數(shù)據(jù)壓縮，就不能不提赫夫曼 （Huffman）編碼，赫夫曼編碼是首個實(shí)用的壓縮編碼放案，即使在今天的許多知名壓縮算法里，依然可以見到赫夫曼編碼的影子。
另外，在數(shù)據(jù)通信中，用?進(jìn)制給每個字符進(jìn)行編碼時不得不面對的?個問題是如何使電文總長最短且不產(chǎn)生二義性。根據(jù)字符出現(xiàn)頻率，利用赫夫曼編碼可以構(gòu)造出?種不等長的二進(jìn)制，使編碼后的電文長度最短，且保證不產(chǎn)生二義性。
同樣，我們先介紹幾個相關(guān)概念
定長編碼：
- ASCII編碼、Unicode編碼：ASCII編碼每?個字符使用8個bit，能夠編碼256個字符；Unicode 編碼每個字符占16個bit，能夠編碼65536個字符，包含所有ASCII編碼的字符。
- 假設(shè)我們要使用定長編碼對由符號A，B，C，D和E構(gòu)造的消息進(jìn)行編碼，對每個字符編碼需要多少位呢？ 至少需要3位，2個bit位不夠表示五個字符，只能表示4個字符。
- 如果對DEAACAAAAABA進(jìn)?編碼呢？總共12個字符，每個字符需要3bit，總共需要36位
而定長編碼有一定的缺陷：浪費(fèi)空間。我們希望出現(xiàn)頻率高的字符編碼短一些，出現(xiàn)頻率低的字符編碼長一些，這樣就可以盡可能使用較少的空間就傳遞了同樣的信息，于是就產(chǎn)生了變長編碼。
變長編碼：
- 單個編碼的長度不?樣，可以根據(jù)整體出現(xiàn)的頻率來調(diào)節(jié)，出現(xiàn)的頻率越高，編碼長度越短。
- 變長編碼優(yōu)于定長編碼：變長編碼可以將短編碼賦予平均出現(xiàn)頻率較高的字符，同?消息的 編碼長度小于定長編碼。
這時，又產(chǎn)生了一個問題：字符有長有短，我們怎么知道?個字符從哪里開始，?從哪里結(jié)束呢？ 如果位數(shù)固定，就沒這個問題了。
前綴屬性：
- 字符集當(dāng)中的?個字符編碼不是其他字符編碼的前綴，則這個字符編碼具有前綴屬性
- 所謂前綴，?個編碼可以被解碼為多個字符，表示不唯?
我們不妨來看個例子，我們隨意對字符進(jìn)行二進(jìn)制編碼：
| 字符 | 編碼 |
| P | 000 |
| Q | 11 |
| R | 01 |
| S | 001 |
| T | 10 |
?可以看出：以上編碼都具有前綴屬性，于是編碼不會產(chǎn)生二義性。比如01001101100010 可以翻譯為RSTQPT，不會翻譯成其他的字符串。
而下面這個編碼，就會產(chǎn)生歧義：10到底是S還是QP呢？顯然，這種編碼就不行。
| 字符 | 編碼 |
| P | 0 |
| Q | 1 |
| R | 01 |
| S | 10 |
| T | 11 |
前綴碼：所謂的前綴碼，就是沒有任何碼字是其他碼字的前綴。
鋪墊了這么久，終于要講到赫夫曼編碼了：赫夫曼編碼就是一種前綴碼，在構(gòu)造編碼時，就是用一棵赫夫曼樹來進(jìn)行構(gòu)造的。于是，我們可以稱其為赫夫曼編碼樹。
它的方法是什么呢？我們直接上赫夫曼編碼樹的特征。
- 赫曼編碼樹是?顆二叉樹
- 每片葉子結(jié)點(diǎn)都包含?個字符
- 從結(jié)點(diǎn)到其左孩子的路徑上標(biāo)記0
- 從結(jié)點(diǎn)到其右孩子的路徑上標(biāo)記1
- 從根結(jié)點(diǎn)到包含字符的葉?結(jié)點(diǎn)的路徑上獲得的葉結(jié)點(diǎn)的編碼
- 編碼均具有前綴屬性
我們繼續(xù)用上面構(gòu)造的赫夫曼樹來舉例：
?顯然，權(quán)重越大，即出現(xiàn)頻率越高的字符，他們的編碼相對更短；并且，他們都是前綴碼，不會產(chǎn)生二義性。
🥎4.完整代碼
上述過程都了解后，我們就可以開始想代碼實(shí)現(xiàn)了。每個人的方法都不同，下面僅給出我的方法。
4.1存儲結(jié)構(gòu)
首先，我們應(yīng)該思考用什么來存儲赫夫曼樹的結(jié)構(gòu)。赫夫曼樹是一棵二叉樹，所以應(yīng)該用二叉樹的存儲結(jié)構(gòu)，包括順序存儲與鏈?zhǔn)酱鎯Α?/p>
深入剖析二叉樹https://blog.csdn.net/weixin_54186646/article/details/124099967?spm=1001.2014.3001.5501由于赫夫曼樹不會出現(xiàn)斜樹的極端情況，故可用數(shù)組來存儲。
/*哈夫曼樹結(jié)構(gòu)*/ //可以用數(shù)組連續(xù)存儲，不會浪費(fèi)空間 //故用數(shù)組下標(biāo)存儲左右孩子、父親結(jié)點(diǎn) typedef struct {int weight;int left;int right;int parent; }Node, * HuffmanTree;4.2創(chuàng)建赫夫曼樹
現(xiàn)在開始創(chuàng)建赫夫曼樹。
葉子結(jié)點(diǎn)一共有n個，那總結(jié)點(diǎn)數(shù)為2n-1個
在上述代碼中，出現(xiàn)了select函數(shù)，其作用就是篩選出無父節(jié)點(diǎn)的最小和此小結(jié)點(diǎn)。
/*選取得到n個無父節(jié)點(diǎn)的兩最小結(jié)點(diǎn)*/ void select(HuffmanTree* T, int n, int* m1, int* m2) {int m;//存儲最小值的數(shù)組下標(biāo)//給m賦初值for (int i = 1; i <= n; i++){if ((*T)[i].parent == 0){m = i;break;}}//找到當(dāng)前最小的權(quán)重（葉子結(jié)點(diǎn)）for (int i = 1; i <= n; i++){if ((*T)[i].parent == 0 && (*T)[i].weight < (*T)[m].weight){m = i;}}//先賦給m1保存一個，再去尋找第二小的值*m1 = m;for (int i = 1; i <= n; i++){if ((*T)[i].parent == 0 && i != *m1){m = i;break;}}for (int i = 1; i <= n; i++){if ((*T)[i].parent == 0 && i != *m1 && (*T)[i].weight < (*T)[m].weight){m = i;}}//保存第二小的數(shù)*m2 = m; }4.3創(chuàng)建赫夫曼編碼
/*創(chuàng)建哈夫曼編碼*/ //從n個葉子結(jié)點(diǎn)到根節(jié)點(diǎn)逆向求解 void CreateHuffmanCode(HuffmanTree* T, HuffmanCode* C, int n) {//編碼長度為s-1,第s位為\0int s = n - 1;//當(dāng)前結(jié)點(diǎn)的父節(jié)點(diǎn)數(shù)組下標(biāo)int p = 0;//為哈夫曼編碼分配空間C = (HuffmanCode*)malloc((n + 1) * sizeof(char*));//臨時保存當(dāng)前葉子結(jié)點(diǎn)的哈夫曼編碼char* cd = (char*)malloc(n * sizeof(char));//最后一位為\0cd[n - 1] = '\0';for (int i = 1; i <= n; i++){s = n - 1;//c指向當(dāng)前結(jié)點(diǎn),p指向此結(jié)點(diǎn)的父節(jié)點(diǎn),兩者交替上升，直到根節(jié)點(diǎn)for (int c = i, p = (*T)[i].parent; p != 0; c = p, p = (*T)[p].parent){//判斷此結(jié)點(diǎn)為父節(jié)點(diǎn)的左孩子還是右孩子if ((*T)[p].left == c)cd[--s] = '0';//左孩子就是編碼0elsecd[--s] = '1';//右孩子就是編碼1}//為第i個編碼分配空間C[i] = (char*)malloc((n - s) * sizeof(char));//將此編碼賦值到整體編碼中strcpy(C[i], &cd[s]);}//釋放free(cd);//打印編碼序列for (int i = 1; i <= n; i++){printf("%d %s", (*T)[i].weight, C[i]);printf("\n");} }4.4完整代碼
#include<stdlib.h> #include<stdio.h> /*哈夫曼樹結(jié)構(gòu)*/ //可以用數(shù)組連續(xù)存儲，不會浪費(fèi)空間 //故用數(shù)組下標(biāo)存儲左右孩子、父親結(jié)點(diǎn) typedef struct {int weight;int left;int right;int parent; }Node, * HuffmanTree;//存儲哈夫曼編碼 typedef char* HuffmanCode; void CreateHuffmanTree(HuffmanTree* T, int w[], int n); void select(HuffmanTree* T, int n, int* m1, int* m2); void CreateHuffmanCode(HuffmanTree* T, HuffmanCode* C, int n); /*創(chuàng)建哈夫曼樹*/ //傳入n個權(quán)重，作為哈夫曼樹的n個葉子結(jié)點(diǎn) void CreateHuffmanTree(HuffmanTree* T, int w[], int n) {int m = 2 * n - 1;//n個葉子結(jié)點(diǎn)，共m個結(jié)點(diǎn)int m1, m2;//用于建立下一個結(jié)點(diǎn)的兩結(jié)點(diǎn)，值為最小的兩個*T = (HuffmanTree)malloc((m + 1) * sizeof(Node));//初始化前n個結(jié)點(diǎn)（葉子結(jié)點(diǎn)），權(quán)重賦值，暫時沒有左右孩子與父親for (int i = 1; i <= n; i++){(*T)[i].weight = w[i];(*T)[i].left = 0;(*T)[i].right = 0;(*T)[i].parent = 0;}//初始化[n+1,m]個結(jié)點(diǎn)(非葉子結(jié)點(diǎn))for (int i = n + 1; i <= m; i++){(*T)[i].weight = 0;(*T)[i].left = 0;(*T)[i].right = 0;(*T)[i].parent = 0;}//開始建樹，第i個結(jié)點(diǎn)的兩孩子為m1,m2，權(quán)重為兩孩子結(jié)點(diǎn)權(quán)重之和for (int i = n + 1; i <= m; i++){select(T, i - 1, &m1, &m2);(*T)[i].left = m1;(*T)[i].right = m2;(*T)[m1].parent = i;(*T)[m2].parent = i;(*T)[i].weight = (*T)[m1].weight + (*T)[m2].weight;printf("%d (%d %d)\n", (*T)[i].weight, (*T)[m1].weight, (*T)[m2].weight);}printf("\n"); }/*選取得到n個無父節(jié)點(diǎn)的兩最小結(jié)點(diǎn)*/ void select(HuffmanTree* T, int n, int* m1, int* m2) {int m;//存儲最小值的數(shù)組下標(biāo)//給m賦初值for (int i = 1; i <= n; i++){if ((*T)[i].parent == 0){m = i;break;}}//找到當(dāng)前最小的權(quán)重（葉子結(jié)點(diǎn)）for (int i = 1; i <= n; i++){if ((*T)[i].parent == 0 && (*T)[i].weight < (*T)[m].weight){m = i;}}//先賦給m1保存一個，再去尋找第二小的值*m1 = m;for (int i = 1; i <= n; i++){if ((*T)[i].parent == 0 && i != *m1){m = i;break;}}for (int i = 1; i <= n; i++){if ((*T)[i].parent == 0 && i != *m1 && (*T)[i].weight < (*T)[m].weight){m = i;}}//保存第二小的數(shù)*m2 = m; }/*創(chuàng)建哈夫曼編碼*/ //從n個葉子結(jié)點(diǎn)到根節(jié)點(diǎn)逆向求解 void CreateHuffmanCode(HuffmanTree* T, HuffmanCode* C, int n) {//編碼長度為s-1,第s位為\0int s = n - 1;//當(dāng)前結(jié)點(diǎn)的父節(jié)點(diǎn)數(shù)組下標(biāo)int p = 0;//為哈夫曼編碼分配空間C = (HuffmanCode*)malloc((n + 1) * sizeof(char*));//臨時保存當(dāng)前葉子結(jié)點(diǎn)的哈夫曼編碼char* cd = (char*)malloc(n * sizeof(char));//最后一位為\0cd[n - 1] = '\0';for (int i = 1; i <= n; i++){s = n - 1;//c指向當(dāng)前結(jié)點(diǎn),p指向此結(jié)點(diǎn)的父節(jié)點(diǎn),兩者交替上升，直到根節(jié)點(diǎn)for (int c = i, p = (*T)[i].parent; p != 0; c = p, p = (*T)[p].parent){//判斷此結(jié)點(diǎn)為父節(jié)點(diǎn)的左孩子還是右孩子if ((*T)[p].left == c)cd[--s] = '0';//左孩子就是編碼0elsecd[--s] = '1';//右孩子就是編碼1}//為第i個編碼分配空間C[i] = (char*)malloc((n - s) * sizeof(char));//將此編碼賦值到整體編碼中strcpy(C[i], &cd[s]);}//釋放free(cd);//打印編碼序列for (int i = 1; i <= n; i++){printf("%d %s", (*T)[i].weight, C[i]);printf("\n");} }int main() {HuffmanTree T;HuffmanCode C;int n, w1, * w;scanf_s("%d", &n);w = (int*)malloc((n + 1) * sizeof(int));for (int i = 1; i <= n; i++){scanf_s("%d", &w1);w[i] = w1;}printf("\n");CreateHuffmanTree(&T, w, n);CreateHuffmanCode(&T, &C, n);return 0; }我們來看看運(yùn)行結(jié)果：
- 輸入：5作為葉子結(jié)點(diǎn)個數(shù)，權(quán)重分別為6 7 5 2 9。
- 輸出：構(gòu)建了另外4個結(jié)點(diǎn)，7的孩子為2、5；13的孩子為6、7；16的孩子為7、9；29的孩子為13、16。權(quán)重為6的字符編碼為00；7的編碼為01；5的編碼為101；2的編碼為100；9的編碼為11
?
總結(jié)
以上是生活随笔為你收集整理的赫夫曼编码树（图解+完整代码）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： C语言将循环小数/有限小数转换为分数
- 下一篇： 二选一多路器Verilog