Question

一棵二叉树高度为h，所有节的度为0或2，则这棵树最少有多少个节点

Answer 1

这棵树最少有2h-1个节点。

分析：考虑按规则构造一棵高度为h的二叉树，可使得其节点数最少。

1、构造一个根节点。

2、为根节点构造2个儿子节点。

3、如果树的高度已经达到H，则结束；否则以上一步的根节点的右儿子最为新的根节点。

除根节点层只有1个结点外，其h-1层都有两个节点。

因此节点总数为2×(h-1)+1=2×h-1。

故这棵树最少有2h-1个节点。

扩展资料

树型结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。一个节点的子树数目称为该节点的度。

例：设一棵完全二叉树具有1000个结点，则此完全二叉树有____个叶子结点，有____个度为2的结点，有____个结点只有非空左子树，有____个结点只有非空右子树。

分析：叶子数＝[n/2]＝500 ，n2=n0-1=499。

另外，最后一结点为2i属于左叶子，右叶子是空的。

所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0。

答：则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。

Answer 2

节点最小的情况应该是如下：
o
/ \
o o
/ \
o o
/ \
o o
除根结点外，其他层都是2个结点
所以最少有2N-1

Answer 3

引用wzhappysnail的回答：
节点最小的情况应该是如下：
o
/ \
o o
/ \
o o
/ \
o o
除根结点外，其他层都是2个结点
所以最少有2N-1

N+1吧，
0
/ \
0 0
\
0
\
0