八个权值是 5 29 7 8 14 23 3 11
(1) 从小到大排序 3 5 7 8 11 14 23 29 (这是有序序列)
(2) 每次提取最小的两个结点,取结点3和结点5,组成新结点N8,其权值=3+5=8,
取数值较小的结点作为左分支,结点3作为左分支,而结点5就作为右分支.
(3) 将新结点N8放入有序序列,保持从小到大排序:
7 8 N8 11 14 23 29 [注意,新结点N8排在原结点8的后面]
(4) 重复步骤(2),提取最小的两个结点,结点7与结点8组成新结点N15,其权值=7+8=15,
结点7的数值较小,将结点7作为左分支,结点8就作为右分支.
(5) 将新结点N15放入有序序列,保持从小到大排序:
N8 11 14 N15 23 29
(6) 重复步骤(2),提取最小的两个结点,N8与结点11组成新结点N19,其权值=8+11=19,
N8的数值较小,作为左分支,结点11就作为右分支.
(7) 将新结点N19放入有序序列,保持从小到大排序:
14 N15 N19 23 29
(8) 重复步骤(2),提取最小的两个结点,结点14与N15组成新结点N29,其权值=14+15=29,
结点14的数值较小,作为左分支,N15就作为右分支.
(9) 将新结点N29放入有序序列,保持从小到大排序:
N19 23 29 N29 [注意,新结点N29排在原结点29的后面]
(10)重复步骤(2),提取最小的两个结点,N19与结点23组成新结点N42,其权值=19+23=42,
N19的数值较小,作为左分支,结点23就作为右分支.
(11)将新结点N42放入有序序列,保持从小到大排序:
29 N29 N42
(12)重复步骤(2),提取最小的两个结点,结点29与N29组成新结点N58,其权值=29+29=58,
结点29与N29的数值相同,将原结点29作为左分支,N29就作为右分支.
(13)将新结点N58放入有序序列,保持从小到大排序:
N42 N58
(14)重复步骤(2),提取剩下的两个结点,N42与N58组成新结点N100,其权值=42+58=100,
数值较小的N42作为左分支,N58就作为右分支.
最后得到"哈夫曼树":
N100
/ \
N42 N58
/ \ / \
N19 23 29 N29
/ \ / \
N8 11 14 N15
/ \ / \
3 5 7 8
带权路径长度(WPL):
根结点N100到结点29的路径长度是2,结点29的带权路径长度是29*2
根结点N100到结点23的路径长度是2,结点23的带权路径长度是23*2
根结点N100到结点14的路径长度是3,结点14的带权路径长度是14*3
根结点N100到结点11的路径长度是3,结点11的带权路径长度是11*3
根结点N100到结点8的路径长度是4,结点8的带权路径长度是8*4
根结点N100到结点7的路径长度是4,结点7的带权路径长度是7*4
根结点N100到结点5的路径长度是4,结点5的带权路径长度是5*4
根结点N100到结点3的路径长度是4,结点3的带权路径长度是3*4
所以,哈夫曼树的带权路径长度(WPL)等于
29*2 + 23*2 + 14*3 + 11*3 + 8*4 + 7*4 + 5*4 + 3*4 = 271
哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
从根结点N100到结点29,先经历右分支,再经历左分支,结点29的编码就是10
从根结点N100到结点23,先经历左分支,再经历右分支,结点23的编码就是01
从根结点N100到结点14,经历两次右分支,再经历左分支,结点14的编码就是110
如此类推,得出所有结点的"哈夫曼编码":
权值29: 10
权值23: 01
权值14: 110
权值11: 001
权值8 : 1111
权值7 : 1110
权值5 : 0001
权值3 : 0000
//C语言测试程序:
//输入叶子结点的总个数: 8
//连续输入8个权值: 5 29 7 8 14 23 3 11
//Weight=5 Code=0001
//Weight=29 Code=10
//Weight=7 Code=1110
//Weight=8 Code=1111
//Weight=14 Code=110
//Weight=23 Code=01
//Weight=3 Code=0000
//Weight=11 Code=001
//huffman's WPL is: 271
#include
#include
#define MaxValue 10000 //初始设定的权值最大值
#define MaxBit 10 //初始设定的最大编码位数
#define MaxN 10 //初始设定的最大结点个数
struct HuffNode //哈夫曼树的结点结构
{
int weight;//权值
int flag;//标记
int parent;//双亲结点下标
int leftChild;//左孩子下标
int rightChild;//右孩子下标
};
struct Code//存放哈夫曼编码的数据元素结构
{
int bit[MaxBit];//数组
int start;//编码的起始下标
int weight;//字符的权值
};
//建立叶结点个数为n权值为weight的哈夫曼树huffTree
void Huffman(int weight[], int n, struct HuffNode huffTree[])
{
int i,j, m1, m2, x1, x2;
//哈夫曼树huffTree初始化。n个叶结点的哈夫曼树共有2n-1个结点
for (i = 0; i<2 * n - 1; i++)
{
if (i {
huffTree[i].weight = weight[i];
}
else
{
huffTree[i].weight = 0;
}
huffTree[i].parent = 0;
huffTree[i].flag = 0;
huffTree[i].leftChild = -1;
huffTree[i].rightChild = -1;
}
//构造哈夫曼树huffTree的n-1个非叶结点
for (i = 0; i {
m1 = m2 = MaxValue;//Maxvalue=10000;(就是一个相当大的数)
x1 = x2 = 0;//x1、x2是用来保存最小的两个值在数组对应的下标
for (j = 0; j {
if (huffTree[j].weight {
m2 = m1;
x2 = x1;
m1 = huffTree[j].weight;
x1 = j;
}
else if(huffTree[j].weight {
m2 = huffTree[j].weight;
x2 = j;
}
}
//将找出的两棵权值最小的子树合并为一棵子树
huffTree[x1].parent = n + i;
huffTree[x2].parent = n + i;
huffTree[x1].flag = 1;
huffTree[x2].flag = 1;
huffTree[n + i].weight = huffTree[x1].weight + huffTree[x2].weight;
huffTree[n + i].leftChild = x1;
huffTree[n + i].rightChild = x2;
}
}
//由n个结点的哈夫曼树huffTree构造哈夫曼编码huffCode
void HuffmanCode(struct HuffNode huffTree[], int n, struct Code huffCode[])
{
struct Code *cd=(struct Code *)malloc(sizeof(struct Code));
int child, parent;
int i,j;
//求n个叶结点的哈夫曼编码
for (i = 0; i {
cd->start = 0; //从0开始计数
cd->weight = huffTree[i].weight; //取得编码对应权值的字符
child = i;
parent = huffTree[child].parent;
//由叶结点向上直到根结点
while (parent != 0)
{
if (huffTree[parent].leftChild == child)
{
cd->bit[cd->start] = 0; //左孩子结点编码0
}
else
{
cd->bit[cd->start] = 1; //右孩子结点编码1
}
cd->start++; //编码自增
child = parent;
parent = huffTree[child].parent;
}
//重新修改编码，从根结点开始计数
for (j = cd->start - 1; j >= 0; j--)
{
huffCode[i].bit[cd->start - j - 1] = cd->bit[j];
}
huffCode[i].start = cd->start;
huffCode[i].weight = cd->weight;//保存编码对应的权值
}
}
int main()
{
int i, j;
int m = 0;
int n = 0;
int weight[20];
printf("输入叶子结点的总个数: ");
scanf("%d",&n);
printf("连续输入%d个权值: ",n);
for(i=0;i {
scanf("%d",&weight[i]);
}
struct HuffNode *myHuffTree=(struct HuffNode *)malloc((2*n-1)*sizeof(struct HuffNode));
struct Code *myHuffCode=(struct Code *)malloc(n*sizeof(struct Code));
if (n>MaxN)
{
printf("\n定义的n越界，修改MaxN!\n");
exit(0);
}
Huffman(weight, n, myHuffTree);
HuffmanCode(myHuffTree, n, myHuffCode);
//输出每个叶结点的哈夫曼编码
for (i = 0; i {
printf("Weight=%-4dCode=",myHuffCode[i].weight);
for (j = 0; j {
printf("%d",myHuffCode[i].bit[j]);
} m = m + myHuffCode[i].weight*myHuffCode[i].start;
printf("\n");
}
printf("huffman's WPL is: %d\n",m);
getchar();
return 0;
}
