帶權路徑長度演算法

⑴ 帶權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;
}