哈夫曼树的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;
}