數據結構基礎：樹與二叉樹核心概念、術語與基本操作詳解

數據結構基礎：樹與二叉樹核心概念、術語與基本操作詳解

樹型結構是非線性數據結構的核心，廣泛應用於文件系統、數據庫索引（B+ 樹）、編譯器語法樹、網絡路由等場景。本文系統梳理樹的定義、核心術語、性質、存儲結構及基本操作 ADT，為後續二叉樹、平衡樹、B 樹等進階主題打下基礎。

一、 樹的嚴格定義

樹 是 n (n ≥ 0) 個節點的有限集合。當 n = 0 時稱空樹。任意非空樹滿足：

1. 有且僅有一個根節點；
2. 其餘節點可分為 m (m > 0) 個互不相交的有限集合 T₁, T₂, ..., Tₘ，每個集合本身又是一棵樹，稱為根的子樹；
3. 遞歸定義體現了樹的分層、分支本質。

二、 核心術語圖解

以圖中樹為例：

三、 樹的抽象數據類型 (ADT)

ADT Tree {
  數據對象: 節點集合
  數據關係: 父子層次關係
  基本操作:
    InitTree(&T)           // 構造空樹
    DestroyTree(&T)        // 銷毀樹
    CreateTree(&T, def)    // 按定義構造樹
    ClearTree(&T)          // 清空為空樹
    TreeEmpty(T)           // 判空
    TreeDepth(T)           // 返回深度
    Root(T)                // 返回根節點
    Value(T, e)            // 返回節點 e 的值
    Assign(T, e, value)    // 賦值
    Parent(T, e)           // 返回雙親，根返回 NULL
    LeftChild(T, e)        // 返回最左孩子，葉子返回 NULL
    RightSibling(T, e)     // 返回右兄弟，無則 NULL
    InsertChild(&T, &p, i, c) // 插入 c 為 p 的第 i 棵子樹
    DeleteChild(&T, &p, i)    // 刪除 p 的第 i 棵子樹
    TraverseTree(T, Visit)    // 遍歷（先序/後序/層序等）
}

四、 樹的存儲結構

1. 雙親表示法：數組存節點，每節點記錄 parent 索引。查父 O(1)，查子 O(n)。
2. 孩子表示法：每節點維護單鏈表存孩子指針。查子方便，查父需掃描。
3. 孩子兄弟表示法（二叉樹表示法）：最通用。每節點兩指針：firstChild 指向長子，nextSibling 指向右兄弟。任意樹可唯一轉換為二叉樹，統一操作邏輯。

// 孩子兄弟表示法節點結構
typedef struct CSNode {
    ElemType data;
    struct CSNode *firstChild, *nextSibling;
} CSNode, *CSTree;

五、 樹的遍歷

• 先序遍歷：根 → 依次遍歷各子樹（等價於二叉樹先序）。
• 後序遍歷：依次遍歷各子樹 → 根（等價於二叉樹中序）。
• 層序遍歷：借隊列逐層訪問。

注意：樹無「中序遍歷」概念，因無左右子樹之分。

六、 森林與二叉樹的轉換

1. 森林 → 二叉樹：各樹內部「長子為左、右兄弟為右」；再將各樹根用右鏈表串聯。
2. 二叉樹 → 森林：刪除根的右孩子鏈，還原「左孩子→長子，右孩子→右兄弟」。
3. 遍歷對應：森林先序 = 二叉樹先序；森林後序 = 二叉樹中序。

七、 經典應用場景

• 文件系統目錄結構（樹）
• 組織架構/部門層級（樹）
• HTML/XML DOM 樹
• 字典查找/自動補全
• 決策樹/遊戲 AI（Minimax、Alpha-Beta 剪枝）

八、 學習路線建議

1. 掌握術語與 ADT →
2. 理解孩子兄弟表示法並能手寫轉換代碼 →
3. 熟練三種遍歷遞歸/非遞歸實現 →
4. 進階：二叉搜索樹 (BST) → AVL/紅黑樹 → B/B+ 樹 → Trie 字典樹 → 堆/優先隊列。

樹是演算法與系統設計的基石，深入理解其結構特性與轉換關係，能讓你在面對層次化、遞歸化問題時游刃有餘。