二叉树的个数

来源：百度知道 编辑：UC知道 时间：2024/05/27 01:29:21
给出n个结点
问形态不同的二叉树有多少种
结点的度没有限制,只要是二叉树就可以
我记得是组合数学上面的结论
但我不记得了

根据二叉树的递归定义来求解

设Bn为所有结点数，显然B0=1，
对于n〉=1的情况，二叉树有1个根结点及n-1个非根结点，
而后者可分为两个子集，左子树和右子树分别为k个和n-k-1个结点
所以他们的结点数为分别为Bk和Bn-k-1个从而得知
Bn=Bn=B0*Bn-1+…+Bk*Bn-1-k
结果为 Cantalan 数 C（n+1）= 2n!/ [n!*(n+1)!] (n=1,2,3……)

设Bn为所有结点数，显然B0=1，
对于n〉=1的情况，二叉树有1个根结点及n-1个非根结点，
而后者可分为两个子集，左子树和右子树分别为k个和n-k-1个结点
所以他们的结点数为分别为Bk和Bn-k-1个从而得知
Bn=Bn=B0*Bn-1+…+Bk*Bn-1-k
结果为 Cantalan 数 C（n+1）= 2n!/ [n!*(n+1)!] (n=1,2,3……)
就这样了，希望你满意

是 2n+1 个