四个结点可以构成( )种不同形状的二叉树。 那N个节点呢？大家能告诉我什么公式、或者方法？

Question

谢谢大家了！

Answer 1

设n个节点的二叉树有f(n)种
N个节点，其中1个为根节点，则剩下有n-1个节点，这n-1个节点可以：
0个作为根节点的左子树（1种方法），n-1个节点作为根节点的右子树（f(n-1)种方法）
1个节点作为左子树（1种方法），n-2个节点作为右子树（f(n-2)种方法）
2个节点作为左子树（f(2)种方法），n-3个节点作为右子树（f(n-3)种方法）
以此类推：把这些情况全部加起来：
f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-2)*f(1) + f(n-1)*f(1)
其中f(0) = f(1) = 1

这个数叫做卡特兰数，具体计算方法可百度之

Answer 2

完全二叉树，除了叶子结点这层外，其他层结点都是度为2的，所以这样的树高度应该最矮了。