首页 > 试题广场 >

一个二叉树有100个子节点数为2的节点，100个子节点数为1

[单选题]
一个二叉树有100个子节点数为2的节点，100个子节点数为1的节点，那么个子节点数为0的节点（叶节点）的个数为： 
  • 101
  • 100
  • 200
  • 300
  • 99
  • 1
查看答案及解析
添加回答
＜（－︿－）＞...头像 ＜（－︿－）＞...
设一颗二叉树有n个节点，则其便有n-1条边，让拥有两个子节点的节点为n2，拥有一个子节点的节点为n1，叶子节点为n0，则有n0+n1+n2=n，
从树根往下看，当一个节点有两个子节点时，会向下伸出两条边，拥有一个子节点时向下伸出一条边，无子节点则不向下伸出边，故有n2个节点拥有两个子节点就有2*n2条边，所以0*n0+1*n1+2*n2=n-1，又n0+n1+n2=n，所以0*n0+1*n1+2*n2=n0+n1+n2-1，n0=n2+1=100+1=101。
发表于 2019-08-27 21:21:18 回复(0)
codeor头像 codeor
一个二叉树，叶子结点数=度为2的结点数+1
发表于 2019-07-23 21:35:37 回复(0)
ZTF头像 ZTF

直接用二叉树结论：叶节点个数等于度为2的节点个数+1

证明：假如一颗二叉树有俩节点，一个根节点，一个左叶节点。那么此时，度为2的为0，叶节点为1。如果再添一个节点：

1、这个节点放在叶节点上，不变。

2、这个节点放在根节点，度为2的变为1，度为0的叶节点变为2。

以此类推，度为2的增加1，相应的度为0的增加1。

发表于 2019-05-28 10:05:19 回复(0)
dong1234头像 dong1234
度数(边数) = 所有节点数-1：
这里度数=2*100+100=300，节点数：100+100+叶子节点数
所以叶子节点数=101
发表于 2017-08-06 09:39:05 回复(4)
丨太阳与月亮丨头像 丨太阳与月亮丨
A
首先，假设该二叉树有n个节点，则有n - 1条边，这是因为除了根节点，其余的每个节点都有且只有一个父节点，那么这n个节点恰好为树贡献了n-1 条边。这是从下往上的思考，而从上往下(从树根到叶节点)的思考，容易得到每个节点的度数和 0*n0 + 1*n1 + 2*n2 即为边的个数。
因此，我们有等式 n-1 = n1 + 2*n2，把n用n0+n1+n2替换，
得到n0 + n1 + n2 - 1 = n1 + 2*n2，于是有

n0 = n2 + 1。

n0=n2+1=100+1=101
编辑于 2017-06-29 15:43:50 回复(2)
oukohou头像 oukohou
总结点个数 n = n0 + n1 + n2；
所有的孩子节点个数为 2 * n2  + 1 * n1， 度为2的节点有2个孩子节点，度为1的节点有1个孩子节点;
只有根节点不是孩子节点，孩子节点个数比总结点个数少一个， n  = 2 * n2 + 1 * n1 + 1；
即得等式：
    n = n0 + n1 + n2 = 2 * n2 + 1 * n1 + 1
    ==》 n0 = n2 + 1
    


发表于 2017-08-21 09:40:18 回复(0)
南京路🇨🇳头像 南京路🇨🇳
n=n0+n1+n2=n0*0+n1*1+n2*2+1   => n0=n2+1
发表于 2020-03-19 14:14:25 回复(0)
慕宗悫之长风头像 慕宗悫之长风
自己画一个，4个字节点为2，4个字节点为1，得到5，然后统计类推得到101。
发表于 2019-03-29 21:18:30 回复(0)
Immortal201803091010221头像 Immortal201803091010221
n0 + n1 + n2 - 1= 0 * n0 + 1 * n1 + 2 * n2
发表于 2018-05-11 12:28:19 回复(0)
北方有佳人zz头像 北方有佳人zz
n0 = n2 + 1
发表于 2018-01-22 13:28:44 回复(0)
春风十里不如一碗凉皮头像 春风十里不如一碗凉皮
N0=N2+1
发表于 2017-10-18 17:09:58 回复(0)
Self_made头像 Self_made
根据定理，n0＝n2+1
发表于 2017-08-22 23:19:44 回复(0)
诸葛逸洛头像 诸葛逸洛
不论点数为1的节点是怎么连接的，都至少有1个叶节点为0，只能选首选和末选，再加上节点数为2的情况下不可能没有节点数为0的页节点。
所以选101
发表于 2017-08-22 16:43:47 回复(0)
渣渣求个offer头像 渣渣求个offer
n个节点，n-1条边
发表于 2017-08-17 23:23:41 回复(0)
稻草人a头像 稻草人a
度为0的节点数等于度为2的节点数加1
发表于 2017-07-22 23:26:15 回复(0)
提交观点

问题信息

树
来自：阿里巴巴2017秋招研...
上传者：牛100
难度：
15条回答 8510浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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