n个结点的二叉树一共有多少种形态

记n个节点的二叉树形态个数为A[n]

1）0个节点的二叉树只有1种形态，A[0]=0；1个节点的二叉树只有1种形态，A[1]=1

2）n个节点（n>=2）的二叉树有
$A[n]={\sum_{m=0}^{n-1}}(A[m]+A[n-1-m])$
，求和的每一项，分别表示根的左子树为m个节点、右子树为 n-1-m个节点的情况。（总共n个节点，左子树m个节点，根节点有1个，那么右子树的节点数为n-1-m个）

刚好就是catalan数，直接用catalan数的公式：h(n)=
$C_{2n}^{n} /(n+1)$
=
$(2n)!/n!*(n+1)!$