數據結構第六章：樹與二叉樹核心知識體系

樹的定義與基本術語

樹是 n (n≥0) 個節點的有限集。n=0 為空樹。非空樹滿足：① 唯一根節點 ② 其餘節點可分 m 個互不相交子樹，各自又是樹。

關鍵術語

樹的存儲結構

• 雙親表示法：數組存儲，每節點含 data + parent 下標，根 parent=-1
• 孩子表示法：節點指向孩子鏈表
• 孩子兄弟表示法：左孩子 + 右兄弟指針，轉為二叉樹存儲

二叉樹定義與特殊形態

定義：n 個節點有限集，或為空，或由根 + 左右兩棵互不相交二叉樹組成。
特點：① 每節點最多兩子樹 ② 左右有序 ③ 單子樹必區分左右。

特殊二叉樹

• 斜樹：全左或全右，退化為鏈表
• 滿二叉樹：深度 k 有 2ᵏ-1 節點，所有葉同層
• 完全二叉樹：前 k-1 滿，第 k 層靠左連續

二叉樹五大性質

1. 第 i 層最多 2ⁱ⁻¹ 節點
2. 深度 k 最多 2ᵏ-1 節點
3. n₀ = n₂ + 1（葉節點 = 度為2節點 + 1）
4. n 節點完全二叉樹深度 = ⌊log₂n⌋ + 1
5. 完全二叉樹按層序編號 i：父⌊i/2⌋，左子 2i，右子 2i+1

二叉樹存儲

• 順序存儲：適合完全二叉樹，非完全需留空位，浪費空間
• 二叉鏈表：data + lchild + rchild，通用標準結構

四種遍歷算法（遞歸實現）

typedef struct BitNode {
    char data;
    struct BitNode *lchild, *rchild;
} BitNode, *BitTree;

// 1. 前序：根 → 左 → 右
void PreOrder(BitTree T) {
    if (!T) return;
    putchar(T->data);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
}

// 2. 中序：左 → 根 → 右
void InOrder(BitTree T) {
    if (!T) return;
    InOrder(T->lchild);
    putchar(T->data);
    InOrder(T->rchild);
}

// 3. 後序：左 → 右 → 根
void PostOrder(BitTree T) {
    if (!T) return;
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    putchar(T->data);
}

// 4. 層次：隊列 BFS
void LevelOrder(BitTree T) {
    queue q; q.push(T);
    while (!q.empty()) {
        BitTree p = q.front(); q.pop();
        putchar(p->data);
        if (p->lchild) q.push(p->lchild);
        if (p->rchild) q.push(p->rchild);
    }
}

遍歷序列與樹的唯一確定性

• 前序 + 中序 → 唯一確定
• 後序 + 中序 → 唯一確定
• 前序 + 後序 → 不能 唯一確定

二叉樹構建（擴展二叉樹前序序列）

void CreateBitTree(BitTree *T) {
    char ch; scanf("%c", &ch);
    if (ch == '#') *T = NULL;
    else {
        *T = (BitTree)malloc(sizeof(BitNode));
        (*T)->data = ch;
        CreateBitTree(&(*T)->lchild);
        CreateBitTree(&(*T)->rchild);
    }
}
// 輸入示例：AB#D##C##  （# 代表空節點）

線索二叉樹

利用 n+1 個空指針域存儲前驅/後繼：
ltag=1 → lchild 指向前驅；ltag=0 → 指向左孩子
rtag=1 → rchild 指向後繼；rtag=0 → 指向右孩子
實現 O(1) 找前驅後繼，適合頻繁遍歷場景。

掌握以上知識點，可覆蓋數據結構考研、面試、工程應用中 95% 的樹與二叉樹考點。