前言：
現(xiàn)在安卓面試，對于數(shù)據(jù)結(jié)構(gòu)的問題也越來越多了，也經(jīng)常看到別人發(fā)的面試題都是問什么紅黑樹，二叉樹查找等，所以我們雖然不會馬上就會各種難的面試題，但起碼樹的基礎(chǔ)知識還是要會的，這樣才能去進一步學(xué)。
貼上最近看到的一個介紹圖片：
Android技能書系列：
Android基礎(chǔ)知識
Android技能樹 — Android存儲路徑及IO操作小結(jié)
Android技能樹 — 多進程相關(guān)小結(jié)
數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識
Android技能樹 — 數(shù)組,鏈表,散列表基礎(chǔ)小結(jié)
Android技能樹 — 樹基礎(chǔ)知識小結(jié)(一)
算法基礎(chǔ)知識
Android技能樹 — 排序算法基礎(chǔ)小結(jié)
本文主要講關(guān)于樹的基礎(chǔ)知識。
樹(Tree)是n(n>=0)個結(jié)點的有限集。n=0時稱為空樹。在任意一棵非空樹中:(1)有且僅有一個特定的稱為根(Root)的結(jié)點；(2)當(dāng)n>1時，其余結(jié)點可分為m(m>O)個互不相交的有限集T1、T2、……、 Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹(SubTree)
基礎(chǔ)知識
結(jié)點
根據(jù)上面的基礎(chǔ)知識我畫了一個歸總的圖（這樣我就不需要寫文字介紹了，啊哈哈）：
樹結(jié)構(gòu)特點
還是用自己畫的圖來說明：
存儲結(jié)構(gòu)
在Android技能樹 — 數(shù)組,鏈表,散列表基礎(chǔ)小結(jié)中，我們介紹了線性存儲，鏈?zhǔn)酱鎯Γ覀兊臉淇梢猿浞钟枚邅斫Y(jié)合表示。
我們統(tǒng)一來用上面各種方式來表示下面這個樹的存儲結(jié)構(gòu)：
雙親表示法：
在每個結(jié)點中，附設(shè)一個指示器指示其雙親結(jié)點在數(shù)組中的位置。
因為有十一個結(jié)點,所以我們的index為0-10，然后index位置中存儲（data + parent的index值），結(jié)果如下圖所示：
這里我們發(fā)現(xiàn)根據(jù)index里面的parent指針，很容易知道父結(jié)點，但是比如我問知道了E結(jié)點，想知道它的子結(jié)點是哪幾個，就不知道了，只能通過整個結(jié)構(gòu)的遍歷。
當(dāng)然我們可以變相的 多加一個指針：
如果我們又比較關(guān)注兄弟結(jié)點之間的關(guān)系，可以增加一個右兄弟域來體現(xiàn)兄弟關(guān)系：
孩子鏈表表示法：
把每個結(jié)點的孩子結(jié)點排列起來,以單鏈表作存儲結(jié)構(gòu)，則n 個結(jié)點有n個孩子鏈表，如果是葉子結(jié)點，則此單鏈表為空。然后n個頭指針又組成一個線性表，采用順序存儲結(jié)構(gòu)，存放進一個一維數(shù)組中。
用孩子表示法表示我們上面的樹，結(jié)構(gòu)如下：
所以我們的結(jié)點結(jié)構(gòu)有二種：
1.表頭數(shù)組的表頭結(jié)點：
-
孩子鏈表的孩子結(jié)點：
但是這樣子對于查找某個結(jié)點的孩子，或者找某個結(jié)點的兄弟都方便，但似乎如果要找某個結(jié)點的雙親結(jié)點就麻煩了。所以我們可以結(jié)合上面講過的《雙親表示法》
雙親孩子表示法：
把上面二個方法結(jié)合就可以了。
孩子兄弟表示法：
任意一棵樹，它的結(jié)點的第一個孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。
所以設(shè)置二個指針，分別指向該結(jié)點的第一個孩子和此結(jié)點的右兄弟
所以和上面類似，只是我們存了不同的二個指針（從方法名字就知道，<孩子><兄弟>法，一個孩子，一個兄弟，二個指針）。
我們把上面的樹按照這種方式實現(xiàn)：
森林：
繼續(xù)畫個圖來說明，省得打字了，嘿嘿：
分類
樹也是會根據(jù)不同條件，做了分類，我們來了解一下。
那有序樹和無序數(shù)的區(qū)別在于哪里呢？
如果將樹中結(jié)點的各子樹看成從左至右是有次序的，不能互換，則成為有序樹，否則就是無序樹
比如我們只是單純的表示一個家族的關(guān)系：
比如只是說明A的孩子有B跟C，這時候B和C換了位置葉 沒關(guān)系，這時候就是無序樹。
但是如果我們這個家族譜是按照年齡來排序（長子，次子），那這時候B和C就不能換位置了，這時候就是有序樹。
但是我們平常說的樹通常都是指的有序樹，而有序樹有很多分類，比較多的就是二叉樹。
二叉樹：
基本形態(tài)：
二叉樹性質(zhì)：
其實這個類似與我們以前數(shù)學(xué)課上要背的數(shù)學(xué)公式，大家可以自己畫個二叉樹，然后試著上面的公式比對下，是不是正確。
遍歷二叉樹：
二叉樹的遍歷是指從根結(jié)點出發(fā)，按照某種次序依次訪問二叉樹中所有結(jié)點，使得每個結(jié)點被訪問依次且僅被訪問一次。
前序遍歷：
單單看這個圖，其實換成我，我也看不懂規(guī)律，但是我們只需要懂得其中的規(guī)則就行。
偽代碼：
遍歷（結(jié)點對象 t）{
if( t == null){
return;
}
//第一步，實現(xiàn)某個業(yè)務(wù)操作，比如我們是打印結(jié)點字符串。
print(t)
//第二步，遞歸方式繼續(xù)調(diào)用該方法遍歷左孩子
遍歷(t.左孩子)
//第三步，遞歸方式繼續(xù)調(diào)用該方法遍歷右孩子
遍歷(t.右孩子)
}
我們看到因為print在其他方法的前面，所以叫前序遍歷。我們現(xiàn)在傳入根結(jié)點到這個方法，然后依次打印并且遞歸，就會發(fā)現(xiàn)，就是圖上的順序。
中序遍歷：
偽代碼：
遍歷（結(jié)點對象 t）{
if( t == null){
return;
}
//第一步，遞歸方式繼續(xù)調(diào)用該方法遍歷左孩子
遍歷(t.左孩子)
//第二步，實現(xiàn)某個業(yè)務(wù)操作，比如我們是打印結(jié)點字符串。
print(t)
//第三步，遞歸方式繼續(xù)調(diào)用該方法遍歷右孩子
遍歷(t.右孩子)
}
我們發(fā)現(xiàn)只要把我們的打印語句放在中間，就是中序遍歷了。
后序遍歷：
偽代碼：
遍歷（結(jié)點對象 t）{
if( t == null){
return;
}
//第一步，遞歸方式繼續(xù)調(diào)用該方法遍歷左孩子
遍歷(t.左孩子)
//第二步，遞歸方式繼續(xù)調(diào)用該方法遍歷右孩子
遍歷(t.右孩子)
//第三步，實現(xiàn)某個業(yè)務(wù)操作，比如我們是打印結(jié)點字符串。
print(t)
}
我們發(fā)現(xiàn)只要把我們的打印語句放在最后，就是后序遍歷了。
分類：
斜樹:
完全二叉樹與滿二叉樹：
一棵深度為k，且有 2^(k+1) - 1 個節(jié)點的二叉樹稱為滿二叉樹，這種樹的特點是每一層上的節(jié)點數(shù)都是最大節(jié)點數(shù)。
而在一棵二叉樹中，除最后一層外，若其余層都是滿的，并且最后一層或者是滿的，或者是在右邊缺少連續(xù)若干節(jié)點，則此二叉樹為完全二叉樹。
平衡二叉樹：
這塊知識很多，后期補上。
排序二叉樹：
這塊知識很多，后期補上。
線索二叉樹：
n個結(jié)點的二叉鏈表中含有n+1(2n-(n-1)=n+1)個空指針域。利用二叉鏈表中的空指針域，存放指向結(jié)點在某種遍歷次序下的前驅(qū)和后繼結(jié)點的指針（這種附加的指針稱為"線索"）。
這里一定要說明一個知識點：什么是前驅(qū)和后繼。
網(wǎng)上很多人都是對這個解釋太過于簡單以至于很多人理解錯誤，比如：
假設(shè)我們現(xiàn)在有這個一個二叉樹：
我現(xiàn)在問I的前驅(qū)是誰，后繼是誰，很多人就單純的從樹的形狀上來看，也就是看 I 的上一個結(jié)點是D，所以前驅(qū)是 D， I 沒有后面的子結(jié)點，所以后驅(qū)為空。這種回答是錯誤的。我們在
Android技能樹 — 數(shù)組,鏈表,散列表基礎(chǔ)小結(jié)文中提到過前驅(qū)和后繼：
比如雙向鏈表就是有前驅(qū)和后繼。那我們單純看這棵樹是看不出來的，我們要先把樹按照某個遍歷方式的時候，把它用這種鏈表形式擺列，然后才能知道某個結(jié)點的前驅(qū)和后繼是什么，比如上面的圖我們用中序遍歷，我們得到的是：HDIBJEAFCG，這時候 I 的前繼是D，后繼是B。
我們在二叉樹存儲結(jié)構(gòu)中，有二個指針指向它的二個子結(jié)點。
但是可能只有一個子結(jié)點，或者沒有子結(jié)點，這樣這個空的指針存儲就浪費了，我們可以在這個指針里面存這個結(jié)點的前驅(qū)或者后繼結(jié)點的指針。
但是這時候又有一個問題，就是我們不知道這個點目前到底放的是前驅(qū)的還是左子結(jié)點的指針，所以我們還需要一個參數(shù)來說明當(dāng)前這個位置放的是哪個的指針。
- 當(dāng)ltag為0的時候，說明lchild是該結(jié)點的左孩子的指針，為1的時候說明lchild是該結(jié)點的前驅(qū)。
- 當(dāng)rtag為0的時候，說明rchild是該結(jié)點的右孩子的指針，為1的時候說明rchild是該結(jié)點的后繼。
存儲結(jié)構(gòu)：
二叉樹順序存儲結(jié)構(gòu)：
我們把二叉樹補充為一個滿二叉樹，然后相應(yīng)的填入一個一維數(shù)組即可。
二叉鏈表：
二叉樹每個結(jié)點最多又二個孩子，所以為它設(shè)計一個數(shù)據(jù)域和二個指針域。
三叉鏈表：
改進于二叉鏈表，增加父節(jié)點的指引，能更好地實現(xiàn)節(jié)點間的訪問
結(jié)語：
本文并沒有寫完，內(nèi)容太多，后面再陸續(xù)補上去。哪里寫錯了，歡迎指出。。。謝謝。
參考：
《大話數(shù)據(jù)結(jié)構(gòu)》
《維基百科》
