/ 注册

首页 > 试题广场 > ( )设高度为h（根的层次为1）的二叉树上只有度为0和

[单选题]

( )设高度为h（根的层次为1）的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为

先了解一下两叉树概念，节点最多有两个子树。

条件：

高度: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)

问题信息

上传者：呼呼L

难度：

2条回答 39收藏 2772浏览

热门推荐