“ 卡特兰数又称卡塔兰数,是组合数学中一种常出现于各种计数问题中的数列。”...一、简单介绍
卡特兰数是一个数列,其前几项为(从第零项开始) : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, ......因为k最后一个出栈,而进栈顺序又是从小到大来的,所以k前面的k-1个数在k进栈以前就已经全部出栈了,我们把前面k-1个数看出一个整体,那么全面k-1个数的出栈情况实际上就有h(k-1)种。...因为中间有k隔着,而它们又必须按照从小到大的次序进栈,所以这两部分进出栈是相互不影响的。
很明显可以看出,该表达式就是卡特兰数的递推式。...+S(n-1)S(0),显然S(n)是卡特兰数。
2.6满二叉树个数
【问题描述】
n+1个叶子的满二叉树个数为多少?
【问题分析】
不再分析,答案为h(n)。