## 樹的概念 樹（英語：tree）是一種抽象數據類型（ADT）或是實作這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。它是由n（n>=1）個有限節點組成一個具有層次關系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點： * 每個節點有零個或多個子節點； * 沒有父節點的節點稱為根節點； * 每一個非根節點有且只有一個父節點； * 除了根節點外，每個子節點可以分為多個不相交的子樹； 比如說：   ## 樹的術語 * 節點的度：一個節點含有的子樹的個數稱為該節點的度； * 樹的度：一棵樹中，最大的節點的度稱為樹的度； * 葉節點或終端節點：度為零的節點； * 父親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點； * 孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點； * 兄弟節點：具有相同父節點的節點互稱為兄弟節點； * 節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推； * 樹的高度或深度：樹中節點的最大層次； * 堂兄弟節點：父節點在同一層的節點互為堂兄弟； * 節點的祖先：從根到該節點所經分支上的所有節點； * 子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。 * 森林：由m（m>=0）棵互不相交的樹的集合稱為森林； ## 樹的種類 * **無序樹**：樹中任意節點的子節點之間沒有順序關系，這種樹稱為無序樹，也稱為自由樹； * **有序樹**：樹中任意節點的子節點之間有順序關系，這種樹稱為有序樹； * **二叉樹**：每個節點最多含有兩個子樹的樹稱為二叉樹； * **完全二叉樹**：對于一顆二叉樹，假設其深度為d(d>1)。除了第d層外，其它各層的節點數目均已達最大值，且第d層所有節點從左向右連續地緊密排列，這樣的二叉樹被稱為完全二叉樹，其中滿二叉樹的定義是所有葉節點都在最底層的完全二叉樹; * **平衡二叉樹（AVL樹）**：當且僅當任何節點的兩棵子樹的高度差不大于1的二叉樹； * **排序二叉樹**（二叉查找樹（英語：Binary Search Tree），也稱二叉搜索樹、有序二叉樹）； * **霍夫曼樹**（用于信息編碼）：帶權路徑最短的二叉樹稱為哈夫曼樹或最優二叉樹； * **B樹**：一種對讀寫操作進行優化的自平衡的二叉查找樹，能夠保持數據有序，擁有多余兩個子樹。 ## 樹的存儲與表示 **順序存儲**：將數據結構存儲在固定的數組中，然在遍歷速度上有一定的優勢，但因所占空間比較大，是非主流二叉樹。二叉樹通常以鏈式存儲。  **鏈式存儲：**  由于對節點的個數無法掌握，常見樹的存儲表示都轉換成二叉樹進行處理，子節點個數最多為2 ## 常見的一些樹的應用場景 1. xml，html等，那么編寫這些東西的解析器的時候，不可避免用到樹 2. 路由協議就是使用了樹的算法 3. mysql數據庫索引 4. 文件系統的目錄結構 5. 所以很多經典的AI算法其實都是樹搜索，此外機器學習中的decision tree也是樹結構