首页 > 试题广场 >

结点数为 5 的不同形态的二叉树一共有____[$##$]_

[填空题]
结点数为 5 的不同形态的二叉树一共有____1_____种。(结点数为 2 的二叉树一共有 2 种:一种是根结点和左儿子,另一种是根结点和右儿子。)

这是卡特兰数经典题, $n$ 个结点的树的同构数目是卡特兰数的第 $n$ 项。
卡特兰数递推式 $f[n] = \sum_{i = 2} ^ {n - 1} f[k] * f[n - k + 1]$
卡特兰数的计算公式 $\binom{2n}{n} / (n + 1)$

发表于 2018-10-11 15:18:03 回复(0)
2个节点-> 2
3个节点-> (2*1)*2+1*1=5
4个节点-> (1*2)*2+(1*5)*2=14
5个节点-> (1*14)*2+(1*5)*2+2*2=42
发表于 2019-10-16 18:53:01 回复(0)