高度（或深度）h 的二叉树的最大可能数量是多少

Question

是否有任何封闭形式的公式可以找出具有高度或深度'h'的最大可能二叉树。我已经看到了给定节点数的二叉树总数的公式。但是我还没有看到任何给定固定高度或深度的封闭形式公式，无论节点数如何。

Answer 1

让我们使用递推关系来找到一个公式。设 n[h] 为高度为 h 的二叉树的数量。那么我们知道

n[0] = 1   //An empty tree
n[1] = 1   //A single leaf

一棵高度为i的二叉树可以这样构建：要么我们用一棵高度为i - 1的树作为左边的child。然后我们可以选择任意一棵高度从0到i - 1的树作为右边的child。或者我们选择一棵高度i - 1的树作为右边的child。然后我们可以选择任何高度从 0 到 i-2 的树作为左边的 child（注意最后一项中的 -2 以避免重复计算相同的树）。因此，

n[h + 1] = Sum{i from 0 to h}[n[h]*n[i]] + Sum{i from 0 to h-1}[n[h]*n[i]]

我们可以计算出前几个元素：

1
1
3
21
651
457653
210065930571
44127887745696109598901
1947270476915296449559659317606103024276803403

如果我们在 OEIS 中搜索此序列，我们会找到 this sequence。底部有一些公式，其中 none 看起来有一个封闭的形式。但这似乎没有必要。序列增长得如此之快以至于数字很快就会超过固定长度的数据类型。因此，很容易计算出这几个可以通过动态规划用您想要的数据类型表示的数字，甚至 pre-calculate 数字并将它们用作常量。

Answer 2

这类似于 Nico 的回答（它似乎在计算所有 non-leaf 节点有恰好两个 children 的树的数量）但计数每个节点最多两个children的树的数量。

这是一个Python脚本，用于通过递推关系计算这个数字：

def b(n):
    if n == 0:
        return 1
    else:
        return b(n-1) + b(n-1)**2 + 2*sum(b(k)*b(n-1) for k in range(n-1))

前几个值的输出是：1、2、10、170、33490、1133870930。序列可以在 OEIS here

中找到

高度（或深度）h 的二叉树的最大可能数量是多少

what is maximum possible number of binary trees for height (or depth) h

math

graph

binary-search-tree