摘要： 哈夫曼树是十分重要的，常用于压缩的编码和解码。但写起来也比较折磨。
迟到的代码，实在抱歉。上代码！
一.代码块
其实由于哈夫曼树结点的度要么为0，要么为2，并且输入的编码的元素必为
叶节点，所以n个元素也就是n个叶节点的哈夫曼树必为2n-1个总结点。知道了结点个数，我们肯定更喜欢用顺序存储（数组）来存储哈夫曼树，而孩子和双亲则类似于静态链表，用下标代替地址
1）结构体定义
typedef struct huffmanTree
{
char data;
int weight;
int lchild,rchild,parent;
}HTNode,*huffmanTreePtr;
typedef char **huffmanTreeCode;//这个其实就是把char** 这个二维数组换成这个名字
2）选取最小的两个权重
由于我们每一次都选用最小的两个值来构建他们的双亲，所以这个函数就是选择从1到length里面最小的两个，用min1和min2传出来。注意，c语言不支持函数传入变量地址，但是c++支持，所以这个虽然用c写的，但是后缀需要是cpp。
void select(huffmanTreePtr &HT,int length,int &min1,int &min2)
{
//这里的tool就是用来找到最小元素的
int i,tool = 100000;
//记录最小的那一个
for(i = 1;i <= length;i ++)
{
//只能选择没有双亲的，即没被选过的
if(HT[i].weight < tool && HT[i].parent == 0)
{
tool = HT[i].weight;
min1 = i;
}
}
//记录第二小的那一个
tool = 100000;
for(i = 1;i <= length;i ++)
{
//i不等于于min1代表把第一遍选出的最小元素剔除了
if(HT[i].weight < tool && HT[i].parent == 0 && i != min1)
{
tool = HT[i].weight;
min2 = i;
}
}
}
3）创建哈夫曼树
我们输入的数据必为树的叶结点，并且我们是用他们往上去构建树，所以我们先直接把叶结点存在数组1-n的位置。虽然本质上是哈夫曼树，但对于计算机，他就是一个结构体的数组，对我们来说该如何体现树的结构性呢，就是用结构体里面的孩子和双亲代表下标来将他们链接起来。
void createHT(huffmanTreePtr &HT,char *dataArray,int *weightArray,int n)
{
int i；
//用来记录下标
int min1,min2;
HT = (huffmanTreePtr)malloc(2*n*sizeof(HTNode));
for(i = 1; i <= n;i ++)
{
HT[i].data = dataArray[i-1];
HT[i].weight = weightArray[i-1];
}
//由于数组0号我们没有用，所以将他们全部初始化为0，代表没有
for(i = 0;i < 2*n;i ++)
{
HT[i].lchild = 0;
HT[i].rchild = 0;
HT[i].parent = 0;
}
//这里是开始给后面n-1个合成的元素找双亲和孩子
for(i = n+1;i < 2*n;i ++)
{
select(HT,i-1,min1,min2);
HT[i].weight = HT[min1].weight + HT[min2].weight;
HT[i].lchild = min1;
HT[i].rchild = min2;
HT[min1].parent = i;
HT[min2].parent = i;
}
}
4）创建每个元素的编码
huffmanTreeCode就是一个二维数组，里面每一个元素都是存放编码的数组
我们用的办法是从叶结点网上回溯到根节点，所以得到的编码是逆序的，我们就用一个临时数组存放编码，如果他是双亲的左孩子，就在临时数组的倒数的二个位置（倒数第一个位置为结束符’ ’）赋0，如果是右孩子就赋1。再想上回溯，给倒数第三个位置赋值，一直到根节点。
最后再把这个数组copy到存放编码的整个二维数组里面去。
void createHTCode(huffmanTreePtr &HT,huffmanTreeCode &HTCode,int n)
{
//先用一个临时数组记录我们每一个元素的编码，记录好之后copy过去就行
char* tempArray = (char*)malloc(sizeof(char)*n);
//先给外层malloc
HTCode = (char**)malloc((n+1)*sizeof(char*));
int temp,j,c;
//最后一个位置先弄上结束符
tempArray[n-1] = ' ';
for(int i = 1;i <= n;i ++)
{
j=n-1;//每次都要先指向结束符位置
temp = HT[i].parent;
c = i;
//以双亲为0作为结束标志
while(temp != 0)
{
if(HT[temp].lchild == c)
tempArray[--j] = '0';
else
tempArray[--j] = '1';
c = temp;//往上走，走到当前元素的双亲
temp = HT[temp].parent;//temp也往上走
}
//实际1上我们申请空间就只需要这个大小，从n减到当前的j
HTCode[i] = (char*)malloc((n-j)*sizeof(char));
strcpy(HTCode[i],&tempArray[j]);
}
free(tempArray);//释放临时空间1
}
5）打印函数
void printHT(huffmanTreePtr &HT,huffmanTreeCode HTCode,int n)
{
printf("元素 权重 双亲 左孩子 右孩子n");
for(int i = 1;i < 2*n;i ++)
{
if(i<=n)
printf("%c ",HT[i].data);
else
printf(" ");
printf("%d ",HT[i].weight);
printf("%d ",HT[i].parent);
printf("%d ",HT[i].lchild);
printf("%d ",HT[i].rchild);
printf("n");
}
for(int i = 1;i <= n;i ++)
{
printf("元素%c的编码是:%sn",HT[i].data,HTCode[i]);
}
}
6）主函数
我们是在主函数里面开的临时数组存放元素和对应的权值，再把他们通过创建哈夫曼树放到树里面去。
int main()
{
int n = 0;
printf("请输入元素个数：n");
scanf("%d",&n);
getchar();//吸收换行符
char ch;
//用来记录元素和权重的临时数组
char* dataArray= (char*)malloc(sizeof(char)*n);
int* weightArray = (int*)malloc(n*sizeof(int));
printf("请输入这%d个元素：n",n);
for (int i = 0; i < n; i++)
{
ch = getchar();
getchar();//吸收空格符
dataArray[i] = ch;
}
printf("请输入这%d个元素对应的权重：n",n);
for(int i = 0;i < n;i ++)
{
scanf("%d",&weightArray[i]);
}
huffmanTreePtr HT;
createHT(HT,dataArray,weightArray,n);
huffmanTreeCode HTCode;
createHTCode(HT,HTCode,n);
printHT(HT,HTCode,n);
free(dataArray);
free(weightArray);
return 0;
}
三.运行结果
请输入元素个数：
5
请输入这5个元素：
s h b n u
请输入这5个元素对应的权重：
10 20 30 15 25
元素 权重 双亲 左孩子 右孩子
s 10 6 0 0
h 20 7 0 0
b 30 8 0 0
n 15 6 0 0
u 25 7 0 0
25 8 1 4
45 9 2 5
55 9 6 3
100 0 7 8
元素s的编码是:100
元素h的编码是:00
元素b的编码是:11
元素n的编码是:101
元素u的编码是:01
四.全部代码
#include#include #include typedef struct huffmanTree { char data; int weight; int lchild,rchild,parent; }HTNode,*huffmanTreePtr; typedef char **huffmanTreeCode;//这个其实就是把char** 这个二维数组换成这个名字 void select(huffmanTreePtr &HT,int length,int &min1,int &min2) { //这里的tool就是用来找到最小元素的 int i,tool = 100000; //记录最小的那一个 for(i = 1;i <= length;i ++) { //只能选择没有双亲的，即没被选过的 if(HT[i].weight < tool && HT[i].parent == 0) { tool = HT[i].weight; min1 = i; } } //记录第二小的那一个 tool = 100000; for(i = 1;i <= length;i ++) { //i不等于于min1代表把第一遍选出的最小元素剔除了 if(HT[i].weight < tool && HT[i].parent == 0 && i != min1) { tool = HT[i].weight; min2 = i; } } } void createHT(huffmanTreePtr &HT,char *dataArray,int *weightArray,int n) { int i; //用来记录下标 int min1,min2; HT = (huffmanTreePtr)malloc(2*n*sizeof(HTNode)); for(i = 1; i <= n;i ++) { HT[i].data = dataArray[i-1]; HT[i].weight = weightArray[i-1]; } //由于数组0号我们没有用，所以将他们全部初始化为0，代表没有 for(i = 0;i < 2*n;i ++) { HT[i].lchild = 0; HT[i].rchild = 0; HT[i].parent = 0; } //这里是开始给后面n-1个合成的元素找双亲和孩子 for(i = n+1;i < 2*n;i ++) { select(HT,i-1,min1,min2); HT[i].weight = HT[min1].weight + HT[min2].weight; HT[i].lchild = min1; HT[i].rchild = min2; HT[min1].parent = i; HT[min2].parent = i; } } void createHTCode(huffmanTreePtr &HT,huffmanTreeCode &HTCode,int n) { //先用一个临时数组记录我们每一个元素的编码，记录好之后copy过去就行 char* tempArray = (char*)malloc(sizeof(char)*n); //先给外层malloc HTCode = (char**)malloc((n+1)*sizeof(char*)); int temp,j,c; //最后一个位置先弄上结束符 tempArray[n-1] = ' '; for(int i = 1;i <= n;i ++) { j=n-1;//每次都要先指向结束符位置 temp = HT[i].parent; c = i; //以双亲为0作为结束标志 while(temp != 0) { if(HT[temp].lchild == c) tempArray[--j] = '0'; else tempArray[--j] = '1'; c = temp;//往上走，走到当前元素的双亲 temp = HT[temp].parent;//temp也往上走 } //实际1上我们申请空间就只需要这个大小，从n减到当前的j HTCode[i] = (char*)malloc((n-j)*sizeof(char)); strcpy(HTCode[i],&tempArray[j]); } free(tempArray);//释放临时空间1 } void printHT(huffmanTreePtr &HT,huffmanTreeCode HTCode,int n) { printf("元素 权重 双亲 左孩子 右孩子n"); for(int i = 1;i < 2*n;i ++) { if(i<=n) printf("%c ",HT[i].data); else printf(" "); printf("%d ",HT[i].weight); printf("%d ",HT[i].parent); printf("%d ",HT[i].lchild); printf("%d ",HT[i].rchild); printf("n"); } for(int i = 1;i <= n;i ++) { printf("元素%c的编码是:%sn",HT[i].data,HTCode[i]); } } int main() { int n = 0; printf("请输入元素个数：n"); scanf("%d",&n); getchar();//吸收换行符 char ch; //用来记录元素和权重的临时数组 char* dataArray= (char*)malloc(sizeof(char)*n); int* weightArray = (int*)malloc(n*sizeof(int)); printf("请输入这%d个元素：n",n); for (int i = 0; i < n; i++) { ch = getchar(); getchar();//吸收空格符 dataArray[i] = ch; } printf("请输入这%d个元素对应的权重：n",n); for(int i = 0;i < n;i ++) { scanf("%d",&weightArray[i]); } huffmanTreePtr HT; createHT(HT,dataArray,weightArray,n); huffmanTreeCode HTCode; createHTCode(HT,HTCode,n); printHT(HT,HTCode,n); free(dataArray); free(weightArray); return 0; }
