【n个节点的二叉树有多少种形态（Catalan数）】
分析过程：

（1）先考虑只有一个节点的情形，设此时的形态有f(1)种，那么很明显f(1)=1
（2）如果有两个节点呢？我们很自然想到，应该在f(1)的基础上考虑递推关系。那么，如果固定一个节点后，左右子树的分布情况为1=1+0=0+1，故有f(2) = f(1) + f(1)
（3）如果有三个节点，（我们需要考虑固定两个节点的情况么？当然不，因为当节点数量大于等于2时，无论你如何固定，其形态必然有多种）我们考虑固定一个节点，即根节点。好的，按照这个思路，还剩2个节点，那么左右子树的分布情况为2=2+0=1+1=0+2。

所以有3个节点时，递归形式为f(3)=f(2) + f(1)*f(1) + f(2)。(注意这里的乘法，因为左右子树一起组成整棵树，根据排列组合里面的乘法原理即可得出)
（4）那么有n个节点呢？我们固定一个节点，那么左右子树的分布情况为n-1=n-1 + 0 = n-2 + 1 = … = 1 + n-2 = 0 + n-1。此时递归表达式为f(n) = f(n-1) + f(n-2)f(1) + f(n-3)f(2) + … + f(1)f(n-2) + f(n-1)
接下来我们定义没有节点的情况，此时也只有一种情况，即f(0)=1

那么则有:

f(0)=1，f(1)=1

f(2)=f(1)f(0)+f(0)f(1)

f(3)=f(2)f(0)+f(1)f(1)+f(0)f(2)

.

.

.

.

f(n)=f(n-1)f(0)+f(n-2)f(1)+……….+f(1)f(n-2)+f(0)f(n-1)

该数列称为卡特兰数（Catalan数），该递推关系的解为：

这里写图片描述

即含n个节点的二叉树有f(n)种形态。
【其他使用Catalan数解决的问题】

(1)矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？

(2)一个栈(无穷大)的进栈序列为1,2,3,…n,有多少个不同的出栈序列?

(3)有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)

(4)将一个凸多边形区域分成三角形区域的方法数?

(5)在圆上选择2n个点,将这些点成对连接起来，使得所得到的n条线段不相交的方法数。

(6)一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？

记n个节点的二叉树形态个数为A[n] 
1）0个节点的二叉树只有1种形态，A[0]=0；1个节点的二叉树只有1种形态，A[1]=1 
2）n个节点（n>=2）的二叉树有 A[n] = ∑ [m=0到n-1] ( A[m]*A[n-m-1] ) ，求和的每一项，分别表示根的左子树为m个节点、右子树为 n-m-1个节点的情况 刚好就是catalan数，直接用catalan数的公式：h(n)=C(2n,n)/(n+1) 
http://zhidao.baidu.com/question/407856789.html?qbl=relate_question_0&word=5%B8%F6%BD%DA%B5%E3%20%B6%FE%B2%E6%CA%F7

具有3个结点的二叉树有几种形态？




正确答案: B   你的答案: B (正确)

4


5


6


7








解析
这是一道牛客网上的测试题，因为题目是求3个节点的二叉树的形态，所以直接手画了。但是看解析的时候，发现评论区居然有计算公式，真的是大开眼界啊。



那个回答者给出的答案是：

这是组合计数问题，最常见的catalan数，C(n)=(1/(n+1))*((2*n)!/(n!*n!))

C(3) = (2*3)!/(3！*3！)/(3+1)=5




链接：具有三个节点的二叉树有多少种形态的解析

        我们知道具有n个结点的不同的二叉树的数量是个(这是一个卡塔兰数)，那么如何确定这些二叉树是什么样子的呢？下面是博主的思路：

        我们还知道一个入栈序列的不同出栈序列的数量也是个，于是博主就想：这不是巧了么，既然他们的数量是一样的，而且均不相同，那么是不是可以构建一个映射，使得不同的出栈序列和不同的二叉树进行一一对应呢。

        于是，在博主的做了深入的观察和思考后，发现对于其中一个出栈序列，其实和某个二叉树的中序遍历结果是相对应的，而经过进一步探索，发现入栈序列是所有二叉树的前序遍历结果。

        众所周知，一个二叉树的前序和中序遍历结果是可以唯一确定一棵二叉树的。

        然而在写代码的过程中博主又遇到了一个难题：就是如何输出一个入栈序列的全部出栈序列呢？为了解决这个问题，博主上某搜索网站参考了各位大神的代码，发现他们基本都是用回溯法解决的。于是在一番研究之下。我成功地写出了输出一个入栈序列的全部出栈序列的函数。

        这样一来，所有问题都解决了。然后经过了20分钟的编码。博主成功地写出了求解具有n个结点的不同的二叉树的所有前序增强序列的C++代码：

        另外如果大家有什么疑问或者见解可以在评论下方讨论，如果发现确实有什么错误的话，还请指正。

如下所示：

#include <iostream>

using namespace std;

static const int M = 100;
//依次代表的意思是结点数、栈、出栈序列、栈指针、出栈序列大小、输入顺序、二叉树中序序列，二叉树中序序列索引
static int n,stk[M],seq[M],stk_top=-1,seq_size=0,input[M],in[M],idx;

//根据二叉树的前序和中序遍历获取增强前序序列
static void getEnhencedPreorder(int root, int begin, int end) {
	if (begin > end) {
		cout << "#" << " ";
		return;
	}
	int i = begin;
	while (input[root] != in[i]) {
		i++;
	}
	cout << input[root] << " ";
	getEnhencedPreorder(root + 1, begin, i - 1);
	getEnhencedPreorder(root + (i - begin) + 1, i + 1, end);
}

//获取所有出栈序列
static void getSequence(int i) {
	if (i == n) {
		//收集结果
		idx = 0;
		for (int i = 0; i < seq_size; i++) {
			in[idx++]=seq[i];
		}
		for (int i = stk_top; i >= 0; i--) {
			in[idx++] = stk[i];
		}
		//根据前序和中序遍历获取其增强前序遍历序列
		getEnhencedPreorder(0,0,n-1);
		cout << endl;
	} else {
		//对于一个入栈的元素，可以入栈，也可以不入栈
		//但是每种情况都要检验

		//一、首先是元素入栈了
		stk[++stk_top]= input[i];
		getSequence(i + 1);
		stk_top--;

		//二、然后元素没有入栈，并且栈顶元素出栈了
		if (stk_top!=-1) {
			int top= stk[stk_top--];
			seq[seq_size++]=top;
			getSequence(i);
			seq_size--;
			stk[++stk_top] = top;
		}
	}
}

//相当于main函数
void stack_pop_sequence_re2_main() {
	cin >> n;
	for (int i = 0; i < n;i++) {
		input[i] = i + 1;
	}
	getSequence(0);
}

下面是一个示例(当n取3时)：

其入栈序列为1 2 3，输出结果为所有组成的二叉树的前序增强序列('#'号标识空)。