问题引出
问题：具有n个节点的不同形态的树（二叉树）有多少棵。 相关概念：
- 二叉树T和T’相似是指：二者都为空树或者都不为空树，且它们的左右子树分别相似。
- 二叉树T和T’等价是指：二者不仅相似，而且对应结点上的数据元素均相同。
二叉树的计数问题就是讨论具有n个节点、互不相似的二叉树的数目bn
题解
从生成树的角度
一棵具有n(n>1)个结点的二叉树可以看成是由一个根节点、一棵具有i个节点的左子树和一棵具有n-i-1个节点的右子树组成，因此可以推出以下公式：
演算得（递推过程有点复杂需要较好的数学功底）：
思前想后还是把递推过程放上来吧，有兴趣可以看看：
对于序列
定义生成函数：
因为：
根据上面的递推公式：
由此得：
即：
解此二次方程得：
由初值
应有
所以
利用二项式展开
当k=0时，上式的第一项为1，故有：
对照生成函数和上式而得：
即
从前中序遍历序列唯一性的角度
由前面二叉树的性质可以知道，树的前序遍历序列和中序遍历序列是唯一的，那么，由前序序列和中序序列也可以唯一确定一棵树。 因为：前序序列第一个元素是根，则可以在中序序列中根结点前的都是左子树的结点，依次类推可以确定一棵树。
确定中序序列的过程：
- 定根 A
- 在中序序列中找到 A
- 中序序列中的 A 的左部为 A 的左子树上的所有结点， A 的右部为 A 的右子树中的所有结点。
- 根据 A 的左子树的所有结点的前序序列确定 A 的左子树的根节点，它是 A的左儿子。
- 根据 A 的右子树的所有结点的前序序列确定 A 的右子树的根节点，它是A的右儿子。
- 在左、右子树中反复以上过程。至所有结点处理完毕。结束
由于问题所求的解是树形种数，则：
设二叉树的前序的序列为 1、2、3、… 、n
不同的中序序列对应着不同形态的二叉树
不同的中序序列的总数 = 不同形态二叉树总数
不同的中序序列在中序遍历时和相应的进出栈序列一一对应。
不同的进出栈序列的总数 = 不同形态的二叉树的总数
进出栈序列总数的计算为：
2n个方格中放置3个1的组合数 - 不合理的序列总数
按不同顺序进出栈得到的排列的数目为：
由二叉树的计数可推得树的计数，由“森林与二叉树的转换”中可知一棵树可转换成唯一的一棵没有右子树的二叉树，反之亦然。
所以具有n个节点的不同形态的树的数目和具有n-1个节点的二叉树的数目相同。
这里的树指的是有序树。
总结
树的计数问题的结果数称为Catalan数
Cat(n)同时也是把n+2边的凸多边形，连n-1条不相交的对角线，把这个凸多边形分成三角形的不同的方法的数目。
总结自：《数据结构（C语言版）》 清华大学出版社 严蔚敏、吴伟民编著
