首页 > 试题广场 >

若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为(

[单选题]
若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（） 
  • n - 1
  • n/m - 1
  • (n-1)/(m-1)
  • n/(m-1) - 1
  • (n+1)/(m+1) - 1
查看正确选项
添加回答
牛客234296号头像 牛客234296号
度为m  那么对于所有的节点 要么度为0 要么度为m  
叶节点 = 非页节点 * (度-1) + 1    //为什么是m-1：因为每一个非业节点要占用一个位置
n = x*(m-1)+1
x = (n-1)/(m-1)

发表于 2017-09-12 20:47:39 回复(0)
ws1602348502头像 ws1602348502
C
首先说明一点,我们平时一般所说的哈夫曼树是指最优二叉树,也叫做严格二叉树（注意不是完全二叉树）,但是哈夫曼树完全不局限于二叉树,也存在于多叉树中,即度为m的哈夫曼树,也叫最优m叉树,严格m叉树（注意不是完全m叉树）.

这题表示哈夫曼树的节点 的度要么是0要么是m
设度不为0（即非叶结点 ）的个数为X
则总的结点数为：X+n
除根结点外，其余的每一个结点都有一个分支连向一个结点，对于度为m的每个结点都有m个分支，而度为0的结点是没有分支的，所以从分支的情况来看
总的结点数位：X*m + 1（这里的1为根结点）
两者相等，所以答案是 （n-1) / （m-1）
发表于 2015-08-14 11:58:36 回复(10)
牛客452770号头像 牛客452770号
首先说明一点,我们平时一般所说的哈夫曼树是指最优二叉树,也叫做严格二叉树（注意不是完全二叉树）,但是哈夫曼树完全不局限于二叉树,也存在于多叉树中,即度为m的哈夫曼树,也叫最优m叉树,严格m叉树（注意不是完全m叉树）.

这题表示哈夫曼树的节点 的度要么是0要么是m
设度不为0（即非叶结点   ）的个数为X  
则总的结点数为：X+n  
除根结点外，其余的每一个结点都有一个分支连向一个结点，对于度为m的每个结点都有m个分支，而度为0的结点是没有分支的，所以从分支的情况来看  
总的结点数位：X*m + 1（这里的1为根结点）  
两者相等，所以答案是 （n-1) / （m-1）
发表于 2017-05-11 09:54:02 回复(0)
huixieqingchun头像 huixieqingchun
度为m的哈夫曼树，只包含有度为0的结点和度为m的结点，可以设度为m的结点个数为X，则哈夫曼树中边的条数为mX，
而树中边的条数为总结点数减1，即n+X-1，两式相等，可得X的值。
发表于 2016-05-11 15:03:55 回复(0)
张佃鹏头像 张佃鹏
设有x个非叶子节点，那么按照总节点相等原则可以得出：m*x+1=n+x，所以求出x=[(n-1)/(m-1)]
发表于 2015-08-06 10:30:37 回复(5)
xiayan头像 xiayan 
哈夫曼树一定不存在只有一个子节点的节点，根据N0=N2+1,A也对

发表于 2016-08-11 11:34:18 回复(0)
prow头像 prow
m 不是等于2，A，C应该是一样的吧
发表于 2015-08-05 17:57:31 回复(0)
┮澈兮Д头像 ┮澈兮Д
我知道C是对的 ，大家说说A呢？
发表于 2015-04-12 19:01:25 回复(2)
_Jiang_头像 _Jiang_
  1. n0=1+n2+2n3· ··+(m-1)nm
  2. 其中只有n0，nm不等于0

编辑于 2019-08-30 22:08:14 回复(0)
Ray12345头像 Ray12345
根据两个前提条件，1 树的节点数等于度数加1，2 哈夫曼树只有度为2的非叶节点和度为0的叶子节点。设非叶节点为t，则总度数为2t，节点数就为2t+1，又节点数等于n+t，故两者相等，可得答案
发表于 2017-10-24 21:45:38 回复(0)
技术小咔头像 技术小咔
题目中的哈弗曼树只有度为0和度为m两种节点
发表于 2017-09-08 09:52:09 回复(0)
yuanyuan1029头像 yuanyuan1029
非叶结点数为x，根据  叉数+1=结点数   ==》   xm+1= n+x   ，可得x=(n-1)/(m-1)
发表于 2017-08-16 08:39:23 回复(0)
我是俊生啊头像 我是俊生啊
度为m的哈夫曼树,也叫最优m叉树，节点的度要么是0要么是m
发表于 2017-08-11 08:59:18 回复(0)
黏黏糖头像 黏黏糖
度为m的哈夫曼树，结点为0或m，因此n0 =(m-1)nm +1，即n=(m-1)nm +1，nm =(n-1)/(m-1)
发表于 2017-05-27 16:01:18 回复(0)
璎珞-沐头像 璎珞-沐
度为m的树，是树中所有结点的度的最大值。

发表于 2017-05-15 19:20:45 回复(0)
爱吃青菜皮卷面的byr头像 爱吃青菜皮卷面的byr
哈夫曼树完全不局限于二叉树,也存在于多叉树中,即度为m的哈夫曼树,也叫最优m叉树,严格m叉树（注意不是完全m叉树）.
编辑于 2017-02-18 23:58:19 回复(0)
Bruteforce头像 Bruteforce
边和点之间的关系
发表于 2016-02-18 08:06:45 回复(1)
提交观点

问题信息

树
难度：
17条回答 21144浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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