Question

具有3个结点的二叉树有5种，可推测出具有4个结点的二叉树有（　　）种。

A.10
B.11
C.14
D.15

Answer 1

【答案】：C
题干给出具有3个结点的二叉树有5种，多增加一个根节点之后，可以有左右不同的3结点二叉树，所以左右分别有单个3结点子树的二叉树有2*5=10种；除此之外，3个结点可以构造成2结点子树和单节点子树，所有不同共有4种。
综上，具有4个结点的二叉树有14种。
也可以使用公式计算，。
这是1个求和公式。
N=0，是空树，只有1种形态，即A[0]=1。
N=1，是单节点树，只有1种形态。即A[1]=1。
当N>=2时，A[N]是对A[N]A[N-M-1]，M从0~N-1的求和。
如：
当N=2时，M=0~N-1=0~1，
A[2]=A[0] ×A[2-0-1]+A[1] ×A[2-1-1]=A[0] ×A[1]+A[1] ×A[0]=2，即A[2]=2。
当N=3时，M=0~N-1=0~2，
A[3]=A[0] ×A[3-0-1]+A[1] ×A[3-1-1]+A[2] ×A[3-2-1]
=A[0] ×A[2]+A[1] ×A[1]+A[2]A[0]=1×2+1×1+2×1=5，即A[3]=5。
当N=4时，M=0~N-1=0~3，
A[4]=A[0] ×A[4-0-1]+A[1] ×A[4-1-1]+A[2] ×A[4-2-1]+A[3] ×A[4-3-1]
= A[0] ×A[3]+A[1] ×A[2]+ A[2] ×A[1]+A[3]A[0]= 1×5+ 1×2+2×1+5×1=14，即A[4]=14。