首页 > 试题广场 >

( )设高度为h（根的层次为1）的二叉树上只有度为0和

[单选题]
设高度为h（根的层次为1）的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（） 
  • 2h
  • 2h - 1
  • 2h + 1
  • h + 1
查看正确选项
添加回答
犇流头像 犇流
先了解一下两叉树概念，节点最多有两个子树。
条件：
          高度:h   节点度=0  节点度=2
求此类两叉树最少的节点数：
A：2h
B：2h-1
C：2h+1
D：h+1
最少满足0度以及2度，那么至少2层，3个节点带入：
B符合条件
D符合条件
排除A,C
简单排除，若换成其他答案，此枚举不合适：
应使用递推：
    1                        1                      1
2     3                 2     3              2         3
                       4    5              4     5    6    7
  图1                  图2                       图3
不难得出结论，每增加一层h，那么节点数最少增加2
正确答案-----D
发表于 2019-10-06 12:48:34 回复(2)
Carpediem_头像 Carpediem_
看一下这个图，小太阳是结点，word画的有点粗糙，，希望能帮助到你，(●'◡'●)
发表于 2021-11-05 19:21:43 回复(0)
川久保玲球头像 川久保玲球
二叉树性质3：对任何一颗二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
由题意 该二叉树只有度为0和度为2的结点，则最下层之上每层至少有一个度为2的结点，即 n2 >= h-1, 
总结点数 = n0+n2 = 2n2+1 >= 2(h-1)+1=2h-1 
发表于 2020-08-01 14:41:24 回复(0)
笑着的程序员头像 笑着的程序员
带入特殊数值验证即可，选B
h=1,结点总数为1
h=2,结点总数为3
h=3,结点总数至少为5，
下面以此类推，每层至少加2
发表于 2019-10-03 17:07:09 回复(0)
提交观点

问题信息

树
上传者：呼呼L
难度：
4条回答 4706浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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