#哈夫曼编码、前缀码
哈夫曼树
【每次合并两个最小的】
以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树，求其带权路径长度：
构造方法是每次取最小的两个数， 合并成一个数， 然后循环这种做法， 直到只剩一个点为止。构造的树是
所以带权路径长度是 （4+5）3+（6+7+8）2=69
- 若为对句子中的字符编码，频率大的赋予大权重，左孩子可以编为0，右孩子为1
- 例如:字符串”alibaba”的二进制哈夫曼编码有（13）位。
根据字符出现频率构建的带权重二叉树确定每个字符编码的。首先我们统计“alibaba”各个字符出现频率：a-3，b-2，l-1，i-1。将a看为数字3，b=2,l=1,i=1,对四个数字{3，2，1，1}构建哈夫曼树，由出现的频率我们有以下哈夫曼二叉树：
对应每个字符编码为：
最终“alibaba”整个字符串的编码为0 100 101 11 0 11 0。
所以字符串”alibaba”的二进制哈夫曼编码有：31+22+31+31=13位
前缀码
- 前缀
设a=b1b2…bn，bi∈{0,1}是一个0-1序列(符号串)。序列b= b1b2…bi (1 i n)称为a的前缀。
例如,设a=010, 则, 0, 01 ,010都是a的前缀. - 前缀码
- 设Q ={a1, a2, …, am}是一个0~1序列集合 .
- 如果Q中没有一个序列是另一个序列的前缀 , 则称Q为前缀码.
- 例如，{0,10,110}就是一个前缀码，而{0,10,101}就不是前缀码。