首页 > 试题广场 >

一颗二叉树有5个叶子结点，有3个出度为1的结点，问二叉树总共

[单选题]
一颗二叉树有5个叶子结点，有3个出度为1的结点，问二叉树总共有多少个结点。 
  • 11
  • 12
  • 13
  • 14
添加回答
baohao头像 baohao
将二叉树的度为0的节点数记为n0，度为1的节点数记为n1，度为2的节点数记为n2。
又因为，二叉树只有度为0，1，2的节点，没有其它节点。
得出，二叉树总节点数 N = n0 + n1 + n2 （此为公式1）
再因为，二叉树总度数（树枝的总数量）永远比节点数少1，这个很简单就能理解。
二叉树总度数 C = N - 1，总度数C ＝ 2 ＊n2 ＋ 1 ＊ n1。
得出，N ＝ 2 ＊ n2 ＋ n1 ＋ 1（此为公式2）
综上公式1和公式2推出：n0 ＝ n2 ＋ 1
这就是二叉树的性质之一：度为0的节点数 等于 度为2的节点数加1。

由题目已知条件：
度为0的节点（叶子节点）数量为5个，即 n0 ＝ 5
度为1的节点数量为3个，即 n1 ＝ 3
由上面的二叉树性质可知 度为2的节点数量为 n2 ＝ n0 － 1 ＝ 5 － 1 ＝ 4
最后二叉树总节点数辆N ＝ n0 ＋ n1 ＋ n2 ＝ 5 ＋ 3 ＋ 4 ＝ 12
答案为12个，选B。
发表于 2015-11-07 21:19:41 回复(0)
cheng城广头像 cheng城广
试画一颗二叉树即可得知总结点为n时,总出度为n-1
二叉树**度只有0或1或2,
有5个叶子节点（出度即为0）和3个出度1的节点，则剩下n-5-3个出度为2的节点数。
综上总出度n-1=5*0+3*1+(n-8)*2
得到n=12
发表于 2019-03-06 08:46:46 回复(0)
紫雪凝香头像 紫雪凝香
答案选B
叶子结点即度为0的结点，记度为2的结点为n2.
由题，n0=5,n1=3，根据二叉树性质，n0=n2+1,则n2=4，
所以n=n0+n1+n2=12

发表于 2015-06-24 11:49:35 回复(0)
zt_xcyk头像 zt_xcyk
B
二叉树性质：终端结点（叶子节点）个数n0 = 度为2的节点（有2个孩子）个数n2 + 1
即n0 = n2 + 1.
3个出度为1的结点
5个叶子结点
度为2的节点=5-1=4
所以总个数 = 3 + 5 +4= 12
编辑于 2015-11-06 22:03:46 回复(0)
along8909头像 along8909
B. 12
        {x}
      {x, x}
    {x,x} {x,x}
{x,x}{x} {}{}
{x}{x}{}
{}{} 
发表于 2015-01-03 01:22:07 回复(0)
提交观点

问题信息

网易 树
上传者：小小
难度：
5条回答 14131浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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