首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
判断下列说法是否正确:在结点数多于1的哈夫曼树中不存在度为1
[单选题]
判断下列说法是否正确:在结点数多于1的哈夫曼树中不存在度为1的结点。()
正确
错误
添加笔记
邀请回答
收藏(3)
分享
纠错
5个回答
添加回答
1
推荐
白驹之过隙
选
A
。考察的是对哈夫曼树的概念。
霍夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。
哈夫曼树的构造:
根据给定的n个权值,选取权值最小的树作为左右子树,构造一个新的二叉树,左右子树的和为新二叉树的根节点。
在给定的n个权值中删除这两个左右子树,将新得到的二叉树根节点加入到给定的权值中,继续重复上述操作。
直到只含一棵树为止。
由此可见构成的哈夫曼树都是两个节点构成的左右子树,所以没有度为1的节点。
编辑于 2019-09-12 14:13:09
回复(0)
0
天尊墨宇
选
A
。考察的是对哈夫曼树的概念。
霍夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。
哈夫曼树的构造:
根据给定的n个权值,选取权值最小的树作为左右子树,构造一个新的二叉树,左右子树的和为新二叉树的根节点。
在给定的n个权值中删除这两个左右子树,将新得到的二叉树根节点加入到给定的权值中,继续重复上述操作。
直到只含一棵树为止。
由此可见构成的哈夫曼树都是两个节点构成的左右子树,所以没有度为1的节点。
发表于 2020-07-06 12:29:33
回复(0)
0
55开
实际上就是一个霍夫曼编码的过程,霍夫曼编码需要构建霍夫曼树,来求每个元素的编码
发表于 2019-09-25 21:46:59
回复(0)
0
搬砖队长
A、正确
哈夫曼树的构造:
根据给定的n个权值,选取权值最小的树作为左右子树,构造一个新的二叉树,左右子树的和为新二叉树的根节点。
在给定的n个权值中删除这两个左右子树,将新得到的二叉树根节点加入到给定的权值中,继续重复上述操作。
直到只含一棵树为止。
由此可见构成的哈夫曼树都是两个节点构成的左右子树,所以没有度为1的节点
可以用数学归纳法证明:
发表于 2019-09-11 22:57:42
回复(0)
0
T201908072136735
由赫夫曼树的构造过程可知,赫夫曼树的每一分支结点都是由两棵子树合并产生的新结点,其度必为2,所以赫夫曼树中不存在度为1的结点。
发表于 2019-09-11 17:51:43
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
树
上传者:
zsw3
难度:
5条回答
3收藏
2602浏览
热门推荐
相关试题
明明的随机数
数组
评论
(3704)
来自
华为研发工程师编程题
体育课测验(二)
广度优先搜索(BFS)
拓扑排序
dfs
评论
(2)
防火墙是怎么实现的?
计算机网络基础
评论
(1)
PMOS和NMOS的区别
元器件
评论
(1)
“乔布斯不做调查,张小龙不看数据。...
用户研究
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题
哈夫曼树的构造: