首页 > 试题广场 >

一棵二叉树高度为h(根的高度为1),所有结点的度或为0或为2

[单选题]
一棵二叉树高度为h(根的高度为1),所有结点的度或为0或为2,则这棵二叉树最少有()个结点 
  • 2h
  • 2h-1
  • 2h+1
  • h+1
查看正确选项
添加回答
guyue头像 guyue
节点最少的情况为：除了根节点外，每层都有且仅有2个节点，所以共有2n-1个节点。
发表于 2015-09-01 10:15:59 回复(3)
在干嘛·头像 在干嘛·
由n0+n1+n2-1=2*n2+n1:得到：n0=n2+1；
n0表示度为0的根节点；想撑起来一个高度为h的就只能靠n2了，高度为h，只要的h-1层的n2就可以撑起来h的高度；
则：n2 = h-1；由n0=n2+1=h；
所有节点=n0+n2=2*h-1；

发表于 2017-08-02 17:40:38 回复(0)
繁星的夜空2012头像 繁星的夜空2012
就是考察的是没有度为1的结点的完全二叉树的知识点。------因为满二叉树的时候，二叉树的结点的个数最多。满足上题条件的，只有没有度为1的完全二叉树。
发表于 2016-12-28 15:12:55 回复(1)
夜夙头像 夜夙
发表于 2019-05-08 21:28:34 回复(0)
爱吃肉的王老五风度翩翩头像 爱吃肉的王老五风度翩翩
最多是 2^h - 1
最少 2*h - 1
编辑于 2019-04-20 10:59:54 回复(0)
sunlight_run头像 sunlight_run
除根节点，每层都仅有两个节点时最少
发表于 2017-06-28 10:48:21 回复(0)
InGodWeTrust头像 InGodWeTrust
叶子节点度为0，中间普通节点度为2。最少节点为2h-1个
发表于 2017-04-06 16:32:58 回复(0)
Rizzzz头像 Rizzzz
最少2*h-1,最多2^h-1
发表于 2017-04-06 16:20:17 回复(0)
蠢萌的公举姚头像 蠢萌的公举姚
没有度为1的结点为满二叉树，考虑只有两层的情况，结点最少。结点为3 ，树高2
编辑于 2017-03-04 10:28:19 回复(0)
水果忍者头像 水果忍者
当只有一个结点时，树高为1
发表于 2016-09-18 11:32:02 回复(0)
With_me_头像 With_me_
我还是没懂啊。是我理解错误了吗~~~~
发表于 2016-08-01 20:32:28 回复(0)
dkplatform头像 dkplatform
B 啊，这种以哈夫曼树为例子，总结个规律：
1   1
2   3
3   5
4   7
5   9
h   2H-1
发表于 2015-08-19 08:36:11 回复(0)
JasonZou头像 JasonZou
b
发表于 2014-12-29 10:13:58 回复(0)
提交观点

问题信息

树
难度：
13条回答 19978浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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