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

[问答题]

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

杨😗

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

编辑于 2020-05-02 17:20:57 回复(0)

xuefu

发表于 2017-04-12 19:38:12 回复(0)

ZZZZ661

哈夫曼树是带全路径长度最小的二叉树，权值较大的结点离根较近。
构造哈夫曼树的方法是：在所有节点中取出两个权重最小的节点，构造一棵树并计算其权重之和赋予到根节点上。同时将该权重再次与其他待比较的节点进行比较，最终构造出一颗哈夫曼树。
带权路径长度(Weighted Path Length)是哈夫曼树中所有构造节点的权重*当前节点所在的深度的和，如下图所示。因此本题的带全路径长度为(4+5)*3+(6+7+8)*2=69。