第 5 章　树与二叉树

5.1　树的基本概念与术语

5.1.1 基本术语：度、深度、高度、有序性

5.1.2 核心性质：结点数 = 度数之和 + 1

5.2　二叉树的概念与性质 高频考点

5.2.1 定义、五种形态与「度为 2 的树」之别

5.2.2 四条基本性质（第 ③ 条每年都考）

5.2.3 满二叉树与完全二叉树辨析

5.2.4 完全二叉树的下标关系与高度公式

5.3　二叉树的存储与遍历 高频考点

5.3.1 顺序存储与二叉链表

// 二叉链表存储结构（本章所有代码基于它）

typedef struct BiTNode {
    ElemType data;                      // 数据域
    struct BiTNode *lchild, *rchild;    // 左、右孩子指针
} BiTNode, *BiTree;

5.3.2 先序 / 中序 / 后序 / 层序遍历

设访问根记 N、遍历左 / 右子树记 L / R：先序（先根）NLR、中序 LNR、后序 LRN；层序按层次自上而下、同层自左向右访问。

// 三种深度优先遍历：只有 visit 的位置在移动（递归框架完全相同）

void PreOrder(BiTree t) {           // 先序 NLR
    if (t != NULL) {
        visit(t);                   // ① 第一次经过就访问
        PreOrder(t->lchild);
        PreOrder(t->rchild);
    }
}

void InOrder(BiTree t) {            // 中序 LNR
    if (t != NULL) {
        InOrder(t->lchild);
        visit(t);                   // ② 第二次经过（左子树回来时）才访问
        InOrder(t->rchild);
    }
}

void PostOrder(BiTree t) {          // 后序 LRN：把 visit 移到两次递归之后即 ③
    if (t != NULL) {
        PostOrder(t->lchild);
        PostOrder(t->rchild);
        visit(t);                   // ③ 第三次经过（离开之前）才访问
    }
}

5.3.3 中序非递归（栈）与层序（队列）

// 中序非递归：沿左链一路入栈，走不动就弹栈访问，再转右子树

void InOrder2(BiTree t) {
    BiTree stk[MAXSIZE]; int top = -1;   // 顺序栈，存「待回访」结点
    BiTree p = t;
    while (p != NULL || top != -1) {
        if (p != NULL) {                 // 情形一：还有左路可走
            stk[++top] = p;              // 入栈，继续向左
            p = p->lchild;
        } else {                         // 情形二：左边走完
            p = stk[top--];              // 弹栈并访问
            visit(p);
            p = p->rchild;               // 转向右子树（可能为空）
        }
    }
}

// 层序遍历：队列——出队一个就访问，再把它的孩子从左到右入队

void LevelOrder(BiTree t) {
    BiTree q[MAXSIZE]; int front = 0, rear = 0;   // 手写顺序队列
    if (t != NULL) q[rear++] = t;
    while (front != rear) {
        BiTree p = q[front++];                    // 出队
        visit(p);
        if (p->lchild != NULL) q[rear++] = p->lchild;
        if (p->rchild != NULL) q[rear++] = p->rchild;
    }
}

5.3.4 遍历序列重建二叉树 大题模板

5.3.5 遍历的应用：深度 / 叶子 / 交换 / 宽度

// 三道经典递归：先解决空树，再「问左右子树要答案」——大题算法题的万能骨架

int Depth(BiTree t) {                  // 求深度（高度）
    if (t == NULL) return 0;          // 空树深度为 0
    int l = Depth(t->lchild);
    int r = Depth(t->rchild);
    return (l > r ? l : r) + 1;       // 取更深的子树，加上本层
}                                     // T=O(n), S=O(h)
int LeafCount(BiTree t) {             // 统计叶子数
    if (t == NULL) return 0;
    if (t->lchild == NULL && t->rchild == NULL)
        return 1;                     // 度为 0 才算叶子
    return LeafCount(t->lchild) + LeafCount(t->rchild);
}                                     // T=O(n), S=O(h)
void SwapTree(BiTree t) {             // 交换每个结点的左右子树
    if (t != NULL) {
        BiTree tmp = t->lchild;
        t->lchild = t->rchild;
        t->rchild = tmp;
        SwapTree(t->lchild);          // 递归处理交换后的两棵子树
        SwapTree(t->rchild);
    }
}                                     // T=O(n), S=O(h)

int Width(BiTree t) {                 // 层序 + 按层计数
    if (t == NULL) return 0;
    BiTree q[MAXSIZE]; int front = 0, rear = 0;
    q[rear++] = t;
    int width = 1;
    while (front != rear) {
        int cnt = rear - front;       // 当前队列全部结点 = 本层结点数
        if (cnt > width) width = cnt;
        for (int i = 0; i < cnt; i++) {   // 本层整体出队
            BiTree p = q[front++];
            if (p->lchild != NULL) q[rear++] = p->lchild;
            if (p->rchild != NULL) q[rear++] = p->rchild;
        }
    }
    return width;                     // T=O(n), S=O(w)（w 为宽度）
}

5.4　线索二叉树

5.4.1 中序线索化：利用 n+1 个空链域

// 线索存储结构 + 中序线索化（递归框架与中序遍历完全同构）

typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;                    // 0：孩子；1：线索
} ThreadNode, *ThreadTree;

ThreadTree pre = NULL;                 // 全局：刚访问完的结点（前驱）
void InThread(ThreadTree p) {
    if (p != NULL) {
        InThread(p->lchild);           // ① 线索化左子树
        if (p->lchild == NULL) {       // ② 左空 → 指向中序前驱
            p->ltag = 1;
            p->lchild = pre;
        }
        if (pre != NULL && pre->rchild == NULL) {
            pre->rtag = 1;             // ③ 前驱右空 → 前驱的后继是我
            pre->rchild = p;
        }
        pre = p;                       // ④ 滚动更新前驱
        InThread(p->rchild);           // ⑤ 线索化右子树
    }
}

5.4.2 线索树上找中序后继

5.5　树、森林与二叉树的转换

5.5.1 孩子兄弟表示法与转换规则

// 树的孩子兄弟存储

typedef struct CSNode {
    ElemType data;
    struct CSNode *firstchild, *nextsibling;   // 长子 + 右兄弟
} CSNode, *CSTree;

5.5.2 遍历对应关系表 必背

5.6　哈夫曼树与并查集 高频考点

5.6.1 WPL 与哈夫曼树的构造

5.6.2 哈夫曼编码（前缀码）

5.6.3 并查集

// 并查集：Find 与 Union

#define SIZE 100
int S[SIZE];                          // S[i]：双亲下标；根为 -1
                                      // 初始化：令每个 S[i] = -1（各自成集合）
int Find(int S[], int x) {            // 返回 x 所在集合的根
    while (S[x] >= 0)
        x = S[x];                     // 沿双亲指针一路向上
    return x;                         // T=O(树高)
}

void Union(int S[], int Root1, int Root2) {   // 两根必须是不同集合
    if (Root1 == Root2) return;       // 同一集合不能自并
    S[Root2] = Root1;                 // 把 Root2 树挂在 Root1 下
}

5.7　章末自测 真题风格

限时 60 分钟，先做后看答案。难度：★★ 基础 / ★★★ 强化 / ★★★★ 冲刺。所有计数题请养成「代小例验算」的习惯再收笔。

int IsComplete(BiTree t) {
    if (t == NULL) return 1;           // 约定空树视为完全
    BiTree q[MAXSIZE]; int front = 0, rear = 0;
    q[rear++] = t;
    int seenNull = 0;
    while (front != rear) {
        BiTree p = q[front++];
        if (p == NULL)
            seenNull = 1;              // 记录：出过一个空指针
        else {
            if (seenNull) return 0;    // 空之后再出非空 → 有洞
            q[rear++] = p->lchild;     // 空指针照样入队
            q[rear++] = p->rchild;
        }
    }
    return 1;                          // T=O(n), S=O(n)
}

5.8　本章考点总结