哈夫曼樹的C語言詳解
1）一些名詞的解釋：
路徑：在一棵樹中，一個結點到另一個結點之間的通路，稱為路徑。圖 1 中，從根結點到結點 a 之間的通路就是一條路徑。
路徑長度：在一條路徑中，每經過一個結點，路徑長度都要加 1 。例如在一棵樹中，規定根結點所在層數為1層，那麼從根結點到第 i 層結點的路徑長度為 i - 1 。圖 1 中從根結點到結點 c 的路徑長度為 3。
結點的權：給每一個結點賦予一個新的數值，被稱為這個結點的權。
結點的帶權路徑長度：指的是從根結點到該結點之間的路徑長度與該結點的權的乘積
2）哈夫曼樹的定義：
當用 n 個結點（都做葉子結點且都有各自的權值）試圖建構一棵樹時，如果建構的這棵樹的帶權路徑長度最小，稱這棵樹為“最優二叉樹”，有時也叫“赫夫曼樹”或者“哈夫曼樹”。
在建構哈弗曼樹時，要使樹的帶權路徑長度最小，隻需要遵循一個原則，那就是：權重越大的結點離樹根越近。在圖 1 中，因為結點 a 的權值最大，是以理應直接作為根結點的孩子結點。
3）構造過程：
對于給定的有各自權值的 n 個結點，建構哈夫曼樹有一個行之有效的辦法：
在 n 個權值中選出兩個最小的權值，對應的兩個結點組成一個新的二叉樹，且新二叉樹的根結點的權值為左右孩子權值的和；
在原有的 n 個權值中删除那兩個最小的權值，同時将新的權值加入到 n–2 個權值的行列中，以此類推；
重複 1 和 2 ，直到是以的結點建構成了一棵二叉樹為止，這棵樹就是哈夫曼樹。
4）算法實作：
建構哈夫曼樹時，需要每次根據各個結點的權重值，篩選出其中值最小的兩個結點，然後建構二叉樹。
查找權重值最小的兩個結點的思想是：從樹組起始位置開始，首先找到兩個無父結點的結點（說明還未使用其建構成樹），然後和後續無父結點的結點依次做比較，有兩種情況需要考慮：
如果比兩個結點中較小的那個還小，就保留這個結點，删除原來較大的結點；
如果介于兩個結點權重值之間，替換原來較大的結點；
#include<iostream>
#include<string.h>
#define MAX 10000
/*
請輸入一段文字:this*program*is*my*favourite
字元和權值資訊如下
字元：t 權值：2
字元：h 權值：1
字元：i 權值：3
字元：s 權值：2
字元：* 權值：4
字元：p 權值：1
字元：r 權值：3
字元：o 權值：2
字元：g 權值：1
字元：a 權值：2
字元：m 權值：2
字元：y 權值：1
字元：f 權值：1
字元：v 權值：1
字元：u 權值：1
字元：e 權值：1
********************************
字元編碼為：
t:1000
h:11010
i:001
s:1001
*:011
p:11011
r:010
o:1010
g:11100
a:1011
m:1100
y:11101
f:11110
v:11111
u:0000
e:0001
文字編碼為：
100011010001100101111011010101011100010101111000110011001011110011101011111101011111111010000001000110000001
********************************
譯碼：
請輸入要譯碼的二進制字元串,輸入'#'結束：100011010001100101111011010101011100010101111000110011001011110011101011111101011111111010000001000110000001#
譯碼為:
this*program*is*my*favourite
是否繼續?(Y/N):
*/
using namespace std;
typedef struct {
char letter, *code;
int weight;
int parent, lchild, rchild;
}HTNode, *HuffmanTree;
int n;
char coding[100];
int Min(HuffmanTree &HT, int i)
{
int j;
unsigned int k = MAX;
int flag;
for (j = 0; j <= i; ++j)
{
if (HT[j].weight < k && HT[j].parent == 0)//用父結點是否為0來判斷此結點是否已經被選過
{
k = HT[j].weight;
flag = j;
}
}
HT[flag].parent = 1;//作個标記，說明已經被選擇了，因為在Select函數中要選擇權值小的兩個結點
return flag;
}
void Select(HuffmanTree &HT, int i, int &s1, int &s2)
{
//在HT[1...i]中選擇parent為0且權值最小的兩個結點，其序号分别為s1,s2
//s1 <= s2
s1 = Min(HT, i);
s2 = Min(HT, i);
}
void CreateHuffmanTree(HuffmanTree &HT, char t[], int w[])
{
int m;
int i, s1, s2;
if (n <= 1)
return;
m = 2 * n - 1; //總共需要2n－1個節點
HT = new HTNode[m + 1];//開辟空間
for (i = 0; i<n; i++)
{
HT[i].code = '\0';
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
HT[i].letter = t[i];
HT[i].weight = w[i];
}
for (i = n; i <= m; i++)
{
HT[i].code = '\0';
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
HT[i].letter = ' ';
HT[i].weight = 0;
}
cout << "********************************" << endl;
for (i = n; i<m; i++)
{
Select(HT, i - 1, s1, s2);//在n個數中找出權值最小的兩個
HT[s1].parent = i;
HT[s2].parent = i;//将他們兩個的parent節點設定為i;
HT[i].lchild = s1;
HT[i].rchild = s2;//把這兩個分别當作左右節點
HT[i].weight = HT[s1].weight + HT[s2].weight;//他們兩個的雙親為他們兩個的和；
}
}
void CreatHuffmanCode(HuffmanTree HT)
{
int start, c, f;
int i;
char *cd = new char[n];
cd[n - 1] = '\0';
cout << "字元編碼為：" << endl;
for (i = 0; i<n; i++)
{
start = n - 1;
c = i;
f = HT[i].parent;
while (f != 0){
--start;
if (HT[f].lchild == c){
cd[start] = '0';
}
else{
cd[start] = '1';
}
c = f;
f = HT[f].parent;
}
HT[i].code = new char[n - start];
strcpy(HT[i].code, &cd[start]);
cout << HT[i].letter << ":" << HT[i].code << endl;
}
delete cd;
}
void HuffmanTreeYima(HuffmanTree HT, char cod[], int b) //譯碼
{
char sen[100];
char temp[50];
char voidstr[] = " "; //空白字元串
int t = 0;
int s = 0;
int count = 0;
for (int i = 0; i<b; i++)
{
temp[t++] = cod[i]; //讀取字元
temp[t] = '\0'; //有效字元串
for (int j = 0; j<n; j++){ //依次與所有字元編碼開始比對
if (!strcmp(HT[j].code, temp)){ //比對成功
sen[s] = HT[j].letter; //将字元儲存到sen中
s++;
count += t;
strcpy(temp, voidstr); //将TEMP置空
t = 0; //t置空
break;
}
}
}
if (t == 0){ //t如果被置空了，表示都比對出來了，列印譯碼
sen[s] = '\0';
cout << "譯碼為:" << endl;
cout << sen << endl;
}
else{ //t如果沒有被置空 ， 源碼無法被完全比對
cout << "二進制源碼有錯！從第" << count + 1 << "位開始" << endl;
}
}
int main()
{
HuffmanTree HT;
char a[100], buff[1024], p;//a為存放字元 buff為輸入的字元串 p為輸入譯碼時的字元
int b[100];//存放權值資訊
int i, j;
int symbol = 1, x, k; //譯碼時做判斷用的變量
cout << "請輸入一段文字:";
cin >> buff;
int len = strlen(buff);
for (i = 0; i<len; i++)
{
for (j = 0; j<n; j++)
{
if (a[j] == buff[i])
{
b[j] = b[j] + 1;
break;
}
}
if (j >= n)
{
a[n] = buff[i];
b[n] = 1;
n++;
}
}
cout << "字元和權值資訊如下" << endl;
for (i = 0; i<n; i++)
{
cout << "字元：" << a[i] << " 權值：" << b[i] << endl;
}
CreateHuffmanTree(HT, a, b);
CreatHuffmanCode(HT);
cout << "文字編碼為：\n";
for (int i = 0; i < len; i++)
{
for (int j = 0; j < n; j++)
{
if (buff[i] == HT[j].letter)
{
cout << HT[j].code;
break;
}
}
}
cout <<endl<< "********************************" << endl;
cout << "譯碼：" << endl;
while (1)
{
cout << "請輸入要譯碼的二進制字元串,輸入'#'結束：";
x = 1;//判斷是否有非法字元隻能是0 1
k = 0;//作為循環變量來使coding【k】=輸入的字元
symbol = 1;//判斷是否輸入結束
while (symbol){
cin >> p;
if (p != '1'&&p != '0'&&p != '#'){ //若存在其它字元，x設為0，表示輸入的不是二進制
x = 0;
}
coding[k] = p;
if (p == '#')
symbol = 0; //#号結束标志
k++;
}
if (x == 1){
HuffmanTreeYima(HT, coding, k - 1); //進行譯碼
}
else{
cout << "有非法字元！" << endl;
}
cout << "是否繼續?(Y/N):";
cin >> p;
if (p == 'y' || p == 'Y')
continue;
else
break;
}
return 0;
}
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)