開學已經倒計時，二叉樹的推論還不會證明？快坐上這輛快車！

匆匆，原以為只是一次普通的過年回家，沒想到變成了寒假連暑假。時間線推移，來到了八月底，很多同學已經摩拳擦掌準備開學了，然而也有同學對即將到來的線下考試惴惴不安。

多說無益，先把文章看完。

在學習資料結構的過程中，二叉樹是我們繞不開的一個坎兒。關於二叉樹的重要性呢，我們並不在本文中贅述，本文想要闡述的是二叉樹的三個推論和兩個定理。

具有n個結點的二叉樹可能的形態數為C（2n，n）/（n+1）。

當n等於0，也就是空樹的情形，公式成立。接著我們可以再來想一個簡單的例子：比如說一個具有三個結點的二叉樹，我們用窮舉的方式考慮。

可能的情形有：全部傾斜向左，全部傾斜向右，根和兩個孩子，根左右，根右左。總共是5種情形，代入我們的公式，沒有問題。

其實在這裡有個小彩蛋，看到這個公式應該是可以聯想起來一些東西的。n個元素順序入棧，所有可能的出棧序列情況數量也是這個公式。

完全二叉樹中1度結點（只有一個孩子的結點）不是0個就是1個。

具有n個結點的二叉樹，如果用二叉連結串列來儲存，其二叉連結串列彙總空指標域的個數為n+1個。

接著我們看兩個很相似的定理，很簡單。

n(n>=0)個結點的二叉樹，可以由它的中序序列和先序序列唯一確定。

n(n>=0)個結點的二叉樹，可以由它的中序序列和後序序列唯一確定。

其實，言外之意就是說，有先序序列和後序序列是不能唯一確定一個二叉樹的、當然，如果只有一種序列也無法唯一確定一個二叉樹。

那麼關於這兩個定理怎麼證明呢？這個曾經是一道考研題，證明的方法是採用數學歸納法，證明思路也並不複雜，同學們可以一起來領略一下。

證明：中序序列和先序序列可以唯一確定一棵二叉樹。

當n為0的時候，可以確定，二叉樹是一棵空樹，結論正確。假設節點數小於n的任何二叉樹都可以根據中序序列和先序序列唯一確定。所以只要可以證明對於n個結點的二叉樹，也可以根據中序序列和先序序列唯一確定，就可以完事了。

對於這一棵包含n個結點的二叉樹，可以假設這課二叉樹的先序序列是a0 a1 a2 a3……a(n-1)，它的中序序列為b0 b(k-1) bk b(k+1)……b(n-1)。

因為在先序遍歷中，二叉樹訪問順序是根左右，先訪問根節點，所以a0就一定是整個二叉樹的根，而且a0也一定會在中序序列中出現，假設它在中序序列中出現的位置bk就是a0。

所以，在中序序列中，k號結點之前的b0到b(k-1)就是根的左子樹的中序序列，而k號結點之後的b(k+1)到bn就是根的右子樹的中序序列。

與之對應的，在先序序列中，緊跟在a0之後的k個結點a1到ak就一定是左子樹的先序序列，其餘的a(k+1)到a（n-1）就一定是右子樹的先序序列。

結合假設2，結點數少於n的二叉樹可以由中序序列和先序序列唯一確定，所以我們談及的左子樹和右子樹可以分別根據它們的先序序列和中序序列唯一確定。

綜上所述，這棵二叉樹的左右子樹可以被唯一確定，所以整個二叉樹也就可以被唯一確定了。

開學之際，分不清興奮還是緊張；

各在一方，皆是為夢奔忙；

負重前行，我已學會眼裡帶光。

感謝閱讀，學習使人強大。