带权路径长度算法

⑴ 带权9.1.3.5.6的五个叶子生成的哈夫曼树，带权路径长度怎么算

五个叶子的权值是91356
(1)将权值从小到大排序后是13569(这是有序序列)
(2)每次提取最小的两个节点,取节点1和节点3,组成新节点N4,其权值=1+3=4,
节点1的数值较小,作为左分支,节点3就作为右分支.
(3)将新节点N4放入有序序列,保持从小到大排序:
N4569(节点1和3已经提取掉)
(4)重复步骤(2),提取最小的两个节点,N4与节点5组成新节点N9,其权值=4+5,
N4的数值较小,作为左分支,节点5就作为右分支.
(5)将新节点N9放入有序序列,保持从小到大排序:
69N9(注意,要将新节点N9排在后,如果顺序是6N99则会有不同的结果)
(6)重复步骤(2),完成剩下的节点,最后,得到"哈夫曼树":

N24
/
N9N15
//
N4569
/
13

根节点N24到节点9的路径长度是2,节点9的带权路径长度是9*2
根节点N24到节点6的路径长度是2,节点6的带权路径长度是6*2
如此类推,可以得出其它节点的带权路径长度.
所以,哈夫曼树的带权路径长度WPL等于
9*2+6*2+5*2+3*3+1*3=52

哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
从根节点N24到节点9,先后经历两次右分支,节点9的编码就是11
从根节点N24到节点6,先经历右分支,再经历左分支,节点6的编码就是10
从根节点N24到节点5,先经历左分支,再经历右分支,节点5的编码就是01
如此类推,可以得出所有的节点的"哈夫曼编码":
权值9:11
权值6:10
权值5:01
权值3:001
权值1:000


//C语言测试程序
//输入构造哈夫曼树中带权叶子结点数n：5
//输入5个整数作为权值：91356
//可以得出哈夫曼树的带权路径长度,以及哈夫曼编码.

#include<stdio.h>
#include<stdlib.h>
typedefintElemType;
structBTreeNode
{
ElemTypedata;
structBTreeNode*left;
structBTreeNode*right;
};

//1、输出二叉树，可在前序遍历的基础上修改。
//采用广义表格式，元素类型为int
voidPrintBTree_int(structBTreeNode*BT)
{
if(BT!=NULL)
{
printf("%d",BT->data);//输出根结点的值
if(BT->left!=NULL||BT->right!=NULL)
{
printf("(");
PrintBTree_int(BT->left);//输出左子树
if(BT->right!=NULL)
printf(",");
PrintBTree_int(BT->right);//输出右子树
printf(")");
}
}
}

//2、根据数组a中n个权值建立一棵哈夫曼树，返回树根指针
structBTreeNode*CreateHuffman(ElemTypea[],intn)
{
inti,j;
structBTreeNode**b,*q;
b=malloc(n*sizeof(structBTreeNode));
//初始化b指针数组，使每个指针元素指向a数组中对应的元素结点
for(i=0;i<n;i++)
{
b[i]=malloc(sizeof(structBTreeNode));
b[i]->data=a[i];
b[i]->left=b[i]->right=NULL;
}
for(i=1;i<n;i++)//进行n-1次循环建立哈夫曼树
{
//k1表示森林中具有最小权值的树根结点的下标，k2为次最小的下标
intk1=-1,k2;
//让k1初始指向森林中第一棵树，k2指向第二棵
for(j=0;j<n;j++)
{
if(b[j]!=NULL&&k1==-1)
{
k1=j;
continue;
}
if(b[j]!=NULL)
{
k2=j;
break;
}
}
//从当前森林中求出最小权值树和次最小
for(j=k2;j<n;j++)
{
if(b[j]!=NULL)
{
if(b[j]->data<b[k1]->data)
{
k2=k1;
k1=j;
}
elseif(b[j]->data<b[k2]->data)
k2=j;
}
}
//由最小权值树和次最小权值树建立一棵新树，q指向树根结点
q=malloc(sizeof(structBTreeNode));
q->data=b[k1]->data+b[k2]->data;
q->left=b[k1];
q->right=b[k2];

b[k1]=q;//将指向新树的指针赋给b指针数组中k1位置
b[k2]=NULL;//k2位置为空
}
free(b);//删除动态建立的数组b
returnq;//返回整个哈夫曼树的树根指针
}

//3、求哈夫曼树的带权路径长度
ElemTypeWeightPathLength(structBTreeNode*FBT,intlen)//len初始为0
{
if(FBT==NULL)//空树返回0
return0;
else
{
if(FBT->left==NULL&&FBT->right==NULL)//访问到叶子结点
{
printf("+%d*%d",FBT->data,len);
returnFBT->data*len;
}
else//访问到非叶子结点，进行递归调用，
{//返回左右子树的带权路径长度之和，len递增
returnWeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
}

//4、哈夫曼编码（可以根据哈夫曼树带权路径长度的算法基础上进行修改）
voidHuffManCoding(structBTreeNode*FBT,intlen)//len初始值为0
{
//定义静态数组a，保存每个叶子的编码，数组长度至少是树深度减一
staticinta[10];
inti;
//访问到叶子结点时输出其保存在数组a中的0和1序列编码
if(FBT!=NULL)
{
if(FBT->left==NULL&&FBT->right==NULL)
{
printf("权值为%d的编码：",FBT->data);
for(i=0;i<len;i++)
printf("%d",a[i]);
printf("
");
}
else//访问到非叶子结点时分别向左右子树递归调用，
{//并把分支上的0、1编码保存到数组a的对应元素中，
//向下深入一层时len值增1
a[len]=0;
HuffManCoding(FBT->left,len+1);
a[len]=1;
HuffManCoding(FBT->right,len+1);
}
}
}

intmain()
{
intn,i;
ElemType*a;
structBTreeNode*fbt;
printf("输入构造哈夫曼树中带权叶子结点数n：");
while(1)
{
scanf("%d",&n);
if(n>1)
break;
else
printf("重输n值：");
}
a=malloc(n*sizeof(ElemType));
printf("输入%d个整数作为权值：",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
fbt=CreateHuffman(a,n);
printf("广义表形式的哈夫曼树：");
PrintBTree_int(fbt);
printf("
");
printf("哈夫曼树的带权路径长度：
");
printf("=");
printf("
=%d
",WeightPathLength(fbt,0));
printf("树中每个叶子结点的哈夫曼编码：
");
HuffManCoding(fbt,0);

return0;
}