首页 > 试题广场 >

一个4叉树，度为4的结点个数为6，度为3的节点个数是10，度

[单选题]
一个4叉树，度为4的结点个数为6，度为3的节点个数是10，度为2的节点个数是5，叶子节点个数为() 
  • 40
  • 42
  • 38
  • 44
添加回答
推荐
SunburstRun头像 SunburstRun
答案是D
              设度为1的节点个数为x,度为0的节点为y。该树的分叉数为4*6+3*10+2*5+x*1
又因为节点数=分叉数+1;
           节点数:6+10+5+x+y= 4*6+3*10+2*5+x*1+1
解得：y=44
编辑于 2015-11-02 12:32:33 回复(8)
牛客53488772号头像 牛客53488772号
节点数=边+1
发表于 2022-05-31 09:25:24 回复(0)
Pis头像 Pis
度    节点数        边
4        6              24
3        10            30
2        5              10
1        x                0
边 = 节点数 -1
64=21+x-1
x=44

发表于 2016-03-28 15:03:36 回复(4)
牛客876873号头像 牛客876873号
结点数=总分叉树+1

发表于 2016-08-02 18:00:40 回复(0)
fghfghggh头像 fghfghggh
1、结点数=总分叉树+1=4*6+3*10+2*5+1=65
2、叶子节点数=总结点数-n4-n3-n2=65-6-10-5=44
发表于 2018-09-24 11:31:17 回复(0)
青山崖野头像 青山崖野
利用边数和节点总数的关系：n1+n2*2+n3*3+n4*4=n-1=n0+n1+n2+n3+n4-1
发表于 2017-04-10 16:18:28 回复(1)
小年头像 小年
因为任一棵树中，结点总数=度数*该度数对应的结点数+1，设度为1的结点数为X,叶子结点数为n0,所以：
总结点数=4*6+3*10+2*5+1*X+1=n0+6+10+5+X(总结点数=度不为0的个数+叶子结点数)
解得：n0=44

发表于 2020-09-06 11:18:17 回复(0)
瞎唱歌的小七头像 瞎唱歌的小七
n个结点=n0+n1+n2+n3+n4
  =边数+1  (因为根结点没有父结点没有边，所以+1)
=n1+2n2+3n3+4n4+1

一消：n0 = n2+2n3+3n4+1
=5+20+18+1=44
发表于 2017-09-11 22:40:19 回复(0)
Forrestcloud头像 Forrestcloud
不管是几叉树，节点数等于=分叉数+1；

发表于 2017-09-05 21:08:14 回复(0)
一个锤子头像 一个锤子
做个笔记：
这种题目通常的解法就是构造两个方程消去求解：
设度为4,3,2,1,0的结点个数分别为x4,x3,x2,x1,x0,总结点数为N；
1.第一个方程根据结点所在层，各个度的结点数目之和等于总结点数
x4+x3+x2+x1+x0=N（代入数据就是6+10+5+x1+x0 = N）
2.第二个方程根据结点的下一层(即子结点)的数目之和等于总结点数：
4*x4+3*x3+2*x2+1*x1+1 = N（代入数据就是4*6+3*10+2*5+x1+1 = N）
（注:由于根节点不是任何结点的子结点所以计算的时候要单独加上）
根据这两个方程就可以求出叶子结点(x0)的数量

注意：
在二叉树当中两个方程分别为
x2+x1+x0 = N
2*x2+1*x1+1 = N

消去则有x2 = x0 - 1
是一个比较有用的结论




编辑于 2019-08-21 23:23:50 回复(0)
翻红的番茄头像 翻红的番茄

节点数=分支数+1
发表于 2020-02-23 14:54:27 回复(0)
Seaworth头像 Seaworth
分支总数=节点数-1
发表于 2019-12-13 14:50:27 回复(0)
哞哞牛哞哞头像 哞哞牛哞哞
总结点数=总度数+1
发表于 2019-10-10 21:09:36 回复(0)
滴滴内推2024头像 滴滴内推2024
节点数=分叉数+1
发表于 2018-06-12 10:45:29 回复(0)
lh_hl头像 lh_hl
总的节点数减1等于总的度数，即总边数；
发表于 2018-03-04 09:05:33 回复(0)
技术小咔头像 技术小咔
分叉数+1=结点数，这个关系很重要
发表于 2017-09-05 11:40:54 回复(0)
张大力头像 张大力
又没说度为1的结点数为0。求出的44应该是度为1和度为0的结点的总数。
发表于 2016-09-19 15:35:33 回复(1)
reakingf头像 reakingf
记错，原来结点的度指的是子树数，还以为要考虑入度。。。
发表于 2016-09-12 22:19:51 回复(0)
666662头像 666662
树结点数-1 = 边数
发表于 2016-09-01 16:41:01 回复(0)
炒更头像 炒更
分叉数就是分叉线
发表于 2016-03-23 17:02:32 回复(0)
提交观点

问题信息

树
来自：360公司2016数据...
难度：
20条回答 17617浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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