首页 > 试题广场 >

一个二叉树有N个度为2的节点，求叶节点的数目为多少？

[单选题]
一个二叉树有N个度为2的节点，求叶节点的数目为多少？ 
  • N-1
  • N
  • N+1
  • N+2
查看答案及解析
添加回答
推荐
牛客562号头像 牛客562号
选 C。
除根节点外，每个度为 2 的节点都贡献一个叶节点。而根节点贡献两个叶节点。
故为 N+1。
编辑于 2015-01-04 22:55:13 回复(0)
weilingry头像 weilingry
画一个三个节点的二叉树就明白了
发表于 2015-09-04 17:58:40 回复(0)
__sgf__头像 __sgf__
二叉树中 度为2的结点数 = 度为0的结点数 - 1
发表于 2022-03-22 14:57:23 回复(0)
huixieqingchun头像 huixieqingchun
n个结点的二叉树，度只可能是0，1，2，分别设其对应的结点个数为n0,n1,n2,则有n=n0+n1+n2;
又n结点的树只有n-1条边，故n-1=n1+2*n2
两式联合起来，可等到等式n0=n2+1

这里主要深入理解树的构造方式。
发表于 2016-05-07 21:41:22 回复(0)
啥头像 啥
总结点数 = 总度数 + 1

N + n0 + n1 = N*2 + n1 + 1

n0 = N + 1
发表于 2015-12-22 08:52:20 回复(0)
不吃葡萄皮头像 不吃葡萄皮
设度为1的节点数为x，度为0的节点数为y，则出度总和为N*2+x*1+y*0，而每个节点都会贡献一个入度，除了根节点入度为零之外，所以入度总和为x+y+N-1。在一棵树中，入度总是等于出度，因此 N*2+x*1+y*0=x+y+N-1,化简得y=N+1
发表于 2015-12-04 09:41:22 回复(0)
章鱼fun头像 章鱼fun
N + 1
因为：
1. 二叉树由度为0，1，2的节点组成，所以节点总个数 N = N0 + N1 + N2
2. 又因为二叉树中度为1和2的节点分别有1个子树和2个子树，所以子树节点个数N1 + N2
3. 二叉树总结点个数= 根节点 + 子树节点个数 = >>  N = N1 + N2 + 1
1中等式与3中等式相减得 N0 = N2 + 1
发表于 2015-04-11 15:58:18 回复(1)
牛客768117412号头像 牛客768117412号
叶节点＝ 度为二的节点数＋1
发表于 2022-04-29 14:49:01 回复(0)
看见我请叫我去刷题头像 看见我请叫我去刷题
叶节点极为度为0的节点，n0=n2+1,n2为度1的节点
n=n0+n1+n2
n-1=n1+n2
发表于 2022-04-06 20:56:46 回复(0)
ryanxw头像 ryanxw
二叉树中
度为2的结点数 = 度为0的结点数 - 1
发表于 2018-10-07 16:40:21 回复(0)
马小李头像 马小李
极端情况N=1，那么只有N+1个叶子节点，把这个结论往选择题里代
发表于 2015-09-08 15:48:34 回复(0)
提交观点

问题信息

搜狐 树
来自：搜狐2017校招研发工...
上传者：小小
难度：
11条回答 16676浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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