how many different binary trees you can build with N nodes?

how many different binary trees you can build with N nodes?

一棵二叉树可以看成根节点，左子树，右子树。因此N个节点，左子树如果有 j (<= N-1)个节点, 右子树有(N-1-j)个节点，故：

N个节点二叉树数目：

f(n) = f(n-1) + f(1)* f(n-2) +...+f(n-2)*f(1) + f(n-1) = sum( f(j) * f(n-j-1)) ( 0<=j<=n-1)

f(0) = 1, f(1) = 1, f(2) = f(1) + f(1) = 2

 

========================================

f(n) = f(n-1) + f(1)* f(n-2) +...+f(n-2)*f(1) + f(n-1)

第一项是1个根节点，0个左节点，（n-1）右节点的情况：1*f（n-1）

第二项是1个根节点，1个左节点，（n-2）右节点的情况：1*f（1）*f（n-2）

......

.....

..

最后一项是1个根节点，（n-1）个左节点，0个右节点的情况：1*f（n-1）

 

整个这个方程是一个递归的表示方法。这个递归的结果是h(n)=C(2n,n)/(n+1) (n=1,2,3,...)

C是选择符号。

这就是有名的卡特兰数。可以百科一下。