2回答

triump

2019-02-27

其实就是一个组合数学里最基本的乘法原理(分步)与加法原理（分类）的一个复合.
设f(n) 为n 个节点所构成的不同结构二叉树的总数.
则 f(n) = f(0)*f(n-1) + f(1)*f(n-2)+ f(2)*f(n-3) + .........f(n-1) * f(0)
其中f(0) = 1 f(1) = 1.
这个就是卡特兰数的递推关系.
可以这样理解，n 个节点从1开始编号. 然后枚举每个节点为根节点的情况（分类思想); 而当选定某个节点i 为根节点后，这个i 节点 的左右两边的节点数分别为 i -1 , n-i , 所以以这个i 为根节点的二叉树的个数为其左边节点构成的二叉树个数 * 其右边节点构成的二叉树个数, 即：f(i-1) * f(n - i).

由此就可能得到卡特兰数的递推关系，不重不漏.

0

1

liuyubobobo

赞！感谢分享：）

2019-02-27

共1条回复

liuyubobobo

2019-02-26

非常抱歉，由于卡特兰数属于组合数学的经典内容，不属于数据结构的内容，不在这个课程的范畴里。课程问答区主要用于解答课程相关的问题。请谅解。

同时，不在这个课程内的问题由于缺少相应的知识体系支撑，我也不可能在问答区一句话两句话就讲明白。还请在互联网上查找相关资料或者社区进行学习交流：）

不过组合数学确实是对于计算机专业来讲非常重要的数学分分支，同时也是离散数学中非常重要的数学分支。有机会我会考虑单独开课的：）

加油！：）

0

1

triump

其实就是一个组合数学里最基本的乘法原理(分步)与加法原理（分类）的一个复合. 设f(n) 为n 个节点所构成的不同结构二叉树的总数. 则 f(n) = f(0)*f(n-1) + f(1)*f(n-2)+ f(2)*f(n-3) + .........f(n-1) * f(0) 其中f(0) = 1. 这个就是卡特兰数的递推关系.

2019-02-26

共1条回复