N个结点的二叉树形态

设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;

}

即递归地求，左子树和右子树的形态数，排列组合将其相乘即可。