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