一、樹的基本概念

樹是一種非線性數據結構，由n（n≥0）個節點組成，類比現實中的樹，包含根、枝幹和葉子。當n=0時為空樹；n≥1時，有且僅有一個根節點（無父節點），其餘節點可分為若干個互不相交的子集，每個子集都是一棵獨立的子樹。樹的核心術語包括：父節點（直接上層節點）、子節點（直接下層節點）、兄弟節點（同一父節點的子節點）、葉子節點（無子女的節點）、節點的度（子節點個數）、樹的深度（從根到最遠葉子的層數，根為第1層）、樹的高度（從葉子到根的最大層數）、路徑（從根到某節點的節點序列）。

二、樹的核心特性

1. 根節點唯一，無父節點，其餘節點有且僅有一個父節點；

2. 節點間通過父子關係連接，不存在環路（否則為圖結構）；

3. 樹的子樹互不相交，任意兩個節點間有且僅有一條路徑；

4. 樹的層次結構體現了“一對多”的邏輯關係，區別於線性結構的“一對一”。

三、常見樹的類型

1. 二叉樹（最常用）

每個節點最多有兩個子節點，分別稱為左子樹和右子樹，子樹有左右順序之分（不可交換）。二叉樹的特殊形態包括：

• 滿二叉樹：除葉子節點外，每個節點都有兩個子節點，且葉子節點在同一層；

• 完全二叉樹：按層序遍歷（從上到下、從左到右）填充節點，除最後一層外，每一層節點數均為最大值，最後一層節點集中在左側（右側可空缺）；

• 斜樹：所有節點都只有左子樹（左斜樹）或右子樹（右斜樹），本質等同於線性結構。

2. 其他常見樹

• 二叉搜索樹（BST）：左子樹所有節點值＜根節點值，右子樹所有節點值＞根節點值，支持高效的查找、插入、刪除操作（理想情況時間複雜度O(logn)）；

• 平衡二叉樹（AVL樹）：二叉搜索樹的優化版，任意節點的左右子樹高度差絕對值≤1，避免斜樹導致的O(n)複雜度；

• 紅黑樹：一種自平衡二叉搜索樹，通過顏色規則（紅/黑節點）維持平衡，插入刪除效率高於AVL樹，常用於Java的TreeMap、C++的std::map；

• 多叉樹：節點可以有多個子節點，典型例子是B樹（多路平衡查找樹），常用於數據庫索引；

• 哈夫曼樹（最優二叉樹）：帶權路徑長度最短的二叉樹，用於哈夫曼編碼（數據壓縮）。

四、樹的遍歷方式（以二叉樹為例）

遍歷核心是按一定順序訪問所有節點，二叉樹有四種基礎遍歷方式，均基於遞歸或迭代實現：

1. 前序遍歷（根-左-右）：先訪問根節點，再遞歸遍歷左子樹，最後遞歸遍歷右子樹；

2. 中序遍歷（左-根-右）：先遞歸遍歷左子樹，再訪問根節點，最後遞歸遍歷右子樹（二叉搜索樹的中序遍歷結果為有序序列）；

3. 後序遍歷（左-右-根）：先遞歸遍歷左子樹，再遞歸遍歷右子樹，最後訪問根節點；

4. 層序遍歷（廣度優先）：按樹的層次從上到下、同一層從左到右依次訪問節點，需藉助隊列實現。

五、樹的應用場景

• 數據存儲與檢索：二叉搜索樹、紅黑樹、B樹用於高效查找（如數據庫索引、集合框架）；

• 層級關係表示：文件系統（目錄樹）、組織架構圖、XML/HTML文檔結構；

• 算法優化：哈夫曼編碼（數據壓縮）、決策樹（機器學習）、廣度優先搜索（BFS）/深度優先搜索（DFS）的底層結構；

• 其他：前綴樹（字典樹，用於字符串匹配）、線段樹（區間查詢與更新）。