首页 > 试题广场 > ( )设高度为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)
带入特殊数值验证即可,选B
h=1,结点总数为1
h=2,结点总数为3
h=3,结点总数至少为5,
下面以此类推,每层至少加2
发表于 2019-10-03 17:07:09 回复(0)