树---2.哈夫曼树

    xiaoxiao2021-03-26  7

    1.哈夫曼树(最优树):

    带权路径最短的树,在信息检索中很有用。(贪心算法)

    路径为0结点至多1个,路径为1的节点至多2个,路径为k的节点至多2^k个。

    2.哈夫曼算法:

    (1)n个权值为{W1,w2,,,wn}构成n棵二叉树集合{F1,F2...Fn};(2)选权值最小的两颗二叉树构成一颗新二叉树,更新新二叉树的权值。(3)重复2

    3.哈夫曼树应用

    (1)判定问题:成绩ABCDE各个等级分布不均匀,比较最少次数得到10000个学生的成绩分组

      (2)哈夫曼编码:电文传送时01编码代表不同含义,保证每个字符的编码都不是其他字符编码的前缀,使整体编码长度最短(左分支0 右分支1)

    4.哈夫曼编码实现可以对应最小堆

    转载请注明原文地址: https://ju.6miu.com/read-600176.html

    最新回复(0)