摘要：给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
一、代码段1）定义结构体
typedef struct huffmanTree
{
char data;
int weight;
int lchild,rchild,parent;
}HTNode,*huffmanTreePtr;
typedef char **huffmanTreeCode;
2) 选取最小的两个权值
void select(huffmanTreePtr &HT,int length,int &min1,int &min2)
{
int i,tool = 10000;
//记录最小的那一个
for(i = 1;i <= length;i ++)
{
//选取没有双亲的
if(HT[i].weight < tool && HT[i].parent == 0)
{
tool = HT[i].weight;
min1 = i;
}
}
//记录第二小的那一个
tool = 10000;
for(i = 1;i <= length;i ++)
{
if(HT[i].weight < tool && HT[i].parent == 0 && i != min1)
{
tool = HT[i].weight;
min2 = i;
}
}
}
3）创建哈夫曼树
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];
}
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）创建每个元素的编码
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);//释放临时空间
}
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)完整代码
#include#include #include typedef struct huffmanTree { char data; int weight; int lchild,rchild,parent; }HTNode,*huffmanTreePtr; typedef char **huffmanTreeCode; void select(huffmanTreePtr &HT,int length,int &min1,int &min2) { int i,tool = 10000; //记录最小的那一个 for(i = 1;i <= length;i ++) { //选取没有双亲的 if(HT[i].weight < tool && HT[i].parent == 0) { tool = HT[i].weight; min1 = i; } } //记录第二小的那一个 tool = 10000; for(i = 1;i <= length;i ++) { 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]; } 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);//释放临时空间 } 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; }
7）运行结果
请输入元素个数：
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
