一. 二叉樹
L、D、R分別表示遍歷左子樹、訪問根結點和遍歷右子樹
- 先序遍歷：DLR
- 中序遍歷：LDR
- 後序遍歷：LRD
僅有前序和後序遍歷，不能確定一個二叉樹，必須有中序遍歷的結果
1. 二叉樹的性質
- 性質1：在二叉樹中第 i 層的結點數最多為2^(i-1)（i ≥ 1）
- 性質2：高度為k的二叉樹其結點總數最多為2^k－1（ k ≥ 1）
- 性質3：對任意的非空二叉樹 T ，如果葉結點的個數為 n0，而其度為 2 的結點數為 n2，則：n0 = n2 + 1
2. 滿二叉樹
深度為k，且有2^k-1個節點稱之為滿二叉樹；
- 性質4：第i層上的節點數為2^(i-1)；
3. 完全二叉樹
深度為k，有n個節點的二叉樹，當且僅當其每一個節點都與深度為k的滿二叉樹中，序號為1至n的節點對應時，稱之為完全二叉樹。
- 性質5：對於具有n個結點的完全二叉樹的高度為log2(n)+1
- 求完全二叉樹的葉子結點個數：
4. 二叉樹的構造
//n 表示當前結點字符
Node* tree(vector<char> data, int n) {
Node* node;
if (n >= data.size())
return NULL;
if (data[n] == '#')
return NULL;
node = new Node;
node->data = data[n];
node->left = tree(data, n + 1);
node->right = tree(data, n + 2);
return node;
}
/<char>
二. 堆
堆通常是一個可以被看做一棵樹的數組對象。堆的實現通過構造二叉堆（binary heap），實為二叉樹的一種；
- 任意節點小於（或大於）它的所有後裔，最小元（或最大元）在堆的根上（堆序性）。
- 堆總是一棵完全樹。即除了最底層，其他層的節點都被元素填滿，且最底層儘可能地從左到右填入。
將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、斐波那契堆等。
通常堆是通過一維數組來實現的。在數組起始位置為1的情形中：
- 父節點i的左子節點在位置(2*i);
- 父節點i的右子節點在位置(2*i+1);
- 子節點i的父節點在位置(i/2);
三. 霍夫曼樹
霍夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的路徑長度是從樹根到每一結點的路徑長度之和，記為WPL=（W1L1+W2L2+W3L3+…+WnLn），N個權值Wi（i=1,2,…n）構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li（i=1,2,…n）。可以證明霍夫曼樹的WPL是最小的。
1. 霍夫曼樹構造
- 根據給定的n個權值(W1,W2...Wn)，使對應節點構成n個二叉樹的森林T=(T1,T2...Tn)，其中每個二叉樹Ti(1 <= i <= n)中都有一個帶權值為Wi的根節點，其左、右子樹均為空。
- 在森林T中選取兩個節點權值最小的子樹，分別作為左、右子樹構造一個新的二叉樹，且置新的二叉樹的根節點的權值為其左右子樹上根節點權值之和。
- 在森林T中，用新得到的二叉樹替代選取的兩個二叉樹。
- 重複2和3，直到T只包含一個樹為止。這個數就是霍夫曼樹。
定理：對於具有n個葉子節點的霍夫曼樹，共有2n-1個節點。這是由於霍夫曼樹只有度為0和度為2的結點，根據二叉樹的性質 n0 = n2 + 1，因此度為2的結點個數為n-1個，總共有2n-1個節點。
2. 霍夫曼編碼
對於一個霍夫曼樹，所有左鏈接取’0’、右鏈接取’1’。從樹根至樹葉依序記錄所有字母的編碼。
3. 帶權路徑
- 結點的權：若將樹中結點賦給一個有著某種含義的數值，則這個數值稱為該結點的權。
- 結點的帶權路徑：從根結點到該結點之間的路徑長度與該結點的權的乘積。
- 樹的帶權路徑：所有葉子結點的帶權路徑長度之和，記為WPL。
四. 二叉排序樹
二叉查找樹，也稱二叉搜索樹、有序二叉樹，排序二叉樹，是指一棵空樹或者具有下列性質的二叉樹：
- 任意節點的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
- 任意節點的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
- 任意節點的左、右子樹也分別為二叉查找樹；
- 沒有鍵值相等的節點。
二分查找的時間複雜度是O(log(n))，最壞情況下的時間複雜度是O(n)（相當於順序查找）
五. 平衡二叉樹
平衡樹是計算機科學中的一類改進的二叉查找樹。一般的二叉查找樹的查詢複雜度是跟目標結點到樹根的距離（即深度）有關，因此當結點的深度普遍較大時，查詢的均攤複雜度會上升，為了更高效的查詢，平衡樹應運而生了。平衡指所有葉子的深度趨於平衡，更廣義的是指在樹上所有可能查找的均攤複雜度偏低。
1. AVL樹
AVL樹是最先發明的 自平衡二叉查找樹。在AVL樹中任何節點的兩個子樹的高度最大差別為一，所以它也被稱為高度平衡樹。
- 它的左子樹和右子樹都是平衡二叉樹。
- 左子樹和右子樹的深度之差的絕對值不超過1。
增加和刪除可能需要通過一次或多次樹旋轉來重新平衡這個樹。
- 右旋：左結點轉到根節點位置。
- 左旋：右節點轉到根節點位置。
高度為k的AVL樹，節點數N最多2^k -1，即滿二叉樹；
2. 紅黑樹
紅黑樹是一種自平衡二叉查找樹，每個節點都帶有顏色屬性的二叉查找樹，顏色為紅色或黑色。在二叉查找樹強制一般要求以外，對於任何有效的紅黑樹我們增加了如下的額外要求：
- 節點是紅色或黑色。
- 根是黑色。
- 所有葉子都是黑色（葉子是NIL節點）。
- 每個紅色節點必須有兩個黑色的子節點。（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。）
- 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。
如果一條路徑上的頂點除了起點和終點可以相同外，其它頂點均不相同，則稱此路徑為一條簡單路徑；起點和終點相同的簡單路徑稱為迴路（或環）。
紅黑樹相對於AVL樹來說，犧牲了部分平衡性以換取插入/刪除操作時少量的旋轉操作，整體來說性能要優於AVL樹。
這些約束確保了紅黑樹的關鍵特性：從根到葉子的最長的可能路徑不多於最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限 允許紅黑樹在最壞情況下都是高效的，而不同於普通的二叉查找樹。
在很多樹數據結構的表示中，一個節點有可能只有一個子節點，而葉子節點包含數據。用這種範例表示紅黑樹是可能的，但是這會改變一些性質並使算法複雜。為此，本文中我們使用”nil葉子”或”空（null）葉子”，如上圖所示，它不包含數據而只充當樹在此結束的指示。這些節點在繪圖中經常被省略，導致了這些樹好像同上述原則相矛盾，而實際上不是這樣。與此有關的結論是所有節點都有兩個子節點，儘管其中的一個或兩個可能是空葉子。
因為每一個紅黑樹也是一個特化的二叉查找樹，因此紅黑樹上的只讀操作與普通二叉查找樹上的只讀操作相同。然而，在紅黑樹上進行插入操作和刪除操作會導致不再符合紅黑樹的性質。恢復紅黑樹的性質需要少量（O(log n)）的顏色變更（實際是非常快速的）和不超過三次樹旋轉（對於插入操作是兩次）。雖然插入和刪除很複雜，但操作時間仍可以保持為O(log n)次。
六. B-樹
是一種多路搜索樹（並不是二叉的）：
- 所有葉子結點位於同一層，並且 不帶信息。
- 樹中每個節點最多有m個子樹(即至多含有m-1個關鍵字)。
- 若根節點不是終端節點，則根節點子樹[2,m].
- 除根節點外其他非葉子節點至少有[m/2]個子樹(即至少含有[m/2]-1個關鍵字)。
- 每個非葉子節點的結構為：
- | n | p0 | k1 | p1 | k2 | p2 | … | kn | pn | >n為該節點中的關鍵字個數，除根節點外，其他所有非葉子節點的關鍵字個數n：[m/2]-1 <= n <= m-1;
ki(i <= i <=n)為該節點的關鍵字且滿足ki < ki+1
pi(0 <= i <=n)為該節點的孩子節點指針pi(0 <= i <=n-1)所指節點上的關鍵字大於等於ki且小於ki+1，pn所指節點上的關鍵字大於kn.
B-樹的階：所有節點的孩子節點數的最大值
1. B-樹的查找
在B-樹中的查找給定關鍵字的方法 類似於二叉排序樹上的查找，不同的是在每個節點上確定向下查找的路徑不一定是二路的，而是n+1路的。因為節點內的關鍵字序列key[1..n]有序，故既可以使用順序查找，也可以使用二分查找。在一棵B-樹上查找關鍵字為k的方法為：將k與根節點中的key[i]進行比較： 1. 若k=key[i]，則查找成功； 2. 若kkey[n]，則沿著指針ptr[n]所指的子樹繼續查找。
2. B-樹的插入
將關鍵字k插入到B-樹的過程分兩步完成：
- 利用B-樹的查找算法查找出該關鍵字的插入節點(注意B-樹的插入節點一定屬於最低非葉子節點層)。
- 判斷該節點是否還有空位，即判斷該節點是否滿足n < m-1，若滿足：直接把關鍵字k插入到該節點合適位置上；若不滿足：分裂節點，取一新節點，把原節點上的關鍵字和k按升序排列後，從中間位置(m/2)處把關鍵字(不包括中間位置的關鍵字)分成兩部分，左部分所含關鍵字放在舊節點中，右部分關鍵字放在新節點中，中間位置的關鍵字連同新節點的存儲位置插入到雙親節點。如果雙親節點的關鍵字個數也超出max則再分裂。
3. B-樹的刪除
首先查找B樹中需刪除的元素，如果該元素在B樹中存在，則將該元素在其結點中進行刪除；如果刪除該元素後，首先判斷該元素是否有左右孩子結點，如果有，則上移孩子結點中的某相近元素到父節點中，然後是移動之後的情況；如果沒有，直接刪除後，然後是移動之後的情況。
刪除元素，移動相應元素之後，如果某結點中元素數目（即關鍵字數）小於Min(m/2)-1，則需要看其某相鄰兄弟結點是否豐滿，如果豐滿，則向父節點借一個元素來滿足條件；如果其相鄰兄弟都剛脫貧，即借了之後其結點數目小於Min(m/2)-1，則該結點與其相鄰的某一兄弟結點進行“合併”成一個結點，
七. B+樹
是一種自平衡二叉樹，通常用於數據庫和操作系統的文件系統中。B+樹的特點是能夠保持數據穩定有序，其插入與修改擁有較穩定的對數時間複雜度。B+樹元素自底向上插入，這與二叉樹恰好相反。B+樹不需要象其他自平衡二叉查找樹那樣經常的重新平衡 。
B+樹是B-樹的變體，也是一種多路搜索樹：
- 每個分支節點最多m個子樹
- 根節點沒有子樹或至少兩個子樹
- 除根節點外，其他每個分支節點至少[m/2]個子樹
- 有n個子樹的節點有n個關鍵字
- 所有葉子節點包含全部關鍵字及指向相應記錄的指針，而且葉子節點按關鍵字大小順序鏈接(可以把每個葉子及誒單看成一個基本索引塊，它的指針不再指向另一級索引塊，而是直接指向數據文件中的記錄)
- 所有分支節點中僅僅包含它的哥哥子節點(即下級索引塊)中最大關鍵字及指向子節點的指針。
m階的B+樹和B-樹的主要差異如下：
- 在B+樹中，具有n個關鍵字的節點含有n個子樹，即每個關鍵字對應一個子樹，而在B-樹中，具有n個關鍵字的節點含有(n+1)個子樹。
- 在B+樹中，每個節點(除根節點外)中的關鍵字個數n的取值範圍是[m/2] <= n <= m，根節點n的取值範圍2 <=n <=m；而在B-樹中，除根節點外，其他所有非葉子節點的關鍵字個數：[m/2]-1 <= n <= m-1，根節點關鍵字個數為1 <= n <= m-1
- B+樹中所有葉子節點包含了全部關鍵字，即其他非葉子節點中的關鍵字包含在葉子節點中，而在B-樹中，關鍵字是不重複的。
- B+樹中所有非葉子節點僅起到索引的作用，即節點中每個索引項值含有對應子樹的最大關鍵字和指向該子樹的指針，不含有該關鍵字對應記錄的存儲地址。而在B-樹中，每個關鍵字對應一個記錄的存儲地址。
- 通常B+樹上有兩個頭指針，一個指向根節點，另一個指向關鍵字最小的葉子節點，所有葉子節點鏈接成一個不定長的線性表。
1. B+樹的查找
在B+樹中可以採用兩種查找方式：
- 直接從最小關鍵字開始順序查找。
- 從B+樹的根節點開始隨機查找。這種查找方式與B-樹的查找方式類似，只是在分支節點上的關鍵字與查找值相等時，查找並不會結束，要繼續查到葉子節點為止，此時若查找成功，則按所給指針取出對應元素。
在B+樹中，不管查找是否成功，每次查找都是經歷一條樹從根節點到葉子節點的路徑。
2. B+樹的插入
- 首先，查找要插入其中的節點的位置。接著把值插入這個節點中。
- 如果沒有節點處於違規狀態則處理結束。
- 如果某個節點有過多元素，則把它分裂為兩個節點，每個都有最小數目的元素。在樹上遞歸向上繼續這個處理直到到達根節點，如果根節點被分裂，則創建一個新根節點。為了使它工作，元素的最小和最大數目典型的必須選擇為使最小數不小於最大數的一半。
3. B+樹的刪除
- 首先，查找要刪除的值。接著從包含它的節點中刪除這個值。
- 如果沒有節點處於違規狀態則處理結束。
- 如果節點處於違規狀態則有兩種可能情況：
- 它的兄弟節點，就是同一個父節點的子節點，可以把一個或多個它的子節點轉移到當前節點，而把它返回為合法狀態。如果是這樣，在更改父節點和兩個兄弟節點的分離值之後處理結束。
- 它的兄弟節點由於處在低邊界上而沒有額外的子節點。在這種情況下把兩個兄弟節點合併到一個單一的節點中，而且我們遞歸到父節點上，因為它被刪除了一個子節點。持續這個處理直到當前節點是合法狀態或者到達根節點，在其上根節點的子節點被合併而且合併後的節點成為新的根節點。
B-樹和B+樹 主要用於外部查找，即數據在外存中。
4. B+樹的優勢所在
為什麼說B+樹比B-樹更適合實際應用中操作系統的文件索引和數據庫索引？
- B+樹的磁盤讀寫代價更低
- 我們都知道磁盤時可以塊存儲的，也就是同一個磁道上同一盤塊中的所有數據都可以一次全部讀取。而B+樹的內部結點並沒有指向關鍵字具體信息的指針(比如文件內容的具體地址 ） 。因此其內部結點相對B-樹更小。如果把所有同一內部結點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多。這樣，一次性讀入內存中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了。
- 舉個例子，假設磁盤中的一個盤塊容納16bytes，而一個關鍵字2bytes，一個關鍵字具體信息指針2bytes。一棵9階B-樹(一個結點最多8個關鍵字)的內部結點需要2個盤塊。而B+樹內部結點只需要1個盤塊。當需要把內部結點讀入內存中的時候，B-樹就比B+數多一次盤塊查找時間（在磁盤中就是盤片旋轉的時間）。
- B+樹的查詢效率更加穩定。
- 由於非終結點並不是最終指向文件內容的結點，而只是葉子結點中關鍵字的索引。所以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導致每一個數據的查詢效率相當。
八. Trie樹
Trie樹，又稱前綴樹，字典樹， 是一種有序樹，用於保存關聯數組，其中的鍵通常是字符串。與二叉查找樹不同，鍵不是直接保存在節點中，而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的前綴，也就是這個節點對應的字符串，而根節點對應空字符串。一般情況下，不是所有的節點都有對應的值，只有葉子節點和部分內部節點所對應的鍵才有相關的值。
Trie樹查詢和插入時間複雜度都是 O(n)，是一種以空間換時間的方法。當節點樹較多的時候，Trie 樹佔用的內存會很大。
Trie樹常用於搜索提示。如當輸入一個網址，可以自動搜索出可能的選擇。當沒有完全匹配的搜索結果，可以返回前綴最相似的可能。
寫在最後
以上就是筆者整理的一些花裡胡哨"樹"的面試題；當然，要想拿下字節跳動的offer光靠這些花裡胡哨"樹"可不西行喲，像Kafka、Mysql、Tomcat、Docker、Spring、MyBatis、Nginx、Netty、Dubbo、Redis、Netty、Spring cloud、分佈式、高併發、性能調優、微服務等架構技術至少也要掌握各七八十才行！
針對以上的技術點呢，筆者也整理了一套視頻學習資料和麵試題，
需要的朋友可以幫忙轉發一下
然後私信我【學習】，即可免費領取！
以下是部分學習資料截圖
閱讀更多 Java肖先生 的文章
