什麼是樹？為什麼要有樹？
個人了解：樹就是帶有一定層次結構的抽象資料類型。因為将資料分成有層次類型之後，在管理和查找操作上就更有效率。
一、二叉樹
二叉樹：每個節點最多含有兩個子樹的樹稱為二叉樹。
滿二叉樹：除最後一層無任何子節點外，每一層上的所有結點都有兩個子結點。也可以這樣了解，除葉子結點外的所有結點均有兩個子結點。節點數達到最大值，所有葉子結點必須在同一層上
完全二叉樹：若設二叉樹的深度為h，除第 h 層外，其它各層 (1～(h-1)層) 的結點數都達到最大個數，第h層所有的結點都連續集中在最左邊，這就是完全二叉樹。
注：完全二叉樹是效率很高的資料結構，堆是一種完全二叉樹或者近似完全二叉樹，是以效率極高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能優化，二叉排序樹的效率也要借助平衡性來提高，而平衡性基于完全二叉樹。
二叉樹的三種周遊方式：
先序周遊：先根節點->周遊左子樹->周遊右子樹
中序周遊：周遊左子樹->根節點->周遊右子樹
後序周遊：周遊左子樹->周遊右子樹->根節點
二、動态查找樹
2.1 二叉查找樹
二叉查找樹定義：又稱為是二叉排序樹（Binary Sort Tree）或二叉搜尋樹。二叉排序樹或者是一棵空樹，或者是具有下列性質的
1) 若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
2) 若右子樹不空，則右子樹上所有結點的值均大于或等于它的根結點的值；
3) 左、右子樹也分别為二叉排序樹；
4) 沒有鍵值相等的節點。
個人了解：整個樹結構的層次關系不是亂的，而是通過有效的排序，這樣大大提升了查找效率。
2.2平衡二叉樹（AVL）
因為我們在二叉樹中不停地插入元素後，可能就會導緻左邊或右邊某一邊子樹特别多，這樣的不平衡就會大大降低了二叉樹的查找效率，是以引入了平衡二叉樹。
平衡二叉樹定義：平衡二叉樹（Balanced Binary Tree）又被稱為AVL樹（有别于AVL算法），且具有以下性質：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。這個方案很好的解決了二叉查找樹退化成連結清單的問題，把插入，查找，删除的時間複雜度最好情況和最壞情況都維持在O(logN)。但是頻繁旋轉會使插入和删除犧牲掉O(logN)左右的時間，不過相對二叉查找樹來說，時間上穩定了很多。
2.2.1平衡二叉樹的調整
平衡因子：BF（Balance Factor） BF(T) = hL-hR(hL、hR分别代表左右子樹的高度)
2.3哈夫曼樹
哈夫曼樹是一種帶權路徑長度最短的二叉樹，也稱為最優二叉樹。
三、多路查找樹
大規模資料存儲中，實作索引查詢這樣一個實際背景下，樹節點存儲的元素數量是有限的（如果元素數量非常多的話，查找就退化成節點内部的線性查找了），這樣導緻二叉查找樹結構由于樹的深度過大而造成磁盤I/O讀寫過于頻繁，進而導緻查詢效率低下。
3.1 B樹
B樹（英語：B-tree）是一種自平衡的樹，能夠保持資料有序。這種資料結構能夠讓查找資料、順序通路、插入資料及删除的動作，都在對數時間内完成。B樹，概括來說是一個一般化的二叉查找樹（binary search tree），可以擁有最多2個子節點。與自平衡二叉查找樹不同，B樹适用于讀寫相對大的資料塊的存儲系統，例如磁盤。
1.根結點至少有兩個子女。
2.每個中間節點都包含k-1個元素和k個孩子，其中 m/2 <= k <= m
3.每一個葉子節點都包含k-1個元素，其中 m/2 <= k <= m
4.所有的葉子結點都位于同一層。
5.每個節點中的元素從小到大排列，節點當中k-1個元素正好是k個孩子包含的元素的值域分劃。
個人了解：相當于降低樹的高度，并且将同一層的結點合并，這樣就避免了同一層中結點數過多，查找變成了線性查找，提升查詢效率。