一、给定节点个数的二叉树个数为卡特兰数的原因

卡特兰数定义恰好符合二叉树的计数问题，即组成二叉树的各个节点的顺序并不影响树的形态，只有节点之间的父子关系才是关键因素，卡特兰数的定义本质上就是基于递归树结构的，正好符合上述递归式的求解方式。

对于n个节点的二叉树，我们把这n个都当作父亲节点，一定可以补充（n+1）个叶子节点，使之成为一棵（2n+1）个节点的完全二叉树。我们把原来的二叉树称作父亲树，即全是父亲节点的树。一棵父亲树一定与一棵完全二叉树一一对应。

对于一棵完全二叉树，分为叶子节点和父亲节点。首先，一棵父亲树到完全树加叶子节点只有一种方式，不会出现一颗父亲树对应多种完全树，所以这是一个映射。任意一棵完全二叉树，删除所有叶子节点都是一颗父亲树。所以父亲树到完全二叉树是满射。对于两个不同的父亲树，添加叶子后的完全二叉树一定不同。所以父亲树到完全二叉树是单射。所以父亲树到完全二叉树是双射。完全二叉树的数量与父亲树的数量是相同的。那么考虑（2n+1）个节点的完全二叉树的数量。根节点是一定的，思考剩下的2n个节点。这2n个节点一定是n个左儿子（儿子节点，不要看成叶子节点），n个右儿子。做不包括树根的先序遍历。节点是左儿子为0，右儿子为1。那么结果就是一个2*n个数的数列，其中n个0，n个1。由于是先序遍历，前缀0一定比前缀1多，即为卡特兰数。完全二叉树与先序遍历一一对应。所以完全树的数量为卡特兰数。

二、卡特兰数简介

卡特兰数是组合数学中一个常出现于各种计数问题中的数列。以中国蒙古族数学家明安图和比利时的数学家欧仁·查理·卡特兰的名字来命名，其前几项为（从第0项开始）：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

它的原理为：

设h(n)为catalan数的第n项，令h(0)=1，h(1)=1，catalan数满足递推式：h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)*h(0) (n≥2)

例如：h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2；h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5

另类递推式：h(n)=h(n-1)*(4*n-2)/(n+1)；h(n+1)=h(n)*(4*n+2)/(n+2)。递推关系的解为：h(n)=C(2n,n)/(n+1) (n=0,1,2,…)

递推关系的另类解为：h(n)=C(2n,n) – C(2n,n-1) (n=0,1,2,…)

Java应用：

import java.util.*;  import java.math.BigInteger;   public class Catalan {  //求卡特兰数     public static void main(String[] args){       int numberOfCatalan = 101; //要求多少个卡特兰数     BigInteger[] digis = new BigInteger[numberOfCatalan];        digis = generateCatalan(numberOfCatalan);             Scanner scanner = new Scanner(System.in);                int number;         while(true) {          number = scanner.nextInt();          if(number == -1) {            break;              String answer = digis[number].toString();              System.out.println(answer);              }        }      }           static BigInteger[] generateCatalan(int numberOfCatalan) {   //产生卡特兰数    BigInteger digis[] = new BigInteger[numberOfCatalan + 1];       BigInteger x = new BigInteger("1"); //名列前茅个卡特兰数为1      digis[1] = x;         int y = 0;        int z = 0;                    for(int counter = 2; counter <= numberOfCatalan; ++ counter) {                y = 4 * counter - 2;               z = counter + 1;                     digis[counter] = digis[counter-1].multiply(new BigInteger("" + y));              digis[counter] = digis[counter].divide(new BigInteger("" + z));          }        return digis;    }}  //使用递归的方式解决卡特兰数public static double CatalanNumber(int n) {       if (n == 1) {               return 1;        } else {         return CatalanNumber(n - 1) * 2 * (2 * n - 1) / (n + 1);       }}public static void main(String[] args) {       for (int i = 1; i <= 50; i++) {            System.out.println(i + "'s Catalan Number is " + CatalanNumber(i));       }}

三、二叉树简介

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点非常多只能有两棵子树，且有左右之分。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点。

二叉树的性质：

延伸阅读1：二叉树遍历

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有节点，使每一个节点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个节点转换成为一个线性序列来表示。

上一篇

人力资源管理制度有哪些?

下一篇

C的数据结构和C++的有区别吗?