Question

n个结点并且其高度为n的二叉树的数目是多少

最好是能有个方法！！！呼呼，谢谢了！

Answer 1

n个节点高度为n。。。这个不就是每个节点只有一个孩子么。。。那么不同种类就是由你结点是左孩子还是右孩子决定的，一共n-1条边，就是2的n-1次方种二叉树

Answer 2

除了最末层的叶子结点外,其他n-1个非终端结点都有且只有一个孩子结点,大概是2的n-1次方个吧

Answer 3

无法满足题中“高度为N”这一条件。数学老师真的别来做计算机题了。

Answer 4

　　当n=1时，只有1个根节点，则只能组成1种形态的二叉树，令n个节点可组成的二叉树数量表示为h(n)，则h(1)=1; h(0)=0;
　　当n=2时，1个根节点固定，还有2-1个节点。这一个节点可以分成（1,0），（0,1）两组。即左边放1个，右边放0个；或者左边放0个，右边放1个。即：h(2)=h(0)*h(1)+h(1)*h(0)=2，则能组成2种形态的二叉树。
　　当n=3时，1个根节点固定，还有2个节点。这2个节点可以分成（2,0），（1,1），（0,2）3组。即h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=5，则能组成5种形态的二叉树。
　　以此类推，当n>=2时，可组成的二叉树数量为h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0)种，即符合Catalan数的定义，可直接利用通项公式得出结果。
　　令h(1)＝1,h(0)=1，catalan数（卡特兰数）满足递归式：
　　h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2)
　　另类递归式：
　　h(n)=((4*n-2)/(n+1))*h(n-1);
　　该递推关系的解为：
　　h(n)=C(2n,n)/(n+1) (n=1,2,3,...)