N个结点可以构成多少个不同的二叉树？

来源：百度知道 编辑：UC知道 时间：2024/05/14 20:42:52
如题，结点没有编号，即结点是无序的。请给出推导的过程和结果公式，如果答案详细易动懂，追加奖励。
答案是(从2N中取得N的组合数)/（N+1）,有记得是怎么推导的么？

这个问题有点难度
先跟你说答案吧(1/n+1)*C(n,2n) 注:C是组合符号
关于这个推导的证明需要一个递推公式:
在n值小的情况下,可以直观看到b0=1 为空树,b1 =1只有一个节点,
b2 = 2, b3 = 5, 所以一般情况下,一个具有n个节点的二叉树可以看是一个根节点,一棵具有i个节点的左子树,和一棵具有n-i-1个节点的右子树组成
写成递推式为:
b0 = 1
b1 = b0*bn + b1*bn-1 + b2* bn-2 .... n >=1
(一直做下去可以做出上面结果,不过需要解很多个方程,比较复杂)
另外,以一个堆栈的出栈序列的个数考虑以上问题是另外一种思路

你参考一下《数据结构》上关于N个元素进栈出栈序列的推导
（在“栈”那一章），这两个问题是等价的。

答案是还是N