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

Question

让我们通过列表表示树.

如果叶子的数量是两个,A和B.那么只有一棵树(AB).

如果叶子的数量是三个,A,B和C.那么有两棵树((AB)C)和(A(BC)).

那么如果有N片叶子,那里有多少棵树？

Answer 1

让带有N叶子的二叉树的数量为T(N).

我们T(1) = T(2) = 1可以立即看到,并且N > 2我们可以在根处分割,获得两个叶子较少的子树.或者,等效地,我们可以使用N来自两个非空二进制树的叶子组装二进制树,k并N-k分别使用和离开.两个子树都非空的条件转换为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)

它的计算速度比递归快得多.