N个节点二叉树有多少种形态

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

1)0个节点的二叉树只有1种形态,A[0]=0;1个节点的二叉树只有1种形态,A[1]=1 

2)n个节点(n>=2)的二叉树有 A[n] = ∑ [m=0到n-1] ( A[m]*A[n-m-1] ) ,求和的每一项,分别表示根的左子树为m个节点、右子树为 n-m-1个节点的情况 刚好就是catalan数,直接用catalan数的公式:h(n)=C(2n,n)/(n+1) 

http://zhidao.baidu.com/question/407856789.html?qbl=relate_question_0&word=5%B8%F6%BD%DA%B5%E3%20%B6%FE%B2%E6%CA%F7

你可能感兴趣的