哈夫曼树（最优二叉树）（c/c++）
哈夫曼編碼
halfman! halfman! 半人萬歲！（來自權(quán)力的游戲 Tyrion Lannister）
huffman coding哈夫曼編碼的核心是構(gòu)造哈夫曼樹─即最優(yōu)二叉樹，帶權(quán)路徑長度最小的二叉樹。它會(huì)使出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，可用于數(shù)據(jù)的無損耗壓縮。
哈夫曼樹
引入
如果對(duì)多個(gè)字符進(jìn)行哈夫曼編碼，如 a（7），b（5），c（2），d（4）四個(gè)字符進(jìn)行編碼，其中括號(hào)中為該字符平均出現(xiàn)次數(shù)，稱為權(quán)重，就要將四個(gè)字符結(jié)點(diǎn)作為葉子結(jié)點(diǎn)構(gòu)造一棵二叉樹，當(dāng)這棵二叉樹的帶權(quán)路徑長度最小時(shí)，最優(yōu)二叉樹就形成了。
結(jié)點(diǎn)的路徑長度：該結(jié)點(diǎn)到根結(jié)點(diǎn)之間的分支數(shù)目
結(jié)點(diǎn)的帶權(quán)路徑長度：結(jié)點(diǎn)的路徑長度與權(quán)重的乘積
樹的帶權(quán)路徑長度：所有結(jié)點(diǎn)的帶權(quán)路徑長度之和
上圖為一棵最優(yōu)二叉樹，結(jié)點(diǎn)的權(quán)值越大，越靠近根結(jié)點(diǎn)。該哈夫曼樹的帶權(quán)路徑長度WPL為：7+5x2+2x3+4x3=35
它的哈夫曼編碼為：
算法實(shí)現(xiàn)
哈夫曼樹結(jié)點(diǎn)中的parent指針指向父節(jié)點(diǎn)的下標(biāo)編號(hào)。
typedef struct htNode {char data;//結(jié)點(diǎn)中的信息int weight;//權(quán)重int parent, lc, rc;//分別指向父結(jié)點(diǎn)，左右孩子結(jié)點(diǎn) }htNode,*HuffmanTree;哈夫曼編碼保存在二維字符數(shù)組中，二維數(shù)組的每一行對(duì)應(yīng)一個(gè)字符的編碼，如下：
typedef char** huffmanCode;實(shí)現(xiàn)哈夫曼編碼的函數(shù)如下：其中存儲(chǔ)哈夫曼結(jié)點(diǎn)的ht和存儲(chǔ)哈夫曼編碼的hc均為引用，調(diào)用的select（）函數(shù)找出一些結(jié)點(diǎn)中權(quán)重最小的兩個(gè)結(jié)點(diǎn)來創(chuàng)建合適的新節(jié)點(diǎn)，并且有目的使最終算法實(shí)現(xiàn)的哈夫曼樹左邊結(jié)點(diǎn)權(quán)重總是小于右邊結(jié)點(diǎn)的。
void huffmanCoding(HuffmanTree& ht, huffmanCode& hc,int* weigh, char* character, int n)//weigh數(shù)組保存字符的權(quán)值，character數(shù)組保存字符，n表示字符個(gè)數(shù) {if (n < 2)return;int m = 2 * n - 1;//8個(gè)字符一共需要建立15個(gè)結(jié)點(diǎn)ht = new htNode[m];int i, s1, s2;for (i = 0; i < n; i++)//對(duì)葉子結(jié)點(diǎn)進(jìn)行初始化{ht[i].weight = weigh[i];ht[i].data = character[i];ht[i].lc = ht[i].rc = ht[i].parent = 0;}while (i < m)//進(jìn)行非葉子結(jié)點(diǎn)構(gòu)造，建成哈夫曼樹{select(ht, i - 1, s1, s2);//每次挑選當(dāng)前結(jié)點(diǎn)i之前最小的parent為0的兩個(gè)結(jié)點(diǎn)，//且s1表示的權(quán)值總是小于s2的，所以哈夫曼樹是權(quán)值小的在左邊，權(quán)值大的在右邊。ht[s1].parent = i;ht[s2].parent = i;ht[i].lc = s1;ht[i].rc = s2;ht[i].parent = 0;//i在此作為父結(jié)點(diǎn)，將其parent總是要置為0的ht[i].weight = ht[s1].weight + ht[s2].weight;i++;}//哈夫曼樹構(gòu)造完畢hc = new char*[n];char* cd = new char[n];//備用字符數(shù)組，從后往前輸入數(shù)據(jù)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)//從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)計(jì)算哈夫曼編碼{if (ht[f].lc == c)//左0右1cd[--start] = '0';elsecd[--start] = '1';}hc[i] = new char[n - start];//為第i個(gè)字符創(chuàng)建存儲(chǔ)空間c = 0;while (start < n)hc[i][c++] = cd[start++];//將cd中的字符復(fù)制到該字符的哈夫曼編碼存儲(chǔ)結(jié)構(gòu)中}delete[] cd; }譯碼過程實(shí)現(xiàn)
void deCoding(HuffmanTree ht, int m, char* buff)//buff中為0，1組成的字符串 {int p = m-1;while (*buff != '\0'&&p != -1)//直到buff中字符被讀取完畢，程序結(jié)束。{if (*buff == '0')p = ht[p].lc;elsep = ht[p].rc;++buff;if (!ht[p].lc&&!ht[p].rc)//葉子結(jié)點(diǎn)輸出{std::cout << ht[p].data << ' ';p = m-1;//又從根結(jié)點(diǎn)開始查找}} }完整示例
這邊列出了一個(gè)完整的范例，是對(duì)給定的8個(gè)字符進(jìn)行編碼，輸入字符存儲(chǔ)在data數(shù)組中，相應(yīng)的權(quán)值存儲(chǔ)在weigh數(shù)組中，編碼之后進(jìn)行譯碼。代碼如下：其中包含編碼輸出結(jié)果和譯碼結(jié)果
#include<iostream> #define N 8 typedef struct htNode {char data;//結(jié)點(diǎn)中的信息int weight;//權(quán)重int parent, lc, rc;//分別指向父結(jié)點(diǎn)，左右孩子結(jié)點(diǎn) }htNode,*HuffmanTree; typedef char** huffmanCode; void huffmanCoding(HuffmanTree& ht, huffmanCode& hc, int* weigh, char* character, int n);//構(gòu)建哈夫曼樹及哈夫曼編碼 void select(HuffmanTree& a, int b, int& s1, int& s2);//查找下標(biāo)b之前的兩個(gè)最小值 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數(shù)組保存字符的權(quán)值，character數(shù)組保存字符，n表示字符個(gè)數(shù) {if (n < 2)return;int m = 2 * n - 1;//8個(gè)字符一共需要建立15個(gè)結(jié)點(diǎn)ht = new htNode[m];int i, s1, s2;for (i = 0; i < n; i++)//對(duì)葉子結(jié)點(diǎn)進(jìn)行初始化{ht[i].weight = weigh[i];ht[i].data = character[i];ht[i].lc = ht[i].rc = ht[i].parent = 0;}while (i < m)//進(jìn)行非葉子結(jié)點(diǎn)構(gòu)造，建成哈夫曼樹{select(ht, i - 1, s1, s2);//每次挑選當(dāng)前結(jié)點(diǎn)i之前最小的parent為0的兩個(gè)結(jié)點(diǎn)，//且s1表示的權(quán)值總是小于s2的，所以哈夫曼樹是權(quán)值小的在左邊，權(quán)值大的在右邊。ht[s1].parent = i;ht[s2].parent = i;ht[i].lc = s1;ht[i].rc = s2;ht[i].parent = 0;//i在此作為父結(jié)點(diǎn)，將其parent總是要置為0的ht[i].weight = ht[s1].weight + ht[s2].weight;i++;}//哈夫曼樹構(gòu)造完畢hc = new char*[n];char* cd = new char[n];//備用字符數(shù)組，從后往前輸入數(shù)據(jù)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)//從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)計(jì)算哈夫曼編碼{if (ht[f].lc == c)//左0右1cd[--start] = '0';elsecd[--start] = '1';}hc[i] = new char[n - start];//為第i個(gè)字符創(chuàng)建存儲(chǔ)空間c = 0;while (start < n)hc[i][c++] = cd[start++];//將cd中的字符復(fù)制到該字符的哈夫曼編碼存儲(chǔ)結(jié)構(gòu)中}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中字符被讀取完畢，程序結(jié)束。{if (*buff == '0')p = ht[p].lc;elsep = ht[p].rc;++buff;if (!ht[p].lc&&!ht[p].rc)//葉子結(jié)點(diǎn)輸出{std::cout << ht[p].data << ' ';p = m-1;//又從根結(jié)點(diǎn)開始查找}} }算法中所建成的哈夫曼樹如圖：
哎呀，忘了在圖上標(biāo)注權(quán)值了@_@
輸出結(jié)果為：
總結(jié)
以上是生活随笔為你收集整理的哈夫曼树（最优二叉树）（c/c++）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 线索二叉树（c/c++）
- 下一篇： 图（c/c++）