1 基本知识点

1、路径从一个结点到另一个结点之间的分支序列,构成了这两个结点之间的路径
2、路径长度路径上的分支数目

1 根结点到第L层结点路径长度为L-1
2 完全二叉树是总路径长度最短的二叉树

3、结点的权给树的每个结点赋予一个有实际意义的数
4、结点的带权路径长度从根结点到该结点的路径长度与结点的权的乘积
5、树的带权路径长度树中所有叶子结点的带权路径长度之和(WPL)
6、哈夫曼树由n个带权值的叶子结点构成的二叉树中,树的带权路径长度(WPL)最小的二叉树(最优二叉树)

2 哈夫曼树的特点

1、权值越大的叶子结点距离根结点越近,权值越小的叶子结点距离根结点越远
2、哈夫曼树只有度为0或者2的结点(没有度为1的结点)
3、哈夫曼树的任意非叶子结点的左右子树是可以交换的

结论
哈夫曼树的树形不是唯一的
但是WPL的值是相同的	

4、n个叶子结点的哈夫曼树由2*n-1个结点

推导
因为n0 = n2 + 1
所以n2 = n0 - 1
已知n0 = n,n2 = n - 1
所以说哈夫曼树由2*n-1个结点(度为0和度为2的结点数目相加)

3 构造哈夫曼树

解释
形成的这两种哈夫曼树都是正确的

4 哈夫曼编码

前缀码任何一个字符的编码**都不是**另一个字符的编码的前缀

使用二叉树可以构造前缀码
哈夫曼树可以构造最短的前缀码(哈夫曼编码)

方法
1 按照各个字符出现的频率来作为权值去构造一棵哈夫曼树
2 每个叶子结点都对应一个字符
3 按照规则将左子树标记为0
4 右子树标记为1
5 从根结点到每一个叶子结点路径上的0和1序列就是对应的哈夫曼编码

5 典型习题解析

正则二叉树是指此二叉树中不存在度为1的结点

6 算法题目

求WPL树中所有叶子结点的带权路径长度之和

调用WPL()函数:WPL(t,0)//参数0代表是从根结点开始
//根结点的路径长度为0,第L层结点的路径长度为L-1

int WPL(Node* t,int d)//d为结点的路径长度
{
	if(t == NULL)	return 0;//t为空子树
	if(t->left == NULL && t->right == NULL)
		return t->weight*d;//t为叶子结点
	else	
		return WPL(t->left,d+1)+WPL(t->right,d+1);
		//左右子树中叶子结点的带权路径长度之和
}

7 习题