一道填空题c++，求讲解

Question

2． 结点数为 5 的不同形态的二叉树一共有__种。
（结点数为 2 的二叉树一共有 2 种：一
种是根结点和左儿子，另一种是根结点和右儿子。）

Answer 1

����������Ҫ�����ݽṹ�������IJ�ͬ�Ķ������м�����_�ٶ�֪�� https://zhidao.baidu.com/question/137072306257106645.html
答案为42个含有n个节点的二叉树的不同形式共有1/(n+1) * C(2n,n)个。所以5个点有42种（左4或右4或左3右1或左1右3或左2右2， 14+14+5+5+2*2=42)。

一个有n个结点的二叉树可以看作由三个部分组成，一个根结点，一个含i个结点的左子树，一个含n-i-1个结点的右子树，其中i的取值为0到n-1。

设所求的不相似二叉树有bn种，其中n是下标为结点的个数，

则b0=1(空二叉树） ，

b1=1(一个根结点），

b2=2(一种只有左子树，另一种只有右子树） ，

更一般的表达式为 ：

bn = 1, 当n=0时 ，

= b0bn-1 + b1bn-2 + ... + bn-1*b0, 当n>=1时 。