首页 > 试题广场 >

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

[问答题]

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

添加回答
杨😗头像 杨😗
带全路径长度最小的二叉树

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

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

问题信息

树
上传者：城市里的养猫者
难度：
3条回答 2072浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号