作业帮有n个结点的二叉树共有多少种?
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/24 20:56:32
有n个结点的二叉树共有多少种?
有n个结点的二叉树共有多少种?
有n个结点的二叉树共有多少种?
Program p9_3(Input,Output);
const maxlen=10000;
var c,h,i,j,n,n1,n2:longint;
fn,fno1,fno2,logfn:real;
fs1,fs2:ansistring;
fa,fb,fc:array [0..maxlen] of integer;
function gcd(m,n:longint):longint;
var r:longint;
begin
while n0 do
begin
r:=m mod n;
m:=n;
n:=r
end;
gcd:=m
end;
begin {Main program}
assign(input,'cont.in');
reset(input);
assign(output,'cont.out');
rewrite(output);
readln(fs1);
readln(fs2);
fno1:=0;
i:=1;
while (i
根据二叉树的递归定义来求解
设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
结果为 Cantala...
全部展开
根据二叉树的递归定义来求解
设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……)
收起
从深度考虑，深度最高n最低log2n。然后考虑第二深度（用词不是很规范，不知道该怎么说），对于深度为n的来说，第二深度为0;深度n-1，则指只能为1....然后再是第三深度，第四....根据每种深度可能出现的深度梯队进行排列组合，就是该深度的形态数，再把所有深度的形态数加起来就得解。
一般书上给出的证明和你问的不一样.关于二叉树节点计数的总个数有:
| 1 [n = 0]
全部展开
从深度考虑，深度最高n最低log2n。然后考虑第二深度（用词不是很规范，不知道该怎么说），对于深度为n的来说，第二深度为0;深度n-1，则指只能为1....然后再是第三深度，第四....根据每种深度可能出现的深度梯队进行排列组合，就是该深度的形态数，再把所有深度的形态数加起来就得解。
一般书上给出的证明和你问的不一样.关于二叉树节点计数的总个数有:
| 1 [n = 0]
B(n) = |
| n-1
| ∑ B(i) * B(n-i-1) [n >= 1]
i=0
解以上递归式,可以得出组合个数为C(2*n,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 也即 ZhangYv(like ASM,抵制日货) 所提供的答案
结果为 Cantalan 数 C（n+1）= 2n!/ [n!*(n+1)!] (n=1,2,3……)
收起