景禹
對于大量的輸入資料，連結清單的通路時間太長，不宜使用。而樹剛好就是一種極大地縮短通路時間的資料結構，其平均通路時間複雜度為O(logN)。
鑒于有些朋友并不僅僅是因為提高自己的程式設計能力來學習資料結構，是以我們先來唠叨一些有關于樹的基本概念和考點。
01.
樹的基本概念
樹(Tree)是n(n>=0)個結點的有限集。當n=0時成為空樹，在任意一棵非空樹中：
- 有且僅有一個特定的稱為根(Root)的結點；
- 當n>1時，其餘結點可分為m(m>0)個互不相交的有限集T1、T2、...、Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹(SubTree)。
注意：
- n>0時，根結點是唯一的，堅決不可能存在多個根結點。
- m>0時，子樹的個數是沒有限制的，但它們互相是一定不會相交的。
比如，下圖中的就不符合樹的定義：
樹中結點的分類：
如圖中所示，每一個圈圈我們就稱為樹的一個結點。結點擁有的子樹數稱為結點的度-(Degree)，樹的度取樹内各結點的度的最大值。
- 度為0的結點稱為葉結點(Leaf)或終端結點；
- 度不為0的結點稱為分支結點或非終端結點，除根結點外，分支結點也稱為内部結點。
樹中結點之間的關系：
- 結點的子樹的根稱為結點的孩子(Child)，相應的，該結點稱為孩子的雙親(Parent)，同一雙親的孩子之間互稱為兄弟(Sibling)。
- 結點的祖先是從根到該結點所經分支上的所有結點。
結點的層次：
- 結點的層次(Level)從根開始，根為第一層，根的孩子為第二層。
- 其雙親在同一層的結點互為堂兄弟。
- 樹中結點的最大層次稱為樹的深度(Depth)或高度。
02.
樹的存儲結構
不論是考試還是準備找工作面試筆試，永遠記住，你了解的越多，那麼你需要記住的東西就越少的道理。
之前景禹更新過有關順序存儲結構與鍊式存儲結構，在談棧與隊列的時候也談到這兩種存儲結構，這也就是為什麼所有的教材将這兩種存儲結構安排在最前面的緣由。關于樹的存儲結構同樣離不開這兩種存儲結構。
要存儲樹，簡單的順序存儲結構和鍊式存儲結構是不行滴！不過如果充分利用它們各自的特點，結合兩種存儲結構完全可以間接地來實作樹的存儲。
雙親表示法
- 雙親表示法，言外之意就是以雙親作為索引的關鍵詞的一種存儲方式。
- 我們假設以一組連續空間存儲樹的結點，同時在每個結點中，附設一個訓示其雙親結點在數組中位置的元素。
- 也就是說，每個結點除了知道自己是誰之外，還知道它的粑粑麻麻在哪裡。
- 根結點沒有雙親結點，其Parent用 -1 表示。
這樣的存儲結構，我們可以根據某結點的parent指針找到它的雙親結點，所用的時間複雜度是O(1)，索引到parent的值為-1時，表示找到了樹結點的根。
可是，如果我們要知道某結點的孩子是什麼？那麼不好意思，請周遊整個樹結構。那麼我們是不是可以一起改進一下呢？
那現在我們又比較關心它們兄弟之間的關系呢？當然也是可以的：
但是我們可以發現，這張表格中存在大量的 -1，也就是說這樣的存儲方式浪費了大量的存儲空間，這并不是我們所期望看到的，是以，我們來看一種更高效的樹的存儲結構。
孩子表示法
将樹中的每個結點的孩子結點排列成一個線性表，用連結清單存儲起來。對于含有 n 個結點的樹來說，就會有 n 個單連結清單，将 n 個單連結清單的頭指針存儲在一個線性表中，這樣的表示方法就是孩子表示法。
是不是瞬間感覺清爽多了，但是孩子表示法正好與雙親表示法相反，适用于查找某結點的孩子結點，不适用于查找其父結點。可以将兩種表示方法合二為一，存儲效果如下所示：
孩子兄弟表示法
使用鍊式存儲結構存儲普通樹。連結清單中每個結點由 3 部分組成：
通過孩子兄弟表示法，普通樹轉化為了二叉樹，是以孩子兄弟表示法又被稱為“二叉樹表示法”或者“二叉連結清單表示法”。如下圖所示：
03.
二叉樹
單連結清單
世上樹有萬千種，唯有二叉課上講。這裡的二叉是二叉樹，因為二叉樹使用的範圍最廣，最具有代表意義，是以不論教材還是考試都以二叉樹為主。
二叉樹（Binary Tree）是n（n>=0）個結點的有限集合，該集合或者為空集（空二叉樹），或者由一個根結點和兩棵互不相交的、分别稱為根結點的左子樹和右子樹的二叉樹組成。
這個定義顯然是遞歸形式的，是以咱看上去有點暈，因為自古有“神使用遞歸，人使用疊代！“ 遞歸在樹的相關操作中簡直友善的不要不要！
二叉樹的特點
- 每個結點最多有兩棵子樹，是以二叉樹中不存在度大于2的結點。（注意：不是都需要兩棵子樹，而是最多可以有兩棵，沒有子樹或者有一棵子樹也都是可以的。）
- 左子樹和右子樹是有順序的，次序不能颠倒。
- 即使樹中某結點隻有一棵子樹，也要區分它是左子樹還是右子樹，下面是完全不同的二叉樹：
二叉樹的五種基本形态
若隻從形态上來考慮，擁有三個結點的普通樹隻有兩種情況：兩層或者三層。而對于二叉樹來說，由于要區分左右，是以就演變成五種形态（這也是為什麼考試面試筆試總選擇二叉樹進行考察）：
二叉樹還可以繼續分類，衍生出滿二叉樹和完全二叉樹。
滿二叉樹
如果二叉樹中除了葉子結點，每個結點的度都為 2，則此二叉樹稱為滿二叉樹。
滿二叉樹除了滿足普通二叉樹的性質，還具有以下性質（請注意圖中的标注）：
1. 滿二叉樹中第 n 層的節點數為 $2^{n-1}$ 個。
2. 深度為 k 的滿二叉樹必有 $2^{k}-1$ 個節點 ，葉子數為 $2^{k-1}$。
3. 滿二叉樹中不存在度為 1 的節點，每一個分支點中都兩棵深度相同的子樹，且葉子節點都在最底層。
4. 具有 n 個節點的滿二叉樹的深度為 $log_2(n+1)$。
完全二叉樹
如果二叉樹中除去最後一層節點為滿二叉樹，且最後一層的結點依次從左到右分布，則此二叉樹被稱為完全二叉樹。
完全二叉樹除了具有普通二叉樹的性質，它自身也具有一些獨特的性質，比如說，n 個結點的完全二叉樹的深度為 ⌊$log_2n$⌋+1（後面有證明）。
⌊$log_2{n}$⌋ 表示取小于 $log_2{n}$ 的最大整數，向下取整。例如，⌊$log_2{8}$⌋ = 3，而 ⌊$log_2{10}$⌋ 結果也是 3。
對于任意一個完全二叉樹來說，如果将含有的結點按照層次從左到右依次标号（如圖上圖)），對于任意一個結點 i ，完全二叉樹還有以下幾個結論成立：
1. 當 i>1 時，父親結點為結點 [i/2] 。（i=1 時，表示的是根結點，無父親結點）
2. 如果 2*i>n（總結點的個數） ，則結點 i 肯定沒有左孩子（為葉子結點）；否則其左孩子是結點 2*i 。
3. 如果 2*i+1>n ，則結點 $i$ 肯定沒有右孩子；否則右孩子是結點 2*i+1 。
二叉樹的性質(不考試的朋友可以跳過了）
二叉樹的性質一：在二叉樹的第i層上至多有$2^{i-1}$個結點(i>=1)
這個性質其實很好記憶，考試的時候懂得畫出二叉樹的圖便可以推出
二叉樹的性質二：深度為k的二叉樹至多有$2^k-1$個結點(k>=1)
二叉樹的性質三：對任何一棵二叉樹T，如果其終端結點數為$n_0$，度為2的結點數為$n_2$，則$n_0$=$n_2$+1
二叉樹的性質四：具有n個結點的完全二叉樹的深度為⌊log₂n⌋+1
小禹禹們！能看到這兒，你真的很棒！今天的内容是最基礎的，後面景禹會陸續更新包括樹的周遊、二叉排序樹、哈弗曼樹、平衡二叉樹、B樹和B+樹、紅黑樹的相關内容！晚安
，小禹禹們！景禹原創不易，覺得不錯請順手在文末右下角點個，如果文中有錯誤，也歡迎大佬指出，謝謝你呀！幫忙轉發給需要的朋友，景禹不勝感激！！！
歡迎關注我的公衆号“五分鐘學算法”，如果喜歡，麻煩點一下