lihuan6
lihuan6
2019-11-10 17:26
采纳率: 50%
浏览 467
已采纳

数据结构------树 能不能帮忙解答下

有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为: 0.2,0.17,0.14,0.12,0.18,0.19,回答下面的问题:
(1) 试构造一棵哈夫曼树(小值左子树,大值右子树)
(2) 给出各个字符的编码(按照左0右1编码)
(3) 求其加权路径长度WPL

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • qq_43278334
    冉义 2019-11-10 19:05
    已采纳

    这个题目你只需要知道哈夫曼树就可以了
    首先将字符与加权一一对应,并将他们按权值大小排序:
    d 0.12 c 0.14 b 0.17 e 0.18 f 0.19 a 0.2
    哈夫曼树构造方法:
    假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:
    (1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);
    (2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
    (3)从森林中删除选取的两棵树,并将新树加入森林;
    (4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。
    ----来源百度百科
    (1)先挑选最小的两个节点,此处为dc,作为一棵树的左右叶子,用他们的和作为根节点,就够造成了一棵树。
    (2)以新产生的树为左子树,在未加入树中的节点在选择一个最小权值的节点,作为右叶子,构造一棵树。
    (3)重复(2),直至结束。
    然后根据左零右一得规则进行编码,即任意一个根节点,指向左孩子的树枝(姑且叫树枝)标注零,同理指向右孩子的标注一。如图

    图片说明

    确定编码:从根节点出发,到指定节点N所走过路径上的编码顺排,就构成了这个节点的编码,如a可以编码1指代。
    每个节点的编码图片中已经给出。
    求加权路径长度:题目中给出了每个节点的权值,可记为Wi(第i个节点的权重)你需要搞清楚普通路径长度是多少,根据够早的哈弗曼数,每一个节点到根节点的所要经过的边数称为路径长度,此处记为Li(第i个节点的...)
    加权路径长度即为全部节点LiWi的西格玛求和
    本题目构造的哈夫曼树WPL为
    0.2×1+0.19×2+0.18×3+0.17×4+0.14×5+0.12×5

    学过好久了,可能有纰漏,海涵。

    点赞 评论

相关推荐