若二叉树只有度为0和度为2的结点则该二叉树的分支总数是多少给出推理过程

Question

这有点类似满二叉树度为0只有叶子结点没有分支一个度为2的结点有两个分支设度为2的结点共有n2个则二叉树分支总数N=2*n2

Answer 1

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

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

1)构造一个根结点

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

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

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