哈夫曼树和哈夫曼编码

哈夫曼树的一些概念

· 哈夫曼树又叫最优二叉树,其特点为带权路径最短
· 树的带权路径长度(WPL)指树中所有叶子节点的带权路径长度之和
· 权值越大的结点,距离根结点越近
· 树中没有度为1的结点。这类树又叫做正则(严格)二叉树
· 存在哈夫曼n叉树,但不是每个待处理序列都可以构造,无法构造时可以补权值为0的结点

哈夫曼树的构造思想

反复选择两个最小的元素,合并,直到只剩下一个元素

哈夫曼编码的一些概念

· 是一种由哈夫曼树产生的编码方式
· (前缀码概念)任何一个字符的编码一定不会成为其他任何一个字符编码的前缀
· 即根通往任一叶子结点的路径都不可能是通往其余叶子结点路径的子路径
· 哈夫曼编码是能使给定字符串编码成01串后长度最短的前缀码
· 哈夫曼编码是针对确定的字符串来讲的~