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

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

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

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

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

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

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

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

二叉樹的性質(zhì)：

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

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

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

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

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


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

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

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

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

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

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

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

我們來幾道例題：
方法二：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
配合圖像理解

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

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

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

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

先序非遞歸遍歷算法
（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為空。
---------------------------------------------------------------------------------------------------------------------------------------

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

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

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

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

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

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

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

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

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

線索二叉樹的概念
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)的指針（這種附加的指針稱為“線索”）。
這種加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹。
根據(jù)線索性質(zhì)的不同，線索二叉樹可分為前序線索二叉樹，中序線索二叉樹和后序線索二叉樹三種。
---------------------------------------------------------------------------------------------------------------------------------------

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

線索化建立過程（中序）
記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的指針變量。
在中序線索二叉樹上查找任意結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)
對(duì)于中序線索二叉樹上的任一結(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)的子樹的最右結(jié)點(diǎn)，即沿著其左子樹的右指針鏈向下查找，當(dāng)某結(jié)點(diǎn)的右標(biāo)志為1時(shí)，它就是所要找的前驅(qū)結(jié)點(diǎn)。

在中序線索二叉樹上查找任意結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)
對(duì)于中序線索二叉樹上的任一結(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)的子樹的最左結(jié)點(diǎn)，即沿著其右子樹的左指針鏈向下查找，當(dāng)某結(jié)點(diǎn)的左標(biāo)志為1時(shí)，它就是所要找的后繼結(jié)點(diǎn)。

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