前言
在上篇文章中，向大家介紹了線性資料結構中的棧、隊列和串三種資料結構，相對來說比較簡單，棧的特點是先進後出(FILO)，隊列的特點是先進先出(FIFO)。棧包含入棧和出棧兩個操作，兩個操作操作的都是棧頂元素；隊列包含入隊和出隊兩個操作，元素從隊尾進入隊列，需要時從隊頭取出元素。
全文大約【4500】字，不說廢話，隻講可以讓你學到技術、明白原理的純幹貨！本文帶有豐富的案例及配圖視訊，讓你更好地了解和運用文中的技術概念，并可以給你帶來具有足夠啟迪的思考......
一. 樹的簡介
1. 概念
樹(Tree)是非線性結構的典型代表。在樹型資料結構中，資料元素之間存在一對多的關系。在資料結構中，對樹的定義是：樹是由n(n>0)個有限結點組成一個具有層次關系的集合。當n=0時，稱為空樹。
之是以把這些由層次關系的結點集合稱之為樹，主要是因為其在形狀上看起來特别像一棵倒挂的樹，即樹根朝上，樹葉朝下。首先給出樹結構所具備的特點：
(1). 樹有且僅有一個特定的根(Root)結點。
(2). 除了根結點，其餘每個結點都有且隻有一個直接前驅，這個前驅結點叫父結點.
(3). 樹的每個結點都可以有多個後繼，叫做子結點。沒有後繼的結點稱為葉子結點。有父結點，也有子結點，這樣的結點被稱為中間結點或分支結點。
(4). 除了根結點，其餘結點可分為m(m>0)個互不相交的有限集合。其中每一個集合本身又是一棵樹，稱為子樹。
但是，如果産生子樹相交的情況，就不符合樹結構的定義，也就不屬于樹了。比如下圖：
如上兩圖所示，左圖中②和③有相交，右圖中結點②和節點③均與節點⑤相連，這兩種情況下都不能稱之為樹。
2. 基本術語
2.1 樹的高度和深度
樹的最大層級數，被稱為樹的高度或深度。我們通過圖例說明如下：
如上圖所示，該樹的高度是4，深度為4。根結點在第1層，結點8、9、10位于第4層。
備注：托馬斯·科爾曼等人所著的《算法導論》一書中，樹的高度是從“0”開始計數的，在本篇文章中，我們遵照慣例，樹的高度是從“1”開始計數。
2.2 結點關系
具有同一父結點的結點互相稱為兄弟結點。比如，上文圖例所示中：結點2和3，結點4和5，結點6和7，結點8和9彼此是兄弟結點。
2.3 樹的度數
特别的，我們把：一個結點的子結點的個數稱為該結點的度數。度為0的結點就是葉子結點，而度不為0的結點就是分支結點。同時，我們還規定：一棵樹的度指的是該樹中結點的最大度數。比如，上文所示圖例中：結點2、3、4的度為2，結點6的度為1，結點5、7、8、9、10的度為0。這棵樹的度為2。
3. 樹的分類
根據度的大小，我們可以将樹可以分為二叉樹和多路樹。堆也屬于一種多路樹結構，另外根據度的大小，堆也分為二叉堆和多叉堆。具體的邏輯關系如下圖所示：
在如上的示例圖中，壹哥給出了樹型資料結構所涉及的常見的分類種類，在後續的文章中，我們會逐漸學習到，大家稍安勿躁，接下來讓我們先從二叉樹開始學起。
二. 二叉樹
1. 概念
二叉樹(Binary Tree)是樹的一種常見形式。二叉樹的任意結點最多可以有兩個子結點，也可以隻有一個或者沒有子結點。是以二叉樹的度數一定小于等于2。二叉樹結點的兩個子結點，一個被稱為左子結點，一個被稱為右子結點。二叉樹嚴格區分左右子結點，兩個子結點的順序是固定的，即使隻有一棵子樹也要區分左右。
如果我們把二叉樹繼續進行分類，就會衍生出滿二叉樹和完全二叉樹。
- 滿二叉樹：滿二叉樹是一種理想狀态。二叉樹的所有非葉子結點都存在左右子結點，每個非葉子結點的度都是2，并且所有葉子結點都在同一層上，那麼這個樹就是滿二叉樹。
如上圖所示：左圖中，所有非葉子結點都存在左右子結點，每個非葉子結點的度都是2，同時所有葉子結點均在同一層，符合滿二叉樹的定義，是以左圖是滿二叉樹。右圖中，雖然每個非葉子結點都有左右子結點，且每個非葉子結點的度都是2，但所有葉子結點并不在同一層，是以不屬于滿二叉樹。由此，我們 可以知道，判斷一棵二叉樹是否是滿二叉樹，有三個條件：
- 每個非葉子結點都存在左右2個子結點
- 每個非葉子結點的度都是2
- 所有葉子結點均在同一層
以上三個條件，實際前兩個條件描述的是同一回事。
- 完全二叉樹：如果二叉樹中除去最後一層結點為滿二叉樹，且最後一層的結點依次從左到右分布，則此二叉樹被稱為完全二叉樹。
如上圖所示，結合完全二叉樹的定義，可以知道完全二叉樹需要滿足兩個條件：
- 除最後一層外為滿二叉樹；
- 最後一層的結點依次從左至右，中間不能有缺失。
2. 性質
二叉樹的性質，也是二叉樹有關的一些結論，所謂結論，就是指這些設計到二叉樹相關的特性的内容，可以直接作為結果或者結論進行引用。我們依然分類進行描述：
2.1 普通二叉樹的性質
- 第i層最多可以有2i-1個結點：根據結論，我們可以驗證二叉樹第1層最多有1個結點，第2層最多有2個結點，第3層最多有4個結點，依次類推。當然，需要注意的是，此處說的是最多，并不是一定會有，要區厘清楚。
- 若二叉樹深度為k，則二叉樹最多有2k-1個結點：該結論也可以通過舉例驗證，二叉樹的深度為1時，結點最多就1個；深度為2時，結點最多有3個；深度為3時，結點最多為7個。依次類推，均符合該結論公式。
- 若葉子結點數為n0，度為2的結點數為n2，則n0=n2+1：該結論也可以用另外一句話表述，即葉子結點數比度為2的結點多1個。
2.2 滿二叉樹的性質
滿二叉樹是特殊的二叉樹，是以所有的普通二叉樹的性質滿二叉樹都滿足。除此之外，滿二叉樹特有的性質有：
- 滿二叉樹中第i層一定有2i-1個結點。
- 深度為k的滿二叉樹一定有2k-1個結點，且一定有2k-1個葉子結點。
- 具有n個結點的滿二叉樹的深度為log2(n+1)。
2.3 完全二叉樹的性質
如上圖所展示的是一棵完全二叉樹，為了友善區分該二叉樹的每一個結點，我們其将含有的結點按照層次從左到右依次标号，依次為1-11。若根據該規則，則對于任意一個結點i，完全二叉樹具有以下結論：
- 若i>1，則i結點的父結點的編号是i/2(向下取整)。比如：i=5結點，其父結點編号為2，滿足結論。
- 若2*i>n(n為總結點的個數)，則結點i肯定沒有左葉子結點，否則其左子結點是結點2*i。
- 若2*i+1>n，則結點i肯定沒有右子結點；否則右子結點是結點2*i+1。
- 完全二叉樹隻能有0個或1個度為1的結點，葉子結點數比度為2的結點數多1個。
總結：對于普通二叉樹，滿二叉樹，以及完全二叉樹的特點和其所具有的性質，在使用時最簡單的方式是通過畫圖例的方式進行驗證，當然如果我們能把上文中列出的所有性質公式都記住自然是最好的。
3. 二叉樹的存儲
在前面的文章中，我們已經學習過數組和連結清單，此處剛好可以使用這種結構對二叉樹的結點進行存儲。是以，二叉樹的存儲一共有兩種方式，分别是：順序存儲、鍊式存儲。
3.1 順序存儲(數組)
所謂的順序存儲，指的是使用數組存儲的二叉樹。
我們在使用數組存儲時，會按照層級順序把二叉樹的結點放到數組中對應的位置上。如果某一個結點的左子結點或右子結點空缺，則數組的相應位置也要空出來。對于一個稀疏的二叉樹(子結點不滿)來說，用順序存儲是非常浪費空間的。是以二叉樹的順序存儲一般隻适用于完全二叉樹，或者說完全二叉樹才适合使用順序表存儲。當順序存儲普通二叉樹時，需要提前将普通二叉樹轉化為完全二叉樹。
如上圖所示，給定的二叉樹是一棵普通的二叉樹。若使用數組進行存儲，首先需要将該二叉樹補充調整為一棵完全二叉樹如上右圖所示，需要添加的兩個結點使用虛線表示（不存儲具體資料，空餘），然後再使用數組存儲該完全二叉樹。可以看到，上圖的數組中，下标4和下标5位置空餘，原因是兩位位置恰好對應的是補充的兩個結點。
由此，我們也能進一步了解：若使用數組存儲普通二叉樹，往往會浪費存儲空間。
3.2 二叉樹鍊式存儲(連結清單)
我們推薦大家使用連結清單對二叉樹進行存儲。鍊式存儲二叉樹，其結點結構與雙向循環連結清單一緻，每一個結點包含三個部分：存儲資料的data變量、指向左子結點的left指針、指向右子結點的right指針，這樣的連結清單稱為二叉連結清單。如下圖所示：
三. 周遊操作
在前面的文章中，我們已經介紹過數組的周遊和連結清單的周遊。所謂周遊就是按照某種邏輯規則，依次通路集合的每個元素的操作。對于二叉樹，同樣可以按照某種邏輯依次通路二叉樹的每一個結點。二叉樹的周遊可以分為兩大類：深度優先周遊、廣度優先周遊。
1. 深度優先周遊
所謂深度優先(depth first search，DFS)，顧名思義就是偏向于縱深，“一頭紮到底”的通路方式。深度優先周遊又根據周遊順序的不同分為三種：前序周遊、中序周遊、後序周遊。
1.1 前序周遊
所謂前序周遊，是指二叉樹周遊每個子樹的時候，都是按照根結點、左子樹、右子樹的順序來周遊，因為根結點在前，是以叫做前序周遊。前序周遊中根結點的優先級别最高。如下圖所示：
如上圖所示：
- 先通路第一層，第一次隻有一個結點，可以得到A結點。
- 再通路第二層，第二層中B是A的左子樹，而B又是第三層D和E的父結點，是以要先通路B結點。
- 通路B後，再通路B的下一層即第三層。在第三層中，B的左子樹D，又包含一個右子樹G，是以，對于D和G來說，應該先通路D。是以通路D結點。
- 通路D後，通路下一層即第四層，D隻有一個右子樹G，是以通路G結點。
- G結點通路結束後，意味着D和G組成的這課分支子樹就結束了，進一步通路BDE這三個結點組成的分支子樹。因為B和D已經被通路過了，是以通路E結點。
- 通路E後，BDE組成的分支子樹已經周遊結束，繼續周遊ABC結點組成的子樹，由于A和B已經被通路，是以通路C結點。
- 依次類推，和左側通路規則一樣，繼續通路得到F結點和H結點。
1.2 中序周遊
如果二叉樹周遊每個子樹的時候，都是按照左子樹、根結點、右子樹的順序來周遊，因為根結點在中間，是以叫做中序周遊。如下圖所示：
如上圖所示，虛線箭頭和數字就是按照中序周遊的規則對二叉樹進行周遊的步驟，最後可得到中序周遊順序：D G B E A C H F。通過上面二叉樹的圖示和結果，我們還可以發現一個中序周遊的規律：第一個元素是樹結構中最左側的元素，最後一個是樹結構中最右側的元素，根結點在中間位置輸出。
1.3 後序周遊
二叉樹周遊每個子樹的時候，都是按照左子樹、右子樹、根結點的順序來周遊，因為根結點在最後，是以叫做後序周遊。如下圖所示：
如上圖所示，虛線箭頭和數字表示除了二叉樹的後續周遊的步驟。我們發現出規律：後序周遊第一個輸出的元素是根結點左側最底層第一個元素，最後一個輸出的是根結點元素。
2. 廣度優先周遊
廣度優先周遊(Breadth First Search，BFS)也叫層序周遊，就是按照二叉樹中的層次從左到右依次周遊每層中的結點。層序周遊的實作思路是利用隊列來實作。先将樹的根結點入隊，然後再讓隊列中的結點出隊。隊列中每一個結點出隊的時候，都要将該結點的左子結點和右子結點入隊。當隊列中的所有結點都出隊，樹中的所有結點也就周遊完成。此時隊列中結點的出隊順序就是層次周遊的最終結果。如下圖所示：
如上圖所示，廣度優先周遊比較容易了解，從上到下按層依次對二叉樹的結點進行周遊，最後可得到周遊結果。
四. 結語
通過本篇内容，帶大家開始學習樹型資料結構，在實際應用中，二叉樹又是使用最廣泛的，特别是二叉樹的幾種周遊操作的規則，需要做着重掌握。在面試或應試考試中，通常會根據前序、中序、後序中的兩種序列，詢問另外一種樹的周遊結果，大家要重點關注。
Java基礎-線性結構中的棧、隊列和串
關于線性結構中的雙向連結清單如何實作
5分鐘學會資料結構中的線性連結清單
深入淺出Spring原理及實戰「緩存Cache開發系列」
更多技術類幹貨/IT程式員資訊，關注@千鋒教育