首页 > 试题广场 >

哈夫曼树是()。以{4,5,6,7,8}作为叶结点的权值构造

[问答题]

哈夫曼树是()。以{4,5,6,7,8}作为叶结点的权值构造哈夫曼树,则其带权路径长度是()。

带全路径长度最小的二叉树

编辑于 2020-05-02 17:20:57 回复(0)
69
发表于 2017-04-12 19:38:12 回复(0)
哈夫曼树是带全路径长度最小的二叉树,权值较大的结点离根较近。
构造哈夫曼树的方法是:在所有节点中取出两个权重最小的节点,构造一棵树并计算其权重之和赋予到根节点上。同时将该权重再次与其他待比较的节点进行比较,最终构造出一颗哈夫曼树。
带权路径长度(Weighted Path Length)是哈夫曼树中所有构造节点的权重*当前节点所在的深度的和,如下图所示。因此本题的带全路径长度为(4+5)*3+(6+7+8)*2=69。

发表于 2018-03-16 21:28:43 回复(0)