若一棵二叉树高度为H,其上只有度为0和度为2的结点,则此二叉树中包含结点数至少为多少。

求高手帮忙,希望有详细解释,非常感谢!

第1个回答  推荐于2016-12-01

二叉树中包含的结点数至少为 2*H-1

考虑按如下规则构造一棵高度为H的二叉树,可使得其节点数最少:

1) 构造一个根结点

2) 为根结点构造2个儿子结点

3) 如果树的高度已经达到H,则结束;否则以上一步的根结点的右儿子最为新的根结点,重复步骤2.

图片展示了上述过程是如何构造这种二叉树的。

本回答被提问者采纳
相似回答