-
问题内容：wanted！二叉树的计数问题
- 原讨论链接：http://community.csdn.net/expert/topicview1.asp?id=5152150
- 所属论坛：数据结构与算法
审核组：其他
- 提问者：yudonglee
解决者：spirit_sheng
- 感谢：spirit_sheng
- 关键字：专题开发/技术/项目 数据结构与算法 参见 感激不尽 树 叉 结点 计数 乘法 形态 catalan 种
- 答案：
请问：具有n个结点的所有不同形态的二叉树有多少棵？
哪位大虾能帮我解决这个问题，感激不尽！
---------------------------------------------------------------
设具有n个结点的所有不同形态的二叉树有b[n]种，则
b[n] = (1/(n + 1))*C(2n,n)
证明如下：
考虑n个结点。除去根，剩下n-1个结点. 对左子树有b[k]种方式。对右子树有b[n - 1 - k] 种方式，由乘法原理，则b[n] = sum[k = 0 .. n - 1](b[k]*b[n - 1 - k])
由于b[1]=1
而这正好是Catalan数，关于Catalan数，参见以下：
http://fqyy.nbu.edu.cn/pc/pccon.php?id=56&nid=2590&pid=0&tag=0&tid=84&p=p
- 评价：
给朵鲜花（0）
扔个鸡蛋（0）
