哈夫曼編碼

halfman! halfman! 半人萬歲！（來自權力的游戲 Tyrion Lannister）
huffman coding哈夫曼編碼的核心是構造哈夫曼樹─即最優二叉樹，帶權路徑長度最小的二叉樹。它會使出現概率高的字符使用較短的編碼，反之出現概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，可用于數據的無損耗壓縮。

哈夫曼樹

引入

如果對多個字符進行哈夫曼編碼，如 a（7），b（5），c（2），d（4）四個字符進行編碼，其中括號中為該字符平均出現次數，稱為權重，就要將四個字符結點作為葉子結點構造一棵二叉樹，當這棵二叉樹的帶權路徑長度最小時，最優二叉樹就形成了。
結點的路徑長度：該結點到根結點之間的分支數目
結點的帶權路徑長度：結點的路徑長度與權重的乘積
樹的帶權路徑長度：所有結點的帶權路徑長度之和

上圖為一棵最優二叉樹，結點的權值越大，越靠近根結點。該哈夫曼樹的帶權路徑長度WPL為：7+5x2+2x3+4x3=35
它的哈夫曼編碼為：

a: 0 b: 10 c: 110 d: 111

算法實現

哈夫曼樹結點中的parent指針指向父節點的下標編號。

typedef struct htNode {char data;//結點中的信息int weight;//權重int parent, lc, rc;//分別指向父結點，左右孩子結點 }htNode,*HuffmanTree;

哈夫曼編碼保存在二維字符數組中，二維數組的每一行對應一個字符的編碼，如下：

typedef char** huffmanCode;

實現哈夫曼編碼的函數如下：其中存儲哈夫曼結點的ht和存儲哈夫曼編碼的hc均為引用，調用的select（）函數找出一些結點中權重最小的兩個結點來創建合適的新節點，并且有目的使最終算法實現的哈夫曼樹左邊結點權重總是小于右邊結點的。

void huffmanCoding(HuffmanTree& ht, huffmanCode& hc,int* weigh, char* character, int n)//weigh數組保存字符的權值，character數組保存字符，n表示字符個數 {if (n < 2)return;int m = 2 * n - 1;//8個字符一共需要建立15個結點ht = new htNode[m];int i, s1, s2;for (i = 0; i < n; i++)//對葉子結點進行初始化{ht[i].weight = weigh[i];ht[i].data = character[i];ht[i].lc = ht[i].rc = ht[i].parent = 0;}while (i < m)//進行非葉子結點構造，建成哈夫曼樹{select(ht, i - 1, s1, s2);//每次挑選當前結點i之前最小的parent為0的兩個結點，//且s1表示的權值總是小于s2的，所以哈夫曼樹是權值小的在左邊，權值大的在右邊。ht[s1].parent = i;ht[s2].parent = i;ht[i].lc = s1;ht[i].rc = s2;ht[i].parent = 0;//i在此作為父結點，將其parent總是要置為0的ht[i].weight = ht[s1].weight + ht[s2].weight;i++;}//哈夫曼樹構造完畢hc = new char*[n];char* cd = new char[n];//備用字符數組，從后往前輸入數據cd[n - 1] = '\0';for (i = 0; i <n; i++){int start = n - 1;int c, f;for (c = i, f = ht[i].parent;f != 0; c = f, f = ht[f].parent)//從葉子結點到根結點計算哈夫曼編碼{if (ht[f].lc == c)//左0右1cd[--start] = '0';elsecd[--start] = '1';}hc[i] = new char[n - start];//為第i個字符創建存儲空間c = 0;while (start < n)hc[i][c++] = cd[start++];//將cd中的字符復制到該字符的哈夫曼編碼存儲結構中}delete[] cd; }

譯碼過程實現

void deCoding(HuffmanTree ht, int m, char* buff)//buff中為0，1組成的字符串 {int p = m-1;while (*buff != '\0'&&p != -1)//直到buff中字符被讀取完畢，程序結束。{if (*buff == '0')p = ht[p].lc;elsep = ht[p].rc;++buff;if (!ht[p].lc&&!ht[p].rc)//葉子結點輸出{std::cout << ht[p].data << ' ';p = m-1;//又從根結點開始查找}} }

完整示例

這邊列出了一個完整的范例，是對給定的8個字符進行編碼，輸入字符存儲在data數組中，相應的權值存儲在weigh數組中，編碼之后進行譯碼。代碼如下：其中包含編碼輸出結果和譯碼結果

#include<iostream> #define N 8 typedef struct htNode {char data;//結點中的信息int weight;//權重int parent, lc, rc;//分別指向父結點，左右孩子結點 }htNode,*HuffmanTree; typedef char** huffmanCode; void huffmanCoding(HuffmanTree& ht, huffmanCode& hc, int* weigh, char* character, int n);//構建哈夫曼樹及哈夫曼編碼 void select(HuffmanTree& a, int b, int& s1, int& s2);//查找下標b之前的兩個最小值 void deCoding(HuffmanTree ht, int m, char* buff);//哈夫曼編碼的譯碼過程 int main() {using namespace std;char data[N] = { 'a', 'b', 'c', 'd', 'e', 'f','g','h' };int weigh[N] = { 10, 5, 2, 15, 32, 26, 19, 9 };HuffmanTree ht;huffmanCode hc;huffmanCoding(ht, hc, weigh, data, N);cout << "哈夫曼編碼：" << endl;int count;for (int i = 0; i < N; i++){count = 0;cout << data[i] <<": ";while (hc[i][count] != '\0')cout << hc[i][count++] << ' ';cout << endl;}cout << "哈夫曼譯碼： " << endl;//char* code = "0110001";//選用f，e，d的哈夫曼編碼const char* c = "0110001";//適用于vs2017版本int len = strlen(c);char* code = new char[len+1];code[len] = '\0';for (int i = 0; i < len; ++i)code[i] = c[i];deCoding(ht, 2 * N - 1, code);cout << endl;return 0; } void huffmanCoding(HuffmanTree& ht, huffmanCode& hc,int* weigh, char* character, int n)//weigh數組保存字符的權值，character數組保存字符，n表示字符個數 {if (n < 2)return;int m = 2 * n - 1;//8個字符一共需要建立15個結點ht = new htNode[m];int i, s1, s2;for (i = 0; i < n; i++)//對葉子結點進行初始化{ht[i].weight = weigh[i];ht[i].data = character[i];ht[i].lc = ht[i].rc = ht[i].parent = 0;}while (i < m)//進行非葉子結點構造，建成哈夫曼樹{select(ht, i - 1, s1, s2);//每次挑選當前結點i之前最小的parent為0的兩個結點，//且s1表示的權值總是小于s2的，所以哈夫曼樹是權值小的在左邊，權值大的在右邊。ht[s1].parent = i;ht[s2].parent = i;ht[i].lc = s1;ht[i].rc = s2;ht[i].parent = 0;//i在此作為父結點，將其parent總是要置為0的ht[i].weight = ht[s1].weight + ht[s2].weight;i++;}//哈夫曼樹構造完畢hc = new char*[n];char* cd = new char[n];//備用字符數組，從后往前輸入數據cd[n - 1] = '\0';for (i = 0; i <n; i++){int start = n - 1;int c, f;for (c = i, f = ht[i].parent;f != 0; c = f, f = ht[f].parent)//從葉子結點到根結點計算哈夫曼編碼{if (ht[f].lc == c)//左0右1cd[--start] = '0';elsecd[--start] = '1';}hc[i] = new char[n - start];//為第i個字符創建存儲空間c = 0;while (start < n)hc[i][c++] = cd[start++];//將cd中的字符復制到該字符的哈夫曼編碼存儲結構中}delete[] cd; } void select(HuffmanTree& a, int b, int& s1, int& s2) {int i, temp1=INT_MAX, temp2=INT_MAX;for (i = 0; i <= b; i++){if (a[i].parent == 0){if (temp1 > a[i].weight){temp1 = a[i].weight;s1 = i;}}}for (i = 0; i <= b; i++){if (a[i].parent == 0 && i != s1){if (temp2 > a[i].weight){temp2 = a[i].weight;s2 = i;}}} } void deCoding(HuffmanTree ht, int m, char* buff)//buff中為0，1組成的字符串 {int p = m-1;while (*buff != '\0'&&p != -1)//直到buff中字符被讀取完畢，程序結束。{if (*buff == '0')p = ht[p].lc;elsep = ht[p].rc;++buff;if (!ht[p].lc&&!ht[p].rc)//葉子結點輸出{std::cout << ht[p].data << ' ';p = m-1;//又從根結點開始查找}} }

算法中所建成的哈夫曼樹如圖：

哎呀，忘了在圖上標注權值了@_@
輸出結果為：

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的哈夫曼树（最优二叉树）（c/c++）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。