二叉树的应用—哈夫曼树

带权路径长度

• 路径长度：路径上所经历的边的个数
• 结点的权：结点被赋予的数值

树的带权路径长度： 树中所有叶节点的带权路径之和

公式及计算如下

哈夫曼树：也成为最优二叉树，就是含n的带权叶子结点的树之中带权路径长度最小的二叉树。在上面的两个树中第二棵树就是一颗哈夫曼树。

构造哈夫曼树，只需按照步骤一步一步来即可
哈夫曼树在构造的时候没有规定左右子树，所以其不唯一

哈夫曼树的构造方法

哈夫曼树的性质

哈夫曼树的应用
编码：对于一个字符串序列，用二进制数来表示每一个字符

固定长度编码
可变长度编码，因为会产生歧义，不可应用
使用哈夫曼树构造的过程如下
字母对应的数字是指字母出现的次数
按照规则构造出来的哈夫曼树，左0，右1
这样构造出来的编码不会产生歧义，且长度变短了