樹(shù)的遞歸定義：
樹(shù)是n（n>=0）個(gè)結(jié)點(diǎn)的有限集T，T為空時(shí)稱為空樹(shù)，否則它滿足如下兩個(gè)條件：
（1）有且僅有一個(gè)特定的稱為根（Root）的結(jié)點(diǎn)
（2）其余的結(jié)點(diǎn)可分為m（m>=0）個(gè)互不相交的子集T1，T2，…，Tm，其中每個(gè)子集本身又是一棵樹(shù)，并稱其為根的子樹(shù)。
注意：樹(shù)的遞歸定義刻畫了樹(shù)的固有特性：一顆非空樹(shù)是由若干棵子樹(shù)構(gòu)成的，而子樹(shù)又可由若干棵更小的子樹(shù)構(gòu)成。

結(jié)點(diǎn)的層次從根開(kāi)始定義起，根為第一層，根的孩子為第二層。
若某結(jié)點(diǎn)在第 L 層，則其子樹(shù)的根就在第 L 1層。
樹(shù)中結(jié)點(diǎn)的最大層次稱為樹(shù)的深度或高度。
樹(shù)的度是所有結(jié)點(diǎn)度里的最大值。

---------------------------------------------------------------------------------------------------------------------------------------

樹(shù)具有如下最基本的性質(zhì):
有序樹(shù)和無(wú)序樹(shù)：若將樹(shù)中每個(gè)結(jié)點(diǎn)的各子樹(shù)看成是從左到右有次序的（即不能互換），則稱該樹(shù)為有序樹(shù)；否則稱為無(wú)序樹(shù)。
注意：若不特別指明，一般討論的樹(shù)都是有序樹(shù)。
森林：森林是 m（m>=0）棵互不相交的樹(shù)的集合。
樹(shù)和森林的概念相近。刪去一棵樹(shù)的根，就得到一個(gè)森林；反之，加上一個(gè)結(jié)點(diǎn)作樹(shù)根，森林就變?yōu)橐豢脴?shù)。

---------------------------------------------------------------------------------------------------------------------------------------

二叉樹(shù)的定義：二叉樹(shù)是樹(shù)形結(jié)構(gòu)的一個(gè)重要類型。許多實(shí)際問(wèn)題抽象出來(lái)的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹(shù)的形式，即使是一般的樹(shù)也能簡(jiǎn)單地轉(zhuǎn)換為二叉樹(shù)，而且二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及其算法都較為簡(jiǎn)單，因此，我們把二叉樹(shù)作為重點(diǎn)。
二叉樹(shù)是n（n>=0）個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集（空二叉樹(shù)），或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的，分別稱為根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成（子樹(shù)也為二叉樹(shù)）。

二叉樹(shù)的特點(diǎn)及與樹(shù)的異同：

二叉樹(shù)的五種基本形態(tài)：
二叉樹(shù)可以是空集；根可以有空的左子樹(shù)和右子樹(shù)；或者左，右子樹(shù)皆為空。

二叉樹(shù)的性質(zhì)：

---------------------------------------------------------------------------------------------------------------------------------------

特殊二叉樹(shù)：
左斜樹(shù)：所有的結(jié)點(diǎn)只有左子樹(shù)。
右斜樹(shù)：所有的結(jié)點(diǎn)只有右子樹(shù)。
特點(diǎn)：每層只有一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)的個(gè)數(shù)與二叉樹(shù)的深度相同。

滿二叉樹(shù)：一棵深度為k且有2^k - 1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)。
特點(diǎn)：
（1）每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值。即對(duì)給定的高度，它是具有最多結(jié)點(diǎn)數(shù)的二叉樹(shù)。
（2）滿二叉樹(shù)中不存在度數(shù)為1的結(jié)點(diǎn)，每個(gè)分支結(jié)點(diǎn)均有兩棵高度相同的子樹(shù)，且樹(shù)葉都在最下一層上。

完全二叉樹(shù)：深度為k的有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從1到n的結(jié)點(diǎn)一 一對(duì)應(yīng)時(shí)，稱為完全二叉樹(shù)。
完全二叉樹(shù)至多只有最下面的兩層上結(jié)點(diǎn)的度數(shù)可以小于2，并且最下一層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上。
特點(diǎn)：
（1）滿二叉樹(shù)是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿二叉樹(shù)。
（2）在滿二叉樹(shù)的最下一層上，從最右邊開(kāi)始連續(xù)刪去若干結(jié)點(diǎn)后得到的二叉樹(shù)仍然是一棵完全二叉樹(shù)。
（3）在完全二叉樹(shù)中，若某個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它一定沒(méi)有右孩子，即該結(jié)點(diǎn)必是葉結(jié)點(diǎn)。

完全二叉樹(shù)的性質(zhì)：


---------------------------------------------------------------------------------------------------------------------------------------

二叉樹(shù)的順序存儲(chǔ)：該方法是把二叉樹(shù)的所有結(jié)點(diǎn)按照一定的線性次序存儲(chǔ)到一片連續(xù)的存儲(chǔ)單元中。結(jié)點(diǎn)在這個(gè)序列中的相互位置還能反映出結(jié)點(diǎn)之間的邏輯關(guān)系。

---------------------------------------------------------------------------------------------------------------------------------------

二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)：

二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)形象對(duì)比圖

帶雙親指針的二叉鏈表：經(jīng)常要在二叉樹(shù)中尋找某節(jié)點(diǎn)的雙親時(shí)，可在每個(gè)結(jié)點(diǎn)上再加一個(gè)指向其雙親的指針parent，形成一個(gè)帶雙親指針的二叉鏈表。

---------------------------------------------------------------------------------------------------------------------------------------

我們來(lái)幾道例題：
方法二：n0 = n2 1
設(shè)第 i 層為最后一層，i - 1 層為滿結(jié)點(diǎn).
最后一層結(jié)點(diǎn)數(shù)量為1，2，4，8，16，32，64，128，256，512
768 - 511 = 257 （第 i 層結(jié)點(diǎn)數(shù)）
257 / 2 = 129（向上取整） （第 i - 1 層度數(shù)為2或1的結(jié)點(diǎn)數(shù)）
256 - 129 = 127 （第 i - 1 層度數(shù)為0的結(jié)點(diǎn)數(shù)）
127 257 = 384
配合圖像理解

---------------------------------------------------------------------------------------------------------------------------------------

二叉樹(shù)遍歷
遍歷是指沿著某條搜索路線，依次對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)均做一次且僅一次訪問(wèn)。
訪問(wèn)結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問(wèn)題。
1.遍歷方案
（1）訪問(wèn)結(jié)點(diǎn)本身（N）
（2）遍歷該結(jié)點(diǎn)的左子樹(shù)（L）
（3）遍歷該結(jié)點(diǎn)的右子樹(shù)（R）
注意：這種遍歷方法的時(shí)間復(fù)雜度是：O(N)

---------------------------------------------------------------------------------------------------------------------------------------

先序遞歸遍歷算法
如果二叉樹(shù)為空，什么也不做。否則：
（1）訪問(wèn)根結(jié)點(diǎn)
（2）先序遍歷左子樹(shù)
（3）先序遍歷右子樹(shù)

先序非遞歸遍歷算法
（1）首先申請(qǐng)一個(gè)新的棧，記為stack。
（2）將頭結(jié)點(diǎn)head壓入stack中。
（3）每次從stack中彈出棧頂結(jié)點(diǎn)，記為cur，然后打印cur的值，如果cur右孩子不為空，則將右孩子壓入棧中；如果cur的左孩子不為空，將其壓入stack中。
（4）重復(fù)步驟3，直到stack為空。
---------------------------------------------------------------------------------------------------------------------------------------

中序遞歸遍歷算法
如果二叉樹(shù)為空，什么也不做。否則：
（1）中序遍歷左子樹(shù)
（2）訪問(wèn)根結(jié)點(diǎn)
（3）中序遍歷右子樹(shù)
---------------------------------------------------------------------------------------------------------------------------------------

后序遞歸遍歷算法
如果二叉樹(shù)為空，什么也不做。否則：
（1）后序遍歷左子樹(shù)
（2）后序遍歷右子樹(shù)
（3）訪問(wèn)根結(jié)點(diǎn)
---------------------------------------------------------------------------------------------------------------------------------------

層次遍歷二叉樹(shù)
要進(jìn)行層次遍歷需要借助一個(gè)隊(duì)列。先將二叉樹(shù)根結(jié)點(diǎn)入隊(duì)，然后出隊(duì)，訪問(wèn)該結(jié)點(diǎn)，如果它有左子樹(shù)，則將左子樹(shù)根結(jié)點(diǎn)入隊(duì)；如果它有右子樹(shù)，則將右子樹(shù)根結(jié)點(diǎn)入隊(duì)。然后出隊(duì)，對(duì)出隊(duì)結(jié)點(diǎn)訪問(wèn)，如此反復(fù)，直到隊(duì)列為空。
---------------------------------------------------------------------------------------------------------------------------------------

遍歷構(gòu)造二叉樹(shù)
注意：前序遍歷序列和中序遍歷序列或者中序遍歷序列和后序遍歷序列可以唯一地構(gòu)造一棵二叉樹(shù)

例1：
前序遍歷序列:ABCDEF
中序遍歷序列：CBDAEF
后序遍歷序列：CDBFEA
前序遍歷先訪問(wèn)根結(jié)點(diǎn)，因此前序遍歷序列的第一個(gè)字母肯定就是根結(jié)點(diǎn)，即A是根結(jié)點(diǎn)；然后，由于中序遍歷先訪問(wèn)左子樹(shù)，再訪問(wèn)根結(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)，所以我們找到中序遍歷中A的位置，然后A左邊的字母就是左子樹(shù)了，也就是CBD是根結(jié)點(diǎn)的左子樹(shù)；同樣的，得到EF為根結(jié)點(diǎn)的右子樹(shù)。將前序遍歷序列分成BCD和EF，分別對(duì)左子樹(shù)和右子樹(shù)應(yīng)用同樣的方法，遞歸下去。

例2：
先序序列：ABCDEFGHI
中序序列：BCAEDGHFI
由先序序列可知A為二叉樹(shù)的根結(jié)點(diǎn)。中序序列中A之前的BC為左子樹(shù)的中序序列，EDGHFI為右子樹(shù)的中序序列。然后由先序序列可知B是左子樹(shù)的根結(jié)點(diǎn)，D是右子樹(shù)的根結(jié)點(diǎn)。依此類推，就能將剩下的結(jié)點(diǎn)繼續(xù)分解下去，最后得到二叉樹(shù)。

例3：
中序序列：HDMIBJNEAFKCG
后序序列：HMIDNJEBKFGCA
由后序遍歷可知A是根結(jié)點(diǎn)，由中序遍歷可知HDMIBJE是A的左子樹(shù)部分，F(xiàn)KCG是右子樹(shù)部分。由后序遍歷可知B是A的左子樹(shù)，A的右子樹(shù)部分KFGC，C是根。由中序遍歷可知，F(xiàn)K是C的左子樹(shù)部分，G是右子樹(shù)部分。由后序遍歷可知，F(xiàn)是C的左子樹(shù)，K是F的右子樹(shù)。
---------------------------------------------------------------------------------------------------------------------------------------

二叉樹(shù)線索化
遍歷二叉樹(shù)就是以一定的規(guī)則將二叉樹(shù)中的結(jié)點(diǎn)排列成一個(gè)線性序列，從而得到二叉樹(shù)結(jié)點(diǎn)的各種遍歷序列。
其實(shí)質(zhì)就是對(duì)一個(gè)非線性結(jié)構(gòu)進(jìn)行線性化操作，使在這個(gè)訪問(wèn)序列中每一個(gè)結(jié)點(diǎn)（除第一個(gè)和最后一個(gè)）都有一個(gè)直接前驅(qū)和直接后繼。
傳統(tǒng)的二叉鏈表只能反映父子關(guān)系，不能直接得到遍歷中的前驅(qū)和后繼。

---------------------------------------------------------------------------------------------------------------------------------------

線索二叉樹(shù)的概念
n個(gè)結(jié)點(diǎn)的二叉鏈表中含有n 1個(gè)空指針域。
N個(gè)結(jié)點(diǎn)有2n個(gè)指針，有N-1個(gè)非空指針。
利用二叉鏈表中的空指針域，存放指向結(jié)點(diǎn)在某種遍歷次序下的前驅(qū)和后繼結(jié)點(diǎn)的指針（這種附加的指針?lè)Q為“線索”）。
這種加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹(shù)稱為線索二叉樹(shù)。
根據(jù)線索性質(zhì)的不同，線索二叉樹(shù)可分為前序線索二叉樹(shù)，中序線索二叉樹(shù)和后序線索二叉樹(shù)三種。
---------------------------------------------------------------------------------------------------------------------------------------

線索二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)
---------------------------------------------------------------------------------------------------------------------------------------

線索化建立過(guò)程（中序）
記ptr指向二叉鏈表中的一個(gè)結(jié)點(diǎn)，以下是建立線索的規(guī)則：
（1）如果ptr->lchild為空，則存放指向中序遍歷序列中該結(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)。這個(gè)結(jié)點(diǎn)稱為ptr的中序前驅(qū)。
（2）如果ptr->rchild為空，則存放指向中序遍歷序列中該結(jié)點(diǎn)的后繼節(jié)點(diǎn)。這個(gè)結(jié)點(diǎn)稱為ptr的中序后繼。
顯然，在決定lchild是指向左孩子還是前驅(qū)，rchild是指向右孩子還是后繼，需要一個(gè)區(qū)分標(biāo)志，注意ltag和rtag只是區(qū)分0和1數(shù)字的布爾型變量，其占用內(nèi)存空間要小于像lchild和rchild的指針變量。
在中序線索二叉樹(shù)上查找任意結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)
對(duì)于中序線索二叉樹(shù)上的任一結(jié)點(diǎn)，尋找其中序的前驅(qū)結(jié)點(diǎn)，有以下兩種情況：
（1）如果該結(jié)點(diǎn)的左標(biāo)志為1，那么其左指針域所指向的結(jié)點(diǎn)便是它的前驅(qū)結(jié)點(diǎn)。
（2）如果該結(jié)點(diǎn)的左標(biāo)志為0，表明該結(jié)點(diǎn)有左孩子，根據(jù)中序遍歷的定義，它的前驅(qū)結(jié)點(diǎn)是以該結(jié)點(diǎn)的左孩子為根結(jié)點(diǎn)的子樹(shù)的最右結(jié)點(diǎn)，即沿著其左子樹(shù)的右指針鏈向下查找，當(dāng)某結(jié)點(diǎn)的右標(biāo)志為1時(shí)，它就是所要找的前驅(qū)結(jié)點(diǎn)。

在中序線索二叉樹(shù)上查找任意結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)
對(duì)于中序線索二叉樹(shù)上的任一結(jié)點(diǎn)，尋找其中序的后繼結(jié)點(diǎn)，有以下兩種情況：
（1）如果該結(jié)點(diǎn)的右標(biāo)志為1，那么其右指針域所指向的結(jié)點(diǎn)便是它的后繼結(jié)點(diǎn)。
（2）如果該結(jié)點(diǎn)的右標(biāo)志為0，表明該結(jié)點(diǎn)有右孩子，根據(jù)中序遍歷的定義，它的后繼結(jié)點(diǎn)是以該結(jié)點(diǎn)的右孩子為根結(jié)點(diǎn)的子樹(shù)的最左結(jié)點(diǎn)，即沿著其右子樹(shù)的左指針鏈向下查找，當(dāng)某結(jié)點(diǎn)的左標(biāo)志為1時(shí)，它就是所要找的后繼結(jié)點(diǎn)。

例1：
后序序列：dbca
d沒(méi)有左子樹(shù)和右子樹(shù)，所以d的左指針域指向它的前驅(qū)結(jié)點(diǎn)，但是d沒(méi)有前驅(qū)結(jié)點(diǎn)，所以指向NULL。
d的右指針域指向它的后繼結(jié)點(diǎn)，即指向b結(jié)點(diǎn)。
此時(shí)pre在d處。
b沒(méi)有左子樹(shù)，所以b的左指針域指向它的前驅(qū)結(jié)點(diǎn)，即指向d。
此時(shí)pre在b處。
c沒(méi)有左子樹(shù)和右子樹(shù)，所以c的左指針域指向它的前驅(qū)結(jié)點(diǎn)，即指向b結(jié)點(diǎn)。
c的右指針域指向它的后繼結(jié)點(diǎn)，即指向a結(jié)點(diǎn)。
此時(shí)pre在c處。
a有左子樹(shù)和右子樹(shù)。
選D。