带权路径长度
路径长度：路径上所经历边的个数。
结点的权：结点被赋予的数值。
树的带权路径长度：WPL，树中所有叶节点的带权路径长度之和，记为
公式
树的带权路径长度计算
哈夫曼树
也称最优二叉树，含有n个带权叶子结点带权路径长度最小的二叉树
哈夫曼树的构造算法
（1）将n个结点作为n棵仅含有一个根结点的二叉树，构成森林F；
（2）生成一个新的结点，并从F中找出根结点权值最小的两棵树作为它的左右子树，且新结点的权值为两棵子树根结点的权值之和。
（3）从F中删除这两棵树，并将新生成的树加入到F中。
（4）重复2，3步骤，直到F中只有一棵树为止。
哈夫曼树构造过程
哈夫曼树的性质
（1）每个初始结点都会成为叶结点，双支结点都为新生成的结点。
（2）权值越大离根结点越近，反之权值越小离根结点越远。
（3）哈夫曼树中没有度为1的结点。
（4）n个叶子结点的哈夫曼树的结点总数为2n-1，其中度为2的结点数为n-1。
哈夫曼树的应用
编码：对于一个字符串序列，用二进制来表示字符。
分类：
（1）固定长度编码：
（2）可变长度编码：
前缀编码：没有一个编码是另一个编码的前缀
使用哈夫曼树构造前缀编码：
使用哈夫曼树构造前缀编码
哈夫曼树并不是唯一的，所以每个字符对应的汉夫曼编码也不唯一，但带权路径长度相同且最优。
