首页 > 试题广场 >

对任何一棵二叉树T，如果其终端结点的个数为n0，度为2的结点

[单选题]
对任何一棵二叉树T，如果其终端结点的个数为n0，度为2的结点个数为n2，则（） 
  • n0=n2+1
  • 没有规律
  • n0=n2
  • n0=n2-1
添加回答
推荐
魔茧虫头像 魔茧虫
证明过程如下：
假设二叉树的0度,1度,2度结点为n0,n1,n2,总节点数为T
则有按照结点求和的
T = n0 + n1 + n2 （1）
按照边求和得：
T = n1 + 2 * n2 + 1 （2）
所以 （2） - （1）可得
n2 + 1 - n0 = 0
所以n0 = n2 + 1
编辑于 2016-09-01 21:44:23 回复(0)
灵魂画师。头像 灵魂画师。
 A  二叉树的性质 叶子节点n0 2度节点n2  no=n2+1
发表于 2016-09-04 16:21:43 回复(0)
tutuqie头像 tutuqie
特殊值代入，自己画一个就知道了
发表于 2015-09-09 12:13:05 回复(1)
雾z~霭头像 雾z~霭
度：节点拥有的子树数
二叉树的性质：n0=n2+1。
推导：假设二叉树拥有的分支数为：T,节点个数为：n
T= n-1；(只有根节点的分支是只出不进的，即每个节点都一定有进的分支，只有根节点没有，所以为n-1)
n= n0+n1+n2(二叉树的节点只有这三种度)；
T=2n2+n1(度为2的节点有两条分支，为1的拥有1条，为0的没有)
结合以上三式：T = n0+n1+n2-1=2n2+n1，故n0=n2+1
发表于 2018-03-08 20:46:02 回复(0)
MrLuan头像 MrLuan
假设度全部为１，则叶子节点只能有一个；
此时其中任何一个节点又度为１变为２则必然增加一个叶子节点，因此叶子节点必然比度为２的节点多１，因此答案选Ａ。
发表于 2016-09-04 16:44:51 回复(0)
蛊声孒头像 蛊声孒

结点度指的是一个结点的出度。
这道题我是自己画了一个写出的
红色的是度数为2的点n2一共三个
黄色度数为0也就是终端结点n0(叶结点)是四个
所以n0=n2+1
发表于 2015-09-26 09:22:17 回复(0)
牛客679724957号头像 牛客679724957号

对任何一个二叉树，若齐叶子结点数为n0,度为2的结点数为n2，则n0=n2+1。证明如下：

设一颗二叉树上叶子结点数为n0，单分支结点数为n1，双分支结点数为n2，则总结点数为：n0+n1+n2。

而一颗二叉树中，所有结点的分支数（即度数）应等于单分支结点数加上双分支结点数的两倍，即总分支数=n1+2n2。

由于二叉树中除了根结点以外，每个结点都有唯一的一个分支指向它，因此二叉树中：总分支数=总结点数-1。

即n1+2n2=n0+n1+n2-1。即n0=n2+1。

发表于 2021-09-12 09:55:36 回复(0)
轻易77头像 轻易77
树的性质：结点数等于度数加1
发表于 2021-02-18 00:01:07 回复(0)
正好有空头像 正好有空
二叉树性质：对任何一颗二叉树T，如果其终端结点数为n0,度为2的结点数为n2，则n0 = n2+1.

证明过程：设n为总结点数，n1为度为1的结点数，n2为度为2的结点数，n0为终端结点数（度为0）
分子数总数（连线、边）=n-1=n1+2*n2【1】。此外，二叉树的结点数（结点）n=n0+n1+n2。【2】
【1】和【2】相减可以得到n0=n2+1

编辑于 2020-01-14 14:38:16 回复(0)
Pinesong头像 Pinesong
A
发表于 2019-09-16 22:16:42 回复(0)
森林小狼头像 森林小狼
注意到N= n2 + n1 + n0;  按照边算总的节点数是边数目加一，变得数目为n1+2*n2.    由此可以推得n0 = n2 + 1

发表于 2019-03-08 15:28:26 回复(0)
Zoey11头像 Zoey11
n0=n2+1
发表于 2016-09-04 08:45:25 回复(0)
唯雨新愿头像 唯雨新愿
我觉是A项，树的性质
发表于 2015-09-05 16:39:26 回复(0)
提交观点

问题信息

树
来自：C++入门级笔试题合集（一）
难度：
13条回答 16785浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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