校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
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