高度给定的二进制树的数量

Question

我想知道我们有多少个带有$ n $ nodes的$ h $的二进制树（另一个问题是我们有多少个带有高度$ lfloor {lg（n）} rfloor $的二进制树。

编辑：我忘了添加节点的数量。

Answer 1

将高度$ h $作为最长的叶子路径的长度。固定根后，我们在两种情况下计算数字：

1. 左右子树的高度$ h $。树的数量$ = a_h^2 $
2. 只有一个子树具有高度$ h $。树的数量$ = 2 CDOT A_H CDOT（A_0+A_1+...+A_ {H-1}）$

$$ a_ {h+1} = a_h^2+2 cdot a_h cdot（a_0+a_1+...+a_ {h-1}）$$

Answer 2

我假设通过以下规范给出了二进制树：二进制树是（a）为（a），或（b）由根和两个（有序）子树组成。

我还假设定义高度，以便一棵完整的高度$ h $具有$ 2^{h+1} -1 $节点（例如，一个节点具有高度$ 0 $）。

令$ a_h $为最多$ h $的二进制树的数量。然后$ a _ { - 1} = 1 $和$ a_h = 1 + a_ {h-1}^2 $。这是 A003095. 。 $ h $的高度的树数为$ a_h -a_ {h -1} $，是 A001699. 。这两个序列都有$ alpha^{2^h} $的渐近学，对于某些$ alpha> 1 $。