PS：為了更好的閱讀體驗，推薦閱讀原文，到我的博客中閱讀。
那麼有了線性結構，我們為什麼還需要非線性結構呢？ 答案是為了高效地兼顧靜態操作和動態操作。大家可以對照各種數據結構的各種操作的複雜度來直觀感受一下。
樹樹的應用同樣非常廣泛，小到文件系統，大到網際網路，組織架構等都可以表示為樹結構，而在我們前端眼中比較熟悉的 DOM 樹也是一種樹結構，而 HTML 作為一種 DSL 去描述這種樹結構的具體表現形式。如果你接觸過 AST，那麼 AST 也是一種樹，XML 也是樹結構。。。樹的應用遠比大多數人想像的要得多。
樹其實是一種特殊的圖，是一種無環連通圖，是一種極大無環圖，也是一種極小連通圖。
從另一個角度看，樹是一種遞歸的數據結構。而且樹的不同表示方法，比如不常用的長子 + 兄弟法，對於 你理解樹這種數據結構有著很大用處， 說是一種對樹的本質的更深刻的理解也不為過。
樹的基本算法有前中後序遍歷和層次遍歷，有的同學對前中後這三個分別具體表現的訪問順序比較模糊，其實當初我也是一樣的，後面我學到了一點，你只需要記住：所謂的前中後指的是根節點的位置，其他位置按照先左後右排列即可。比如前序遍歷就是根左右, 中序就是左根右，後序就是左右根， 很簡單吧？
我剛才提到了樹是一種遞歸的數據結構，因此樹的遍歷算法使用遞歸去完成非常簡單，幸運的是樹的算法基本上都要依賴於樹的遍歷。 但是遞歸在計算機中的性能一直都有問題，因此掌握不那麼容易理解的"命令式地迭代"遍歷算法在某些情況下是有用的。如果你使用迭代式方式去遍歷的話，可以藉助上面提到的棧來進行，可以極大減少代碼量。
如果使用棧來簡化運算，由於棧是 FILO 的，因此一定要注意左右子樹的推入順序。
樹的重要性質：
如果樹有 n 個頂點，那麼其就有 n - 1 條邊，這說明了樹的頂點數和邊數是同階的。任何一個節點到根節點存在唯一路徑, 路徑的長度為節點所處的深度實際使用的樹有可能會更複雜，比如使用在遊戲中的碰撞檢測可能會用到四叉樹或者八叉樹。以及 k 維的樹結構 k-d 樹等。
（圖片來自 https://zh.wikipedia.org/wiki/K-d%E6%A0%91）
二叉樹二叉樹是節點度數不超過二的樹，是樹的一種特殊子集，有趣的是二叉樹這種被限制的樹結構卻能夠表示和實現所有的樹， 它背後的原理正是長子 + 兄弟法，用鄧老師的話說就是二叉樹是多叉樹的特例，但在有根且有序時，其描述能力卻足以覆蓋後者。
實際上， 在你使用長子 + 兄弟法表示樹的同時，進行 45 度角旋轉即可。
一個典型的二叉樹：
標記為 7 的節點具有兩個子節點, 標記為 2 和 6; 一個父節點,標記為 2,作為根節點, 在頂部,沒有父節點。
(圖片來自 https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/tree/README.zh-CN.md)
對於一般的樹，我們通常會去遍歷，這裡又會有很多變種。
下面我列舉一些二叉樹遍歷的相關算法:
94.binary-tree-inorder-traversal102.binary-tree-level-order-traversal103.binary-tree-zigzag-level-order-traversal144.binary-tree-preorder-traversal145.binary-tree-postorder-traversal199.binary-tree-right-side-view相關概念：
真二叉樹 （所有節點的度數只能是偶數，即只能為 0 或者 2）另外我也專門開設了二叉樹的遍歷章節, 具體細節和算法可以去那裡查看。
堆堆其實是一種優先級隊列，在很多語言都有對應的內置數據結構，很遺憾 javascript 沒有這種原生的數據結構。 不過這對我們理解和運用不會有影響。
堆的特點：
在一個 最小堆(min heap) 中, 如果 P 是 C 的一個父級節點, 那麼 P 的 key(或 value)應小於或等於 C 的對應值. 正因為此，堆頂元素一定是最小的，我們會利用這個特點求最小值或者第 k 小的值。在一個 最大堆(max heap) 中, P 的 key(或 value)大於 C 的對應值。需要注意的是優先隊列不僅有堆一種，還有更複雜的，但是通常來說，我們會把兩者做等價。
相關算法：
295.find-median-from-data-stream二叉查找樹二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹。
二叉查找樹具有下列性質的二叉樹：
若左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；若右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；對於一個二叉查找樹，常規操作有插入，查找，刪除，找父節點，求最大值，求最小值。
二叉查找樹，之所以叫查找樹就是因為其非常適合查找，舉個例子， 如下一顆二叉查找樹，我們想找節點值小於且最接近 58 的節點，搜索的流程如圖所示：
（圖片來自 https://www.geeksforgeeks.org/floor-in-binary-search-tree-bst/）
另外我們二叉查找樹有一個性質是： 其中序遍歷的結果是一個有序數組。 有時候我們可以利用到這個性質。
相關題目：
98.validate-binary-search-tree二叉平衡樹平衡樹是計算機科學中的一類數據結構，為改進的二叉查找樹。一般的二叉查找樹的查詢複雜度取決於目標結點到樹根的距離（即深度），因此當結點的深度普遍較大時，查詢的均攤複雜度會上升。為了實現更高效的查詢，產生了平衡樹。
在這裡，平衡指所有葉子的深度趨於平衡，更廣義的是指在樹上所有可能查找的均攤複雜度偏低。
一些資料庫引擎內部就是用的這種數據結構，其目標也是將查詢的操作降低到 logn（樹的深度），可以簡單理解為樹在數據結構層面構造了二分查找算法。
基本操作：
AVL是最早被發明的自平衡二叉查找樹。在 AVL 樹中，任一節點對應的兩棵子樹的最大高度差為 1，因此它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下的時間複雜度都是 {\displaystyle O(\log {n})} O(\log{n})。增加和刪除元素的操作則可能需要藉由一次或多次樹旋轉，以實現樹的重新平衡。AVL 樹得名於它的發明者 G. M. Adelson-Velsky 和 Evgenii Landis，他們在 1962 年的論文 An algorithm for the organization of information 中公開了這一數據結構。 節點的平衡因子是它的左子樹的高度減去它的右子樹的高度（有時相反）。帶有平衡因子 1、0 或 -1 的節點被認為是平衡的。帶有平衡因子 -2 或 2 的節點被認為是不平衡的，並需要重新平衡這個樹。平衡因子可以直接存儲在每個節點中，或從可能存儲在節點中的子樹高度計算出來。
紅黑樹在 1972 年由魯道夫·貝爾發明，被稱為"對稱二叉 B 樹"，它現代的名字源於 Leo J. Guibas 和 Robert Sedgewick 於 1978 年寫的一篇論文。紅黑樹的結構複雜，但它的操作有著良好的最壞情況運行時間，並且在實踐中高效：它可以在 {\displaystyle O(\log {n})} O(\log{n})時間內完成查找，插入和刪除，這裡的 n 是樹中元素的數目
字典樹(前綴樹)又稱 Trie 樹，是一種樹形結構。典型應用是用於統計，排序和保存大量的字符串（但不僅限於字符串），所以經常被搜尋引擎系統用於文本詞頻統計。它的優點是：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。
(圖來自 https://baike.baidu.com/item/%E5%AD%97%E5%85%B8%E6%A0%91/9825209?fr=aladdin) 它有 3 個基本性質：
根節點不包含字符，除根節點外每一個節點都只包含一個字符；從根節點到某一節點，路徑上經過的字符連接起來，為該節點對應的字符串；immutable 與 字典樹immutableJS的底層就是share + tree. 這樣看的話，其實和字典樹是一致的。
相關算法：
208.implement-trie-prefix-tree圖前面講的數據結構都可以看成是圖的特例。 前面提到了二叉樹完全可以實現其他樹結構， 其實有向圖也完全可以實現無向圖和混合圖，因此有向圖的研究一直是重點考察對象。
圖論〔Graph Theory〕是數學的一個分支。它以圖為研究對象。圖論中的圖是由若干給定的點及連接兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關係，用點代表事物，用連接兩點的線表示相應兩個事物間具有這種關係。
圖的表示方法空間複雜度 O(n^2),n 為頂點個數。
優點：
判斷兩個頂點是否連接，獲取入度和出度以及更新度數，時間複雜度都是 O(1)
對於每個點，存儲著一個鍊表，用來指向所有與該點直接相連的點 對於有權圖來說，鍊表中元素值對應著權重
例如在無向無權圖中：
（圖片來自 https://zhuanlan.zhihu.com/p/25498681）
可以看出在無向圖中，鄰接矩陣關於對角線對稱，而鄰接鍊表總有兩條對稱的邊 而在有向無權圖中：
（圖片來自 https://zhuanlan.zhihu.com/p/25498681）
圖的遍歷圖的遍歷就是要找出圖中所有的點，一般有以下兩種方法：
深度優先遍歷：(Depth First Search, DFS)深度優先遍歷圖的方法是，從圖中某頂點 v 出發， 不斷訪問鄰居， 鄰居的鄰居直到訪問完畢。
廣度優先搜索：(Breadth First Search, BFS)廣度優先搜索，可以被形象地描述為 "淺嘗輒止"，它也需要一個隊列以保持遍歷過的頂點順序，以便按出隊的順序再去訪問這些頂點的鄰接頂點。
----完-
相關閱讀：數據結構快速盤點 - 線性結構