设f(n)表示n个结点的二叉树的形态数
对于n=0的情况，树只有一种形态，即没有结点的状态，f(0) = 1。
对于n=1的情况，树只有一种形态，即f(1) = 1。
对于n=2的情况，固定一个结点为根节点，则剩下的另一结点分布在左子树，或右子树，且结点与结点相同(不会产生结点位置问题)，得f(2)=2。
对于更多情况，与n=2的思路相同，造成树的形态不同的是左子树和右子树上的结点数量。
可得f(n) = Σ( m=1 -> n )f(m) * f(n-m-1) ,根结点固定所以减一，m表示左子树所拥有的结点数，n-m-1则为右子树，由排列组合原理可知左树形态与右树形态相乘。
Java实现:
int f(int n){
int result = 0;
if(n==1||n==0)
return 1;
for (int i = 0; i < n; i++) {
result += f(i)*f(n-i-1);
}
return result;
}
即递归地求，左子树和右子树的形态数，排列组合将其相乘即可。
网友评论