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

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

在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的過程中，二叉樹是我們繞不開的一個(gè)坎兒。關(guān)于二叉樹的重要性呢，我們并不在本文中贅述，本文想要闡述的是二叉樹的三個(gè)推論和兩個(gè)定理。

具有n個(gè)結(jié)點(diǎn)的二叉樹可能的形態(tài)數(shù)為C（2n，n）/（n+1）。

當(dāng)n等于0，也就是空樹的情形，公式成立。接著我們可以再來想一個(gè)簡單的例子：比如說一個(gè)具有三個(gè)結(jié)點(diǎn)的二叉樹，我們用窮舉的方式考慮。

可能的情形有：全部傾斜向左，全部傾斜向右，根和兩個(gè)孩子，根左右，根右左?？偣彩?種情形，代入我們的公式，沒有問題。

其實(shí)在這里有個(gè)小彩蛋，看到這個(gè)公式應(yīng)該是可以聯(lián)想起來一些東西的。n個(gè)元素順序入棧，所有可能的出棧序列情況數(shù)量也是這個(gè)公式。

完全二叉樹中1度結(jié)點(diǎn)（只有一個(gè)孩子的結(jié)點(diǎn)）不是0個(gè)就是1個(gè)。

具有n個(gè)結(jié)點(diǎn)的二叉樹，如果用二叉鏈表來存儲(chǔ)，其二叉鏈表匯總空指針域的個(gè)數(shù)為n+1個(gè)。

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

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

n(n>=0)個(gè)結(jié)點(diǎn)的二叉樹，可以由它的中序序列和后序序列唯一確定。

其實(shí)，言外之意就是說，有先序序列和后序序列是不能唯一確定一個(gè)二叉樹的、當(dāng)然，如果只有一種序列也無法唯一確定一個(gè)二叉樹。

那么關(guān)于這兩個(gè)定理怎么證明呢？這個(gè)曾經(jīng)是一道考研題，證明的方法是采用數(shù)學(xué)歸納法，證明思路也并不復(fù)雜，同學(xué)們可以一起來領(lǐng)略一下。

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

當(dāng)n為0的時(shí)候，可以確定，二叉樹是一棵空樹，結(jié)論正確。假設(shè)節(jié)點(diǎn)數(shù)小于n的任何二叉樹都可以根據(jù)中序序列和先序序列唯一確定。所以只要可以證明對(duì)于n個(gè)結(jié)點(diǎn)的二叉樹，也可以根據(jù)中序序列和先序序列唯一確定，就可以完事了。

對(duì)于這一棵包含n個(gè)結(jié)點(diǎn)的二叉樹，可以假設(shè)這課二叉樹的先序序列是a0 a1 a2 a3……a(n-1)，它的中序序列為b0 b(k-1) bk b(k+1)……b(n-1)。

因?yàn)樵谙刃虮闅v中，二叉樹訪問順序是根左右，先訪問根節(jié)點(diǎn)，所以a0就一定是整個(gè)二叉樹的根，而且a0也一定會(huì)在中序序列中出現(xiàn)，假設(shè)它在中序序列中出現(xiàn)的位置bk就是a0。

所以，在中序序列中，k號(hào)結(jié)點(diǎn)之前的b0到b(k-1)就是根的左子樹的中序序列，而k號(hào)結(jié)點(diǎn)之后的b(k+1)到bn就是根的右子樹的中序序列。

與之對(duì)應(yīng)的，在先序序列中，緊跟在a0之后的k個(gè)結(jié)點(diǎn)a1到ak就一定是左子樹的先序序列，其余的a(k+1)到a（n-1）就一定是右子樹的先序序列。

結(jié)合假設(shè)2，結(jié)點(diǎn)數(shù)少于n的二叉樹可以由中序序列和先序序列唯一確定，所以我們談及的左子樹和右子樹可以分別根據(jù)它們的先序序列和中序序列唯一確定。

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

開學(xué)之際，分不清興奮還是緊張；

各在一方，皆是為夢(mèng)奔忙；

負(fù)重前行，我已學(xué)會(huì)眼里帶光。

感謝閱讀，學(xué)習(xí)使人強(qiáng)大。

如果你想更好的提升你的編程能力，成為一個(gè)強(qiáng)大的C/C++程序員！不妨和一些志同道合的小伙伴一起學(xué)習(xí)成長！