二叉树的个数给出n个结点问形态不同的二叉树有多少种结点的度没有限制,只要是二叉树就可以我记得是组合数学上面的结论但我不记得了
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/27 03:51:25
二叉树的个数给出n个结点问形态不同的二叉树有多少种结点的度没有限制,只要是二叉树就可以我记得是组合数学上面的结论但我不记得了
二叉树的个数
给出n个结点
问形态不同的二叉树有多少种
结点的度没有限制,只要是二叉树就可以
我记得是组合数学上面的结论
但我不记得了
二叉树的个数给出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……)
是 2n+1 个
设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)!] (...
全部展开
设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……)
就这样了，希望你满意
收起