首页 线上实习 课程 找实习 必考题 咨询 专栏 组团学 稳拿计划
校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 赫夫曼树
题目

设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点

A.99

B.100

C.101

D.102

上一题 下一题
解答

正确答案是 B

节点数=分叉数+1；
设度为2的节点有x，度为0的节点有y（叶子节点）；
则：分叉数：2*x+0*y=2x；
        节点数：199；
得：2x+1=199；x=99；y=100；
C 3条回复 评论
老干妈拌面

度为2的哈夫曼树的结点数为：2 * n - 1。n为叶子结点。
故2 * n - 1 = 199。解得n = 100。

发表于 2018-10-13 15:32:03
0 0
老干妈拌面

在哈夫曼树中，只有度为0（叶子结点），度为2的结点，没有度为1的结点，


设叶子结点的个数为n0，度为2的结点的个数为n2，

则总结点数=n0+n2=2*n2+1=199，

则n2=99,而n0=n2+1=100

发表于 2018-10-13 15:31:50
0 0
途安米

哈夫曼树也是二叉树，满足二叉树的性质 


哈夫曼树中没有度为1的结点，n0=n2+1

发表于 2018-10-13 15:30:55
0 0
问题信息
分类：数据结构 - 赫夫曼树
难度:
最新校招难题刷题，快来进刷题群吧
相关试题