如果叶子节点从左到右的顺序固定，那么有多少个二叉树？

Question

让我们通过列表来表示树。

如果叶子节点的数量是两个，分别是A和B。那么只有一棵树（A B）。

如果叶子节点的数量是三个，分别是A、B和C。那么就有两棵树：((A B) C) 和 (A (B C))。

那么如果有N个叶子节点，会有多少棵树呢？

- louxiu

---

让我们通过列表来表示树。请问您如何实现？ - ypercubeᵀᴹ

这里有一个提示：如果叶子节点的数量是2的幂，则存在一棵二叉树，其叶子节点按指定顺序排列。 - gogognome

@gogognome 我认为那不是真的。例如，看看这个：http://draw.to/DfUt2p。它展示了一棵不平衡的8叶二叉树。 - Omri Barel

@louxiu 内部节点的度数有限制吗？例如，如果允许度数=1，则在给定顺序中具有N个节点的二叉树数量是无限的。此外，总节点数是否有限制？ - Omri Barel

确实，@OmriBarel，你是对的。我假设二叉树是平衡的，并且非叶节点有两个子节点。 - gogognome

Answer 1

让具有 N 个叶子节点的二叉树数量为 T(N)。

我们可以立即看到 T(1) = T(2) = 1，对于 N > 2，我们可以在根部分裂，得到两个叶子更少的子树。或者等价地，我们可以从具有 k 和 N-k 个叶子节点的两个非空二叉树组装一个具有 N 个叶子节点的二叉树。两个子树都非空的条件转化为 1 <= k <= N-1。因此我们有递归式：

      N-1
T(N) = ∑  T(k) * T(N-k)
      k=1

如果递归还没有确定，计算前几个值并不困难。

1,1,2,5,14,42,132,429,1430,4862,16796

并且搜索它们。人们会发现这些是卡塔兰数,

C(n) = (2*n)! / (n! * (n+1)!)

偏移量加一，因此

T(N) = C(N-1)

这可以比递归计算快得多。

- Daniel Fischer

---

+1，解释得很好。我也喜欢卡特兰数！许多事情都可以归结为它们。 - amit

请注意，这里对内部节点的度数有一个条件。如果对于某个子树，根节点的度数为1，则无法将该子树分成两个非空的子子树。 - Omri Barel

@OmriBarel 当然，每个非叶节点必须有两个子节点，否则对于所有 N > 0，你将拥有 ℵ_0 棵树。 - Daniel Fischer