哈夫曼编码主要应用场景
哈夫曼编码和二进制编码优缺点比较？
哈夫曼编码和二进制编码优缺点比较？
根据字符出现频率构建的带权重二叉树确定每个字符编码的。首先我们统计“alibaba”各个字符出现频率：a-3，b-2，l-1，i-1。由出现的频率我们有以下哈夫曼二叉树：
对应每个字符编码为：
所以最终“alibaba”整个字符串的编码为0 100 101 11 0 11 0。也就是说该字符串二进制哈夫曼编码位数为13位。
对于给定的一组权值W{7，2，8，4，16，3，9}构造出哈夫曼树。并计算带权路径？
7个权值是 7 2 8 4 16 3 9(1) 从小到大排序 2 3 4 7 8 9 16 (这是有序序列)(2) 每次提取最小的两个结点,取结点2和结点3,组成新结点N5,其权值2 35, 取数值较小的结点作为左分支,结点2作为左分支,而结点3就作为右分支.(3) 将新结点N5放入有序序列,保持从小到大排序: 4 N5 7 8 9 16(4) 重复步骤(2),提取最小的两个结点,结点4与N5组成新结点N9,其权值4 59, 结点4的数值较小,作为左分支,N5就作为右分支.(5) 将新结点N9放入有序序列,保持从小到大排序: 7 8 9 N9 16 [注意:新结点N9排在原有结点9的后面](6) 重复步骤(2),提取最小的两个结点,结点7与结点8组成新结点N15,其权值7 815, 结点7的数值较小,作为左分支,结点8就作为右分支.(7) 将新结点N15放入有序序列,保持从小到大排序: 9 N9 N15 16(8) 重复步骤(2),提取最小的两个结点,结点9与N9组成新结点N18,其权值9 918, 结点9作为左分支,N9就作为右分支.(9) 将新结点N18放入有序序列,保持从小到大排序: N15 16 N18(10)重复步骤(2),提取最小的两个结点,N15与结点16组成新结点N31,其权值15 1631, N15的数值较小,作为左分支,结点16就作为右分支.(11)将新结点N31放入有序序列,保持从小到大排序: N18 N31(12)重复步骤(2),提取剩下的两个结点,N18与N31组成新结点N49,其权值18 3149, 数值较小的N18作为左分支,N31就作为右分支. 最后得到哈夫曼树: N49 / N18 N31 / / 9 N9 N15 16 / / 4 N5 7 8 / 2 3带权路径长度(WPL):根结点N49到结点16的路径长度是2,结点16的带权路径长度是16*2根结点N49到结点9的路径长度是2,结点9的带权路径长度是9*2根结点N49到结点8的路径长度是3,结点8的带权路径长度是8*3根结点N49到结点7的路径长度是3,结点7的带权路径长度是7*3根结点N49到结点4的路径长度是3,结点4的带权路径长度是4*3根结点N49到结点3的路径长度是4,结点3的带权路径长度是3*4根结点N49到结点2的路径长度是4,结点2的带权路径长度是2*4所以,哈夫曼树的带权路径长度(WPL)等于16*2 9*2 8*3 7*3 4*3 3*4 2*4 127附:哈夫曼编码:规定哈夫曼树的左分支代表0,右分支代表1.从根结点N49到结点16,连续经历两次右分支,编码就是11从根结点N49到结点9,连续经历两次左分支,编码就是00从根结点N49到结点8,先经历右分支,再左分支,最后右分支,编码就是101如此类推,可以得出所有的结点的 哈夫曼编码:权值16: 11权值 9: 00权值 8: 101权值 7: 100权值 4: 010权值 3: 0111权值 2: 0110