精华内容
下载资源
问答
  • 哈夫曼路径
    2021-05-26 01:38:34

    这是在做一道编程提示遇到的,学习了一位博主的编码,其中有些问题未能理解,分析解决掉。

    首先什么是哈夫曼树:

    哈夫曼树,又称最优二叉树,是一类带权路径长度最短的树。

    也就是根节点到节点的中的长度最小,当然条件就是,每条路径都是有权重的,

    所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的 路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+…+Wn*Ln)

    0818b9ca8b590ca3270a3433284dd417.png

    此时WPL=32×1+24×2+2×3+7×3

    一般建立哈夫曼树的步骤为

    1,将所有左,右子树都为空的作为根节点。

    2,在森林中选出两棵根节点的权值最小的树作为一棵新树的左,右子树,且置新树的附加根节点的权值为其左,右子树上根节点的权值之和。注意,左子树的权值应小于右子树的权值。

    3,从森林中删除这两棵树,同时把新树加入到森林中。

    4,重复2,3步骤,直到森林中只有一棵树为止,此树便是哈夫曼树。

    太原理工网站给出了动画演示

    http://www.tyut.edu.cn/kecheng1/site01/suanfayanshi/Huffman.asp

    上面提到的根据权重排序,选出权重最小的两个,这个功能在优先队列中完全可以做到。所以在构建哈夫曼树时可以利用优先队列

    然后看看题目吧

    Input

    The input file will contain a list of text strings, one per line. The text strings will consist only of uppercase alphanumeric characters and underscores (which are used in place of spaces). The end of the input will be signalled by a line containing only the word “END” as the text string. This line should not be processed.

    Output

    For each text string in the input, output the length in bits of the 8-bit ASCII encoding, the length in bits of an optimal prefix-free variable-length encoding, and the compression ratio accurate to one decimal point.

    Sample Input

    AAAAABCD

    THE_CAT_IN_THE_HAT

    END

    Sample Output

    64 13 4.9

    144 51 2.8

    这里直接给出网上参考代码,然后分析

    #include

    #include

    #include

    #include

    #include

    using namespace std;

    #define M 1000050

    char str[M]; //全局变量中 默认初始化为0;

    int list[27];

    priority_queue< int,vector,greater >que;

    int main()

    {

    int ans,sum;

    int i,a,b,c;

    while(scanf("%s",str),strcmp(str,"END")){

    memset(list,0,sizeof(list));

    for(i=0;str[i];i++){

    if(isalpha(str[i]))

    list[str[i]-'A']++;

    else

    list[26]++;

    }

    sum=i*8;ans=i;c=0; //sum 为原等长编码需要的bit位 ans为hfm编码

    for(i=0;i<27;i++){

    if(list[i]){

    que.push(list[i]);

    c++;

    }

    }

    if(c>1) //c==1时,只有一种字母

    {

    ans=0;//注意只有一种字符的情况

    while(que.size()!=1)

    {

    a=que.top();

    que.pop();

    b=que.top();

    que.pop();

    ans+=a+b;

    que.push(a+b);

    }

    while(!que.empty())//使用后清空队列

    que.pop();

    }

    printf("%d %d %.1f\n",sum,ans,1.0*sum/ans);

    }

    return 0;

    }

    1、输入字符串部分

    for(i=0;str[i];i++){

    if(isalpha(str[i]))

    list[str[i]-'A']++;

    else

    list[26]++;

    }

    在ctype.h中,是一个宏,判读是否为大写字母

    list是一个数组int list[27]统计26个字母和下划线字符,用来统计多少个A、B,用字母到A的绝对距离作为数组的下标,数组对应的元素存放字母出现

    的次数。这里的写法非常简洁,数组元素++的写法,

    2、编码计数

    sum=i*8;ans=i;c=0;

    sum 为原等长编码需要的bit位 ans为hfm编码,i为字母的个数

    3、利用优先队列来考虑权重问题

    for(i=0;i<27;i++){ if(list[i]){ que.push(list[i]); c++; }

    }

    将字母出现的次数作为权重,压如队列中,C用于记录出现不同字母的个数。

    3、模拟建立哈夫曼树

    if(c>1)//c==1时,只有一种字母

    {

    ans=0;//注意只有一种字符的情况

    while(que.size()!=1)

    {

    a=que.top();

    que.pop();

    b=que.top();

    que.pop();

    ans+=a+b;

    que.push(a+b);

    }

    while(!que.empty())//使用后清空队列

    que.pop();

    }

    while中的过程完全按照,上面提到的步骤来

    如果加入输入AAAABBBCCD,根据上面步骤会得到这样一棵树

    0818b9ca8b590ca3270a3433284dd417.png 这样编码出来为 A: 0 1bit B: 10 2bit C: 110 3bit D: 111 3bit 所以中的编码位数就是出现次数×编码bit 1×4+2×3+3×2+3×1=19 这个就是带权路径长度,因为出现的次数就是权重,编码长度就是节点到根节点的层数, 如何在不把树建立起来,求带权路径长度,只要将这些权重全部加起来即可,正如程序中所做的那样 程序中 ans=(1+2)+(3+3)+(4+6); 这样分解出来 (1+2)+((1+2)+3)+(4+((1+2)+3)) 将(1+2)加了3次,实际就是加的层数。 所以ans就是这个哈夫曼树的带权路径和。

    更多相关内容
  • 哈夫曼树 带权路径

    千次阅读 2021-09-18 16:01:25
    一般的,我们是可以用常规的构造哈夫曼树求带权路径长度。 计算结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。 带权路径长度WPL(Weighted Path Length)最小的二叉树,也称为最优二又树。 在...

    树的带权路径长度

    (Weighted Path Length of Tree,简记为WPL)

    一般的,我们是可以用常规的构造哈夫曼树求带权路径长度。

    计算结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。

    带权路径长度WPL(Weighted Path Length)最小的二叉树,也称为最优二又树。

    在这里简单举个例子说一下:

    题目:

    给定6个字符(a,b,c,d,e,f),它们的权值集合W =(2,3,4,7,8,9),试构造关于W的一棵哈夫曼树,求其带权路径长度WPL。

    解:根据题意构造关于W的哈夫曼树如1图所示:
    在这里插入图片描述

    那么其带权路径长度WPL=(9+7+8)×2+4×3+(2+3)×4=80。
    在这里插入图片描述

    结点到树根之间的路径长度与该结点上权的乘积

    哈夫曼树

    构造哈夫曼树的办法是:在W中选出两个权小结点,并同时计算出它们的和,如果两个数的和正好是下一步的两个最小数的其中的一个,那么这个树直接往上生长就可以了,如果这两个数的和比较大,不是下一步的两个最小数的其中一个,那么就并列生长。
    在这里插入图片描述
    哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1L1+W2L2+W3L3+…+WnLn),N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,…n),可以证明哈夫曼树的WPL是最小的。

    展开全文
  • 哈夫曼树求最短路径

    2018-12-06 12:51:07
    上机后的代码,内容为构建哈夫曼树,并求最短编码长度。
  • hfm.rar_哈夫曼路径

    2022-09-24 17:01:42
    哈夫曼树 用于寻找二叉树中寻找最短的路径问题
  • 哈夫曼树带权路径长度

    万次阅读 多人点赞 2018-08-13 16:24:51
    可见,图b的带权路径长度较小,我们可以证明图b就是哈夫曼树(也称为最优二叉树)。   二. 怎么生成和计算? 1. 总结 ①先对权值从小到大排序。 ②选两个最小的加起来成为一个新结点,而这两个最小的值是新结点...

    一. 长什么样?

    左边是普通树,右边是哈夫曼树

    图a: WPL=5*2+7*2+2*2+13*2=54

    图b: WPL=5*3+2*3+7*2+13*1=48

    可见,图b的带权路径长度较小,我们可以证明图b就是哈夫曼树(也称为最优二叉树)。

     

    二. 怎么生成和计算?

    1. 总结

    ①先对权值从小到大排序。

    ②选两个最小的加起来成为一个新结点,而这两个最小的值是新结点的左右子结点。

    ③两个老的结点去掉,新的结点放入再次排序然后重复过程②。

    ④直到完全生成一棵树。

    ⑤计算的时候,只计算那些初始权值里面有的值,把它乘以深度(和传统说的深度不一样,是传统说的深度减一)加起来就是路径长度。

    2. 例子

    例:对于给定的一组权值w={1,4,9,16,25,36,49,64,81,100},构造具有最小带权外部路径长度的扩充二叉树,并求出他的的带权外部路径长度。

    解答过程(红色表示原来的权值结点,蓝色是加出来的结点):

    带权外部路径长度计算:

    WPL=2*100 + 3*64 + 2*81 + 4*25 + 3*49 + 3*36 + 5*16 + 6*9 + 7*1 + 7*4 =1078

    展开全文
  • 哈夫曼树结构及带权路径长度

    千次阅读 2022-05-19 16:56:31
    当用 n 个结点(都做叶子结点且都有各自的权值)试图构建一棵树时,如果构建的这棵树的带权路径长度最小,称这棵树为“最优二叉树”,有时也叫“赫夫曼树”或者“哈夫曼树”。 在构建哈弗曼树时,要使树的带权路径...

    哈夫曼树:

    当用 n 个结点(都做叶子结点且都有各自的权值)试图构建一棵树时,如果构建的这棵树的带权路径长度最小,称这棵树为“最优二叉树”,有时也叫“赫夫曼树”或者“哈夫曼树”。
    在构建哈弗曼树时,要使树的带权路径长度最小,只需要遵循一个原则,那就是:权重越大的结点离树根越近。在图 1 中,因为结点 a 的权值最大,所以理应直接作为根结点的孩子结点。

    哈夫曼树相关的几个名词

    路径:在一棵树中,一个结点到另一个结点之间的通路,称为路径。图 1 中,从根结点到结点 a 之间的通路就是一条路径。

    路径长度:在一条路径中,每经过一个结点,路径长度都要加 1 。例如在一棵树中,规定根结点所在层数为1层,那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。

    结点的权:给每一个结点赋予一个新的数值,被称为这个结点的权。例如,图 1 中结点 a 的权为 7,结点 b 的权为 5。

    结点的带权路径长度:指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如,图 1 中结点 b 的带权路径长度为 2 * 5 = 10 。

    构建哈夫曼树过程(1):

    对于给定的有各自权值的 n 个结点,构建哈夫曼树有一个行之有效的办法:

    1. 在 n 个权值中选出两个最小的权值,对应的两个结点组成一个新的二叉树,且新二叉树的根结点的权值为左右孩子权值的和;
    2. 在原有的 n 个权值中删除那两个最小的权值,同时将新的权值加入到 n–2 个权值的行列中,以此类推;
    3. 重复 1 和 2 ,直到所以的结点构建成了一棵二叉树为止,这棵树就是哈夫曼树。

     构建哈夫曼树过程(2):

     

    假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:


    (1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);
    (2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
    (3)从森林中删除选取的两棵树,并将新树加入森林;
    (4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。

     如:对 下图中的六个带权叶子结点来构造一棵哈夫曼树,步骤如下:

     

     

     

    性质

    每个初始结点都会成为叶子结点,双支结点都为新生成的结点
    权值越大离根结点越近,反之离根结点越远
    哈夫曼树中没有结点的度为1 (叶子节点:0 ,分支结点:2 )
    n个叶子结点的哈夫曼树的结点总数为2n − 1,其中度为2的结点数位n − 1

     

    展开全文
  • 哈夫曼路径问题

    千次阅读 多人点赞 2019-11-28 12:02:46
    哈夫曼树构造 哈夫曼树的构造并不难,无非就是从给定的...下列选项给出的是从根分别到达两个叶结点路径上的权值序列,能属于同一棵哈夫曼树的是 () 。(D) A、24,10,5 和 24,10,7 B、24,10,5 和 24,12,7 C、24,1...
  • 正常想要计算哈夫曼树的路径长度之和,是遍历一遍树,将叶结点的权值乘上深度再加和。 那么对于路径和的计算有这样一个公式: 哈夫曼树的带权路径长度和=等于所有非叶节点的权值和 所以说我们只需要每次将数组前两个...
  • 哈夫曼树带权路径长度怎么计算

    万次阅读 2021-01-17 13:41:58
    哈夫曼树的带权路径长度是什么?1.树的路径长度树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中,完全二叉树的路径长度最短。2.树的带权路径长度(Weighted Path Length of Tree,...
  • 哈夫曼树的带权路径长度的算法

    千次阅读 2021-05-10 20:06:24
    计算方法: ①先对集合中的结点按照权值从小到大排。 ②选两个权值最小的结点,将它们...⑤计算的时候,只计算那些初始权值里面有的值,把它们的【权值】*【权值到根节点的距离】,再全部相加得到带权路径长度。 ...
  • Huffman Tree哈夫曼树(霍夫曼树、赫夫曼树)权值路径长度WPL计算 计算定义:把构建成功的哈夫曼树的每一个边缘节点(叶子)值乘以该节点到根的路径长度,最后求合。 import random from binarytree import Node...
  • 哈夫曼树(Huffman Tree)也是一种特殊的二叉树,这种树的所有叶子结点都带有权值,从中构造出带权路径长度最短的二叉树,即哈夫曼树。
  • C语言哈夫曼编码转换

    2020-03-11 21:23:28
    给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
  • 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 二.实现步骤: 1....
  • 树的带权路径长度WPL最小的树为哈夫曼树,本文介绍哈夫曼的构造和应用
  • 计算WPL·哈夫曼树构建及带权路径长计算题目信息输入输出测试样例解答想法 题目信息 Huffman编码是通信系统中常用的一种不等长编码,它的特点是:能够使编码之后的电文长度最短。 输入 第一行为要编码的符号数量n 第...
  • 已知输入一串正整数,正整数之间用空格键分开,请建立一个哈夫曼树,以输入的数字为叶节点,求这棵哈夫曼树的带权路径长度。 【输入形式】 首先输入正整数的个数,然后接下来为接下来的正整数,正整数个数不超过10个...
  • 需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出哈夫曼树的带权路径长度(WPL)。 输入格式: 第一行输入一个数n,第二行输入n个叶结点(叶结点权值不超过1000,2<=n&...
  • ①带权路径:每个叶子结点都有权值,对于某叶子结点来说,它的带权路径就是“结点权值*从根节点到该结点的路径长度”。 ②哈夫曼树的构造方法:两个权值最小的叶子结点作为兄弟去构成一个非叶节点。(该父亲非叶...
  • 创建哈夫曼树并求带权路径长度

    千次阅读 2020-11-16 14:32:51
    创建哈夫曼树并求带权路径长度 【问题描述】根据给定的权重,构造哈夫曼树,输出其带权路径长度。 【输入形式】输入权重,空格作为分隔,回车结束,权重个数小于10。 【输出形式】哈夫曼树的带权路径长度。 【样例...
  • 笔试题:哈夫曼编码{4,9,2,7,5,12}的带权路径长度 解决思路: 首先构造哈夫曼树 在使用WPL=(W1*L1+W2*L2+W3*L3+…+Wn*Ln)计算带权路径长度 实现: 构造哈夫曼树: 每次取出最小的两个数构造第一层,在给出的...
  • 哈夫曼树编码

    2019-02-25 08:51:28
    2 掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。  【设计内容】   欲发一封内容为AABBCAB „„(共长 100 字符,其中:A 、B 、C 、D 、E 、F分别有7 、9 、12 、22 、23 、27个)的电报...
  • 本文用C++采用顺序存储实现求哈夫曼树(即最小生成树)的带权路径长度努力下面来了解一下哈夫曼树的构造以及如何求带权路径长度:哈夫曼树为带权路径长度最小的树哈夫曼哈夫曼树的顺序存储【问题描述】已知输入一串...
  • 思想: 先构建一个线性表,将树的结点存入,然后对树的结点进行升序排序,这样就保证了线性表的前两...而寻找带权路径长度可以使用递归的方法。 代码: public class Main { public static void main(String[] args) {
  • 哈夫曼树(Huffman(Huffman(Huffman Tree)Tree)Tree),又称为最优二叉树,指的是带权路径长度最小的二叉树。树的带权路径常记作: 其中,nnn为树中叶子结点的数目,wkw_kwk​为第kkk个叶子结点的权值,lkl_klk​为...
  • } 四、最短路径问题 最短问题的抽象: 在网络中,求两个不同顶点之间的所有路径中,边的权值之和最小的那一条路径。 (一)无权图的单源最短路径算法 void Unweighted( Vertex S) { Enqueue( S,Q); while( !...
  • 哈夫曼树的建立,求编码,译码,带权路径长度
  • 树的路径长度定义为;最优二叉树的定义;最优二叉树的定义;最优二叉树的定义;最优二叉树的定义;哈夫曼树; 2.在 F 中选取其根结点的权值为最小的两棵二叉树分别作为左右子树构造一棵新的二叉树并置这棵新的二叉树根结点...
  • 哈夫曼编码和带权路径计算

    千次阅读 2019-09-14 20:40:52
    哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树。下面用一幅图来说明。 它们的带权路径长度分别为: 图a: WPL=5*2+7*2+2*2+13*2=54 图b: WPL=5*3+2*3+7*2+13*1=48 可见,图b的带权路径长度较小...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,810
精华内容 5,924
关键字:

哈夫曼路径