樹是n（n>=0）個(gè)結(jié)點(diǎn)的有限集。n=0時(shí)稱為空樹。在任意一顆非空樹中：

（1）有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；
（2）當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m（m>0）個(gè)互不相交的有限集T1、T2、......、Tm，其中每一個(gè)集合本身又是一棵樹，并且稱為根的子樹。

一、樹的定義

樹是n（n>=0）個(gè)結(jié)點(diǎn)的有限集。n=0時(shí)稱為空樹。在任意一顆非空樹中：
（1）有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；
（2）當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m（m>0）個(gè)互不相交的有限集T1、T2、......、Tm，其中每一個(gè)集合本身又是一棵樹，并且稱為根的子樹。
如圖所示：

關(guān)于樹：

（1）n>0時(shí)根結(jié)點(diǎn)是唯一的，不可能存在多個(gè)根結(jié)點(diǎn)。
（2）m>0時(shí)，子樹的個(gè)數(shù)沒有限制，但是它們一定是互不相交的，下圖所示的就不符合數(shù)的定義，因?yàn)樗鼈兌加邢嘟坏淖訕洹?/p>

二、樹的存儲(chǔ)結(jié)構(gòu)

1.雙親表示法

在每個(gè)結(jié)點(diǎn)中，附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)在數(shù)組中的位置。也就是說，每個(gè)結(jié)點(diǎn)除了知道自己是誰(shuí)以外，還知道它的雙親結(jié)點(diǎn)在數(shù)組中的位置。

其中data是數(shù)據(jù)域，存儲(chǔ)結(jié)點(diǎn)的數(shù)據(jù)信息。而parent是指針域，存儲(chǔ)該結(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo)。

這樣的存儲(chǔ)結(jié)構(gòu)，我們可以根據(jù)結(jié)點(diǎn)的parent指針很容易找到它的雙親結(jié)點(diǎn)，所以用的時(shí)間復(fù)雜度為O(1)，知道parent為-1時(shí)，表示找到了樹結(jié)點(diǎn)的根?？墒侨绻澜Y(jié)點(diǎn)的孩子是什么，得遍歷整個(gè)結(jié)構(gòu)才行。

改進(jìn)：

增加一個(gè)結(jié)點(diǎn)最左邊孩子的域，叫它長(zhǎng)子域，這樣就可以很容易得到結(jié)點(diǎn)的孩子。如果沒有孩子的結(jié)點(diǎn)，這個(gè)長(zhǎng)子域就設(shè)置為-1，如圖所示：

對(duì)于有0個(gè)或1個(gè)孩子結(jié)點(diǎn)來說，這樣就解決了找結(jié)點(diǎn)孩子的問題了。甚至是兩個(gè)孩子，知道了長(zhǎng)子是誰(shuí)，另一個(gè)當(dāng)然就是次子了。

再改進(jìn)：

可以增加一個(gè)右兄弟域來體現(xiàn)兄弟關(guān)系，也就是說，每個(gè)結(jié)點(diǎn)如果它存在右兄弟，則記錄下右兄弟的下標(biāo)。同樣的，如果右兄弟不存在，則賦值為-1，如下圖所示：

總結(jié)：

存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)是一個(gè)非常靈活的過程。一個(gè)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)得是否合理，取決于基于該存儲(chǔ)結(jié)構(gòu)的運(yùn)算是否合適、是否方便，時(shí)間復(fù)雜度好不好等。注意也不是越多越好，有需要時(shí)再設(shè)計(jì)相應(yīng)的結(jié)構(gòu)。

2.孩子表示法

把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來，以單鏈表作存儲(chǔ)結(jié)構(gòu)，則n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表，如果是葉子結(jié)點(diǎn)則此單鏈表為空。然后n個(gè)頭指針又組成一個(gè)線性表，采用順序存儲(chǔ)結(jié)構(gòu)，存放進(jìn)一個(gè)一維數(shù)組中，如下圖所示：

3.孩子兄弟表示法

任意一棵樹，它的結(jié)點(diǎn)的第一個(gè)孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我們?cè)O(shè)置兩個(gè)指針，分別指向該結(jié)點(diǎn)的第一個(gè)孩子和此結(jié)點(diǎn)的右兄弟。

三、二叉樹的定義

二叉樹是n（n>=0）個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個(gè)根結(jié)點(diǎn)和兩顆互不相交的、分別稱為根結(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。

二叉樹特點(diǎn)：

（1）每個(gè)結(jié)點(diǎn)最多有兩棵子樹，所以二叉樹中不存在度大于2的結(jié)點(diǎn)。注意不是只有兩棵子樹，而是最多有。沒有子樹或者有一棵子樹都是可以的。
（2）左子樹和右子樹是有順序的，次序不能任意顛倒。
（3）即使樹中某結(jié)點(diǎn)只有一棵子樹，也要區(qū)別它是左子樹還是右子樹。

二叉樹具有五種基本形態(tài)：

（1）空二叉樹。
（2）只有一個(gè)根結(jié)點(diǎn)。
（3）根結(jié)點(diǎn)只有右子樹。
（4）根結(jié)點(diǎn)既有左子樹又有右子樹。

特殊二叉樹：

1.斜樹

所有的結(jié)點(diǎn)都只有左子樹的二叉樹叫左斜樹。所有結(jié)點(diǎn)都是只有右子樹的二叉樹叫右斜樹。這兩者統(tǒng)稱為斜樹。斜樹有很明顯的特點(diǎn)，就是每一層都只有一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)的個(gè)數(shù)與二叉樹的深度相同。

2.滿二叉樹

在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹。
滿二叉樹的特點(diǎn)：
（1）葉子只能出現(xiàn)在最下一層。出現(xiàn)在其它層就不可能達(dá)成平衡。
（2）非葉子結(jié)點(diǎn)的度一定是2。
（3）在同樣深度的二叉樹中，滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多，葉子數(shù)最多。

3.完全二叉樹

對(duì)一個(gè)具有n個(gè)結(jié)點(diǎn)的二叉樹按層序編號(hào)，如果編號(hào)為i（1<=i<=n）的結(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào)為i的結(jié)點(diǎn)在二叉樹中位置完全相同，則這棵二叉樹稱為完全二叉樹。
完全二叉樹的特點(diǎn)：
（1）葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層。
（2）最下層的葉子一定集中在左部連續(xù)位置。
（3）倒數(shù)兩層，若有葉子結(jié)點(diǎn)，一定都在右部連續(xù)位置。
（4）如果結(jié)點(diǎn)度為1，則該結(jié)點(diǎn)只有左孩子，即不存在只有右子樹的情況。
（5）同樣結(jié)點(diǎn)數(shù)的二叉樹，完全二叉樹的深度最小。

滿二叉樹一定是一棵完全二叉樹，但完全二叉樹不一定是滿的。

四、二叉樹的存儲(chǔ)結(jié)構(gòu)

二叉樹的順序存儲(chǔ)結(jié)構(gòu)

二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是用一維數(shù)組存儲(chǔ)二叉樹中的結(jié)點(diǎn)，并且結(jié)點(diǎn)的存儲(chǔ)位置，也就是數(shù)組的下標(biāo)要能體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系，不如雙親與孩子的關(guān)系，左右兄弟的關(guān)系等。
滿二叉樹的順序存儲(chǔ)：

將這棵二叉樹存入到數(shù)組中，相應(yīng)的下標(biāo)對(duì)應(yīng)其同樣的位置，如圖所示：

二叉鏈表

二叉樹每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，所以為它設(shè)計(jì)一個(gè)數(shù)據(jù)域和兩個(gè)指針域。稱這樣的鏈表叫做二叉鏈表。

其中，data是數(shù)據(jù)域，lchild和rchild都是指針域，分別存放指向左孩子和右孩子的指針。如果有需要，還可以再增加一個(gè)指向其雙親的指針域，那樣就稱之為三叉鏈表。

五、遍歷二叉樹

二叉樹的遍歷是指從根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪問二叉樹中所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。

1.前序遍歷

規(guī)則是若二叉樹為空，則空操作返回，否則先訪問根結(jié)點(diǎn)，然后前序遍歷左子樹，再前序遍歷右子樹。遍歷的順序?yàn)椋篈BDGHCEIF。

2.中序遍歷

規(guī)則是若樹為空，則空操作返回，否則從根結(jié)點(diǎn)開始（注意并不是先訪問根結(jié)點(diǎn)），中序遍歷根結(jié)點(diǎn)的左子樹，然后是訪問根結(jié)點(diǎn)，最后中序遍歷右子樹。遍歷的順序?yàn)椋篏DHBAEICF。

3.后序遍歷

規(guī)則是若樹為空，則空操作返回，否則從左到右先葉子后結(jié)點(diǎn)的方式遍歷訪問左右子樹，最后是訪問根結(jié)點(diǎn)。遍歷的順序?yàn)椋篏HDBIEFCA。

4.層序遍歷

規(guī)則是若樹為空，則空操作返回，否則從樹的第一層，也就是根結(jié)點(diǎn)開始訪問，從上而下逐層遍歷，在同一層中，按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。遍歷的順序?yàn)椋篈BCDEFGHIJ。

學(xué)習(xí)是一個(gè)慢慢積累的過程，也是一件很快樂的事，這種快樂來自于你的思考。完成一項(xiàng)學(xué)習(xí)任務(wù)固然重要，但更重要的是在完成的過程中學(xué)到了什么，掌握了什么，遇到一些什么問題，為什么會(huì)出現(xiàn)這種問題，根源是什么，都有哪些解決方案，什么樣的情況適合這個(gè)方案。只有在不斷的思考，你的能力才會(huì)有所提升！