一、給定節點個數的二叉樹個數為卡特蘭數的原因

卡特蘭數定義恰好符合二叉樹的計數問題，即組成二叉樹的各個節點的順序并不影響樹的形態，只有節點之間的父子關系才是關鍵因素，卡特蘭數的定義本質上就是基于遞歸樹結構的，正好符合上述遞歸式的求解方式。

對于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++的有區別嗎?