学步园

题目：树的形态

思路：此题即为Catalan数的应用之一：N个结点可以构成多少不同的二叉树。

针对问题一，设N个结点可以构成f(N)个不同的二叉树，若左子树有M个结点，那么右子树就有N-M-1个结点，此时子树个数分别为(M, N-M-1)的二叉树有f(M) * f(N-M-1)种，而M可以从0取到N-1，所以f(N)=f(0)*f(N-1) + f(1)*f(N-2) + ··· + f(M)*f(N-M-1) + ··· + f(N-1)*f(0)，f(0) = 1，f(1) = 1。上式正是Catalan数的计算公式。

Catalan数的计算公式有如下几种：

C(2n,n)是组合数，此处选用红色标出的公式计算。

针对问题二，由于每个结点都可能是红黑色，所以N个结点就有2^N中可能的颜色排列，再乘以上面的二叉树的种类数，即为着色后的二叉树的种类数：2^N * f(N)

#include <iostream>
#include <math.h>
#include <queue>
typedef unsigned long long ULONG;

ULONG Factorial(ULONG N) {
		if (N < 0) return 0;
		ULONG result = 1;
		for (ULONG i = 2; i <= N; ++ i)
			result *= i;
		return result;
}

ULONG Catalan(ULONG N) {
	if (N < 0)  return 0;
	if (N == 0) return 1;
	if (N == 1) return 1;
	ULONG fn = Factorial(N);
	ULONG comb = Factorial(2*N) / (fn * fn);
	return comb / (N + 1);
}

void CatalanReadData() {
	std::queue<int> input;
	int N;
	while (std::cin >> N) {
		input.push(N);
	}
	while (!input.empty()) {
			ULONG cata = Catalan(input.front());
			std::cout << cata << std::endl;
			std::cout << (ULONG)pow((double)2, input.front()) * cata <<std::endl;
			input.pop();
	}
}

PS：有道，机试，2013，校招

[1] http://blog.csdn.net/ffjjqqjj/article/details/6081711

[2] http://baike.baidu.com/view/2499752.htm