樹的概念
樹(tree)是一種能夠分層存儲數據的重要數據結構，樹中的每個元素被稱為樹的節點，每個節點有若干個指針指向子節點。從節點的角度來看，樹是由唯一的起始節點引出的節點集合。這個起始結點稱為根(root)。樹中節點的子樹數目稱為節點的度(degree)。在面試中，關于樹的面試問題非常常見，尤其是關于二叉樹(binary tree)，二叉搜索樹(Binary Search Tree, BST)的問題。
所謂的二叉樹，是指對于樹中的每個節點而言，至多有左右兩個子節點，即任意節點的度小于等于2。而廣義的樹則沒有如上限制。二叉樹是最常見的樹形結構。二分查找樹是二叉樹的一種特例，對于二分查找樹的任意節點，該節點存儲的數值一定比左子樹的所有節點的值大比右子樹的所有節點的值小“(與之完全對稱的情況也是有效的：即該節點存儲的數值一定比左子樹的所有節點的值小比右子樹的所有節點的值大)。
基于這個特性，二分查找樹通常被用于維護有序數據。二分查找樹查找、刪除、插入的效率都會于一般的線性數據結構。事實上，對于二分查找樹的操作相當于執行二分搜索，其執行效率與樹的高度(depth)有關，檢索任意數據的比較次數不會多于樹的高度。這里需要引入高度的概念：對一棵樹而言，從根節點到某個節點的路徑長度稱為該節點的層數(level)，根節點為第0層，非根節點的層數是其父節點的層數加1。樹的高度定義為該樹中層數最大的葉節點的層數加1，即相當于于從根節點到葉節點的最長路徑加1。由此，對于n個數據，二分查找樹應該以“盡可能小的高度存儲所有數據。由于二叉樹第L層至多可以存儲 2^L 個節點，故樹的高度應在logn量級，因此，二分查找樹的搜索效率為O(logn)。
直觀上看，盡可能地把二分查找樹的每一層“塞滿”數據可以使得搜索效率最高，但考慮到每次插入刪除都需要維護二分查找樹的性質，要實現這點并不容易。特別地，當二分查找樹退化為一個由小到大排列的單鏈表(每個節點只有右孩子)，其搜索效率變為O(n)。為了解決這樣的問題，人們引入平衡二叉樹的概念。所謂平衡二叉樹，是指一棵樹的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。通過恰當的構造與調整，平衡二叉樹能夠保證每次插入刪除之后都保持平衡性。平衡二叉樹的具體實現算法包括AVL算法和紅黑算法等。由于平衡二叉樹的實現比較復雜，故一般面試官只會問些概念性的問題。
滿二叉樹(full binary tree)：如果一棵二叉樹的任何結點，或者是葉節點，或者左右子樹都存在，則這棵二叉樹稱作滿二叉樹。
完全二叉樹(complete binary tree)：如果一棵二叉樹最多只有最下面的兩層節點度數可以小于2，并且最下面一層的節點都集中在該層最左邊的連續位置上，則此二叉樹稱作完全二叉樹。
Free tree
指的是相互連接的無環無向圖
假設 G = (V, E) 是一個無向圖，那么下面的語句是等價的：
- G 是一個 free tree
- G 中的任意兩個節點間都有唯一的一條路徑
- G 是連通的的，但是如果去掉任何一條邊，G 就不連通了
- G 是連通的，并且 $|E|=|V|-1$
- G 是無環的，并且 $|E|=|V|-1$
- G 是無環的，但是加入任何一條新的邊，就會變成有環的
Forest 森林
同樣是無環無向圖，但不是所有的節點都是連通的
下圖中包含一個環，所以不能算是森林：
Rooted Tree
有根的樹也是一棵 free tree，但是其中一個節點和其他不同，稱為根。有根樹中有一些概念需要理解清楚，這里只列舉出來不再贅述：ancestor, descendant, proper ancestor, proper descendant, parent, child, siblings, external node(leaf), internal node。
一個節點的孩子數量稱之為節點的度(degree)，從根到某節點的要經過的邊的數量就是該節點的深度，最大的深度稱為樹的高度。
根樹有幾個特例，也非常常用，需要理解清楚，這里列舉如下：
- Binary tree
- Full binary tree: each node is either a leaf or has degree exactly 2
- Complete k-ary tree: a k-ary tree in which all leaves have the same depth and all internal nodes have degree k
- Binary search tree: 一個節點的左右子節點和節點本身滿足一定的大小關系
樹的遍歷
這一部分也是非常重要的內容，基本來說各類考點都在這里，不但需要對概念的清晰理解，還需要利用遞歸來解決問題（雖然不用遞歸也可以），主要有下面這四類：
- 前序遍歷
- 中序遍歷
- 后序遍歷
- 層次遍歷
具體的概念可以在 wiki 上查看，注意一下層次遍歷可能需要一些特殊處理即可。
二叉樹的常見操作包括樹的遍歷，即以一種特定的規律訪問樹中的所有節點。常見的遍歷方式包括：
- 前序遍歷(Pre-order traversal)：訪問根結點；按前序遍歷左子樹；按前序遍歷右子樹。
- 中序遍歷(In-order traversal)：按中序遍歷左子樹；訪問根結點；按中序遍歷右子樹。特別地，對于二分查找樹而言，中序遍歷可以獲得一個由小到大或者由大到小的有序序列。
- 后續遍歷(Post-order traversal)：按后序遍歷左子樹；按后序遍歷右子樹；訪問根結點。
以上三種遍歷方式都是深度優先搜索算法(depth-first search)。深度優先算法最自然的實現方式是通過遞歸實現，事實上，大部分樹相關的面試問題都可以優先考慮遞歸。此外，另一個值得注意的要點是：深度優先的算法往往都可以通過使用棧數據結構將遞歸化為非遞歸實現。這里利用了棧先進后出的特性，其數據的進出順序與遞歸順序一致(請見 Stack and Queue) 。
層次遍歷(Level traversal)：首先訪問第0層，也就是根結點所在的層；當第i層的所有結點訪問完之后，再從左至右依次訪問第i+1層的各個結點。層次遍歷屬于廣度優先搜索算法(breadth-first search)。廣度優先算法往往通過隊列數據結構實現。
B-Tree
如果我們想要表示一個 complete binary tree 的話，其實可以用數組來完成，這種結構其實也可以看成是一個堆。堆的話需要理解的不算特別多，注意下最大堆最小堆，以及對應的操作即可。另外前面提到的優先隊列也可以認為是堆，不過這個不展開了。
這一部分我們著重來看看 B-Tree，這是一類搜索樹，在給定 n 個節點的條件下，盡可能減少樹的高度，相對于原來的二叉搜索樹，B-Tree 做了兩個調整：
- 節點可以有多于兩個子節點
- 節點中可以保存多個元素
因為需要保存不定數量的元素，所以一般用 set 來實現（這種情況下不允許有重復的元素，重復的情況這里暫時不考慮）。稍微提一下，許多數據庫都是用 B-Tree 實現的。
所有的 B-Tree 都有一個非常重要的常數 MINIMUM，決定了每個節點中需要保存多少元素，具體的規則如下：
- 根節點有 0 或 1 個元素，其他的節點至少需要保存 MINIMUM 個元素
- 一個節點中最多可以保存
2*MINIMUM個元素 - 一個節點中保存的元素是有序的，從最小到最大
- 假設一個非葉節點中存有 N 個元素，那么它會有 N+1 個子樹 <
)
