构造哈夫曼树，并计算树的带权的路径长度

哈夫曼树如下：
120
/ \
52 68
/ \ / \
25 27 29 39
/ \ / \
12 15 19 20
/ \ / \
5 7 9 10
树的带权路径长度：4(5+7 + 9 + 10) + 3(15+20) +2(25+29)=337

首先需要构造哈夫曼树，其构造规则是选择两个权值最小的结点，作为左右结点构造成一颗树，这颗树的根权值为左右子树权值大小的和，这个新的权值放入到原有的权值集合中，左右子树权值删除掉
循环上述过程，直到只有一棵树为止。
带权路径长度就是权值结点所在的高度 权值大小
带权路径长度之和就是将所有上面的所有求知结果汇总

七个权值3 3 7 7 11 13 17
(1) 从小到大排序 3 3 7 7 11 13 17 (这是有序序列)
(2) 每次提取最小的两个节点,取节点3和另一个节点3,组成新节点N6,其权值=3+3=6,
取数值较小的节点作为左分支,两个权值都是3,一个为左分支,另个为右分支
(3) 将新节点N6放入有序序列,保持从小到大排序:
N6 7 7 11 13 17 (两个节点3已经提取掉)
(4) 重复步骤(2),提取最小的两个节点,N6与节点7组成新节点N13,其权值=6+7=13,
N6的数值较小,作为左分支,节点7就作为右分支
(5) 将新节点N13放入有序序列,保持从小到大排序:
7 11 13 N13 17 (注意,要将新节点N13排在节点13的后面)
(6) 重复步骤(2),提取最小的两个节点,节点7与节点11组成新节点N18,其权值=7+11=18,
节点7的数值较小,作为左分支,节点11就作为右分支
(7) 将新节点N18放入有序序列,保持从小到大排序:
13 N13 17 N18
(8) 重复步骤(2),提取最小的两个节点,节点13与N13组成新节点N26,其权值=13+13=26,
节点13作为左分支,N13就作为右分支
(9) 将新节点N26放入有序序列,保持从小到大排序:
17 N18 N26
(10)重复步骤(2),完成剩下的节点,最后,得到"哈夫曼树":
N61
/ \
N26 N35
/ \ / \
13 N13 17 N18
/ \ / \
N6 7 7 11
/ \
3 3
根节点N61到节点17的路径长度是2,节点17的带权路径长度是172
根节点N61到节点13的路径长度是2,节点13的带权路径长度是132
根节点N61到节点11的路径长度是3,节点11的带权路径长度是113
如此类推,可以得出其它节点的带权路径长度
所以,哈夫曼树的带权路径长度WPL等于
172 + 132 + 113 + 73 + 73 + 34 + 34 = 159
哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1
从根节点N61到节点17,先经历右分支,再经历左分支,节点6的编码就是10
从根节点N61到节点13,先后经历两次左分支,节点13的编码就是00
从根节点N61到节点11,先后经历三次右分支,节点11的编码就是111
如此类推,可以得出所有的节点的"哈夫曼编码":
权值17: 10
权值13: 00
权值11: 111
权值 7: 011
权值 7: 110
权值 3: 0100
权值 3: 0101
//C语言测试程序
//输入构造哈夫曼树中带权叶子结点数n：7
//输入5个整数作为权值：17 13 11 7 7 3 3
//可以得出哈夫曼树的带权路径长度,以及哈夫曼编码
#include
#include
typedef int ElemType;
struct BTreeNode
{
ElemType data;
struct BTreeNode left;
struct BTreeNode right;
};
//1、输出二叉树，可在前序遍历的基础上修改。
// 采用广义表格式，元素类型为int
void PrintBTree_int(struct BTreeNode 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 个权值建立一棵哈夫曼树，返回树根指针
struct BTreeNode CreateHuffman(ElemType a[], int n)
{
int i, j;
struct BTreeNode b, q;
b = malloc(nsizeof(struct BTreeNode));
//初始化b指针数组，使每个指针元素指向a数组中对应的元素结点
for (i = 0; i < n; i++)
{
b[i] = malloc(sizeof(struct BTreeNode));
b[i]->data = a[i];
b[i]->left = b[i]->right = NULL;
}
for (i = 1; i < n; i++)//进行 n-1 次循环建立哈夫曼树
{
//k1表示森林中具有最小权值的树根结点的下标，k2为次最小的下标
int k1 = -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;
}
else if (b[j]->data b[k2]->data)
k2 = j;
}
}
//由最小权值树和次最小权值树建立一棵新树，q指向树根结点
q = malloc(sizeof(struct BTreeNode));
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
return q; //返回整个哈夫曼树的树根指针
}
//3、求哈夫曼树的带权路径长度
ElemType WeightPathLength(struct BTreeNode FBT, int len)//len初始为0
{
if (FBT == NULL) //空树返回0
return 0;
else
{
if (FBT->left == NULL && FBT->right == NULL)//访问到叶子结点
{
printf("+ %d %d ",FBT->data,len);
return FBT->data len;
}
else //访问到非叶子结点，进行递归调用，
{ //返回左右子树的带权路径长度之和，len递增
return WeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
}
//4、哈夫曼编码（可以根据哈夫曼树带权路径长度的算法基础上进行修改）
void HuffManCoding(struct BTreeNode FBT, int len)//len初始值为0
{
//定义静态数组a，保存每个叶子的编码，数组长度至少是树深度减一
static int a[10];
int i;
//访问到叶子结点时输出其保存在数组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("\n");
}
else //访问到非叶子结点时分别向左右子树递归调用，
{ //并把分支上的0、1编码保存到数组a的对应元素中，
//向下深入一层时len值增1
a[len] = 0;
HuffManCoding(FBT->left, len + 1);
a[len] = 1;
HuffManCoding(FBT->right, len + 1);
}
}
}
int main()
{
int n, i;
ElemType a;
struct BTreeNode fbt;
printf("输入构造哈夫曼树中带权叶子结点数n：");
while(1)
{
scanf("%d", &n);
if (n > 1)
break;
else
printf("重输n值：");
}
a = malloc(nsizeof(ElemType));
printf("输入%d个整数作为权值：", n);
for (i = 0; i < n; i++)
scanf(" %d", &a[i]);
fbt = CreateHuffman(a, n);
printf("广义表形式的哈夫曼树：");
PrintBTree_int(fbt);
printf("\n");
printf("哈夫曼树的带权路径长度：\n");
printf("=");
printf("\n=%d\n", WeightPathLength(fbt, 0));
printf("树中每个叶子结点的哈夫曼编码：\n");
HuffManCoding(fbt, 0);
return 0;
}

哈夫曼树见图。用word随便画的，比较难看。

带权路径长度 （2+3）3+(5+7+9)2+121=15+42+12=69

其实你可以根据下面的直接求。

哈夫曼树的构造

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树

深度6先序：EBADCFHGIKJ

中序：ABCDEFGHIJK

后序：ACDBGJKIHFE。

哈夫曼树是：

100

/ \

42 58

/ \ / \

17 25 26 32

/ \ / \

8 9 12 13

/ \ / \

3 5 6 7

树的带权路径长度为WPL = （3+5 + 6 +7）4 + （9+ 12）3 + （26+32）2 = 263

扩展资料：

树的带权路径长度记为WPL=(W1L1+W2L2+W3L3++WnLn)，N个权值Wi(i=1,2,n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,n)。可以证明哈夫曼树的WPL是最小的。

WPL是衡量一个带权二叉树优劣的关键。

无论如何，对于n个带权节点，总可以用他们作为叶节点构造出一颗最小WPL值得树，并称满足这个条件的二叉树为哈夫曼树。

参考资料来源：百度百科-wpl

---