#树与二叉树

#考点定位

• 所属大纲章节：树的基本概念；二叉树的定义、性质与存储；二叉树的遍历；线索二叉树；树和森林；树与二叉树的应用（哈夫曼树、并查集）
• 常见题型：选择题（性质计算、遍历序列、树/森林/二叉树转换、哈夫曼、并查集复杂度）；算法设计题（遍历框架上的变形：WPL、层序变形、路径类）
• 考查频率：极高。树一章常年占据 408 数据结构分值的三分之一上下，且是算法设计题最大题源（WPL、层序变形、叶子输出、深度计算均为历年反复考查的模板）

工程直觉迁移：工程里的树遍历就是递归下降，你天天写，不必从零学。本节篇幅全部留给考试特有产物：非递归手写规范、遍历序列互推、树/森林/二叉树三者机械转换、并查集复杂度结论——这些工程中几乎不存在，全是应试技巧。

#一、二叉树性质：计算题套路

#常数级结论速查

#$$：30 秒推导与三种变形

推导（边数两头数）：结点总数 $$。除根外每个结点恰有一条入边，故边数 $$；又每条边出自一个度为 1 或 2 的结点，$$。联立：

三种变形考法：

1. 直接给 $$ 求 $$：代公式。
2. 完全二叉树给总结点数 $$ 求叶子：完全二叉树的 $$ 只能是 0 或 1（奇数层排列决定了至多一个独子结点）。由 $$：$$ 为奇数时 $$，$$；$$ 为偶数时 $$，$$。合并记忆：$$。
3. 与编号联动：$$ 个结点的完全二叉树中，编号 $$ 的结点全是叶子；编号 $$ 的结点当 $$ 为偶数时只有左孩子（左孩子恰为 $$ 号），$$ 为奇数时有两个孩子。

例 1（模拟题）：某完全二叉树共有 1001 个结点，则叶结点个数为（ ）

A. 500 B. 501 C. 502 D. 无法确定

解答：$$ 为奇数 → $$ → $$，选 B。自检：$$，$$ 成立。错因提醒：套用 $$ 时要能说清"为什么 $$ 只能是 0 或 1"，否则大题证明类小问会丢分。

例 2（模拟题）：100 个结点的完全二叉树，其高度为（ ），编号为 50 的结点（ ）

A. 7；有两个孩子 B. 7；只有左孩子 C. 6；只有右孩子 D. 7；是叶子

解答：高度 $$。$$ 是最后一个分支结点；左孩子 $$（存在），右孩子 $$（不存在），故只有左孩子，选 B。错因提醒：高度公式两个形态（$$ 与 $$）值恒等，用 $$ 复核最稳。

#高度与结点数双向推算

高度为 $$ 的完全二叉树结点范围：$$。叶子数范围：$$（$$；下界对应 $$ 时：第 $$ 层仅 1 叶，第 $$ 层有 $$ 个叶）。这类"至少/至多"题用两个极端形态（只挂一个左孩子 vs 满二叉树）现场推，不要背区间。

#二、遍历：递归、非递归与序列互推

样例树（后续所有演示共用）：

四种遍历结果（先背下来对照所有演示）：

#非递归先序与中序：同一模板，访问时机不同（待动画化）

void InOrder(BTNode *t) {          // 先序版：把 visit 挪到 push 之前即可
    InitStack(S);
    BTNode *p = t;
    while (p || !IsEmpty(S)) {     // p 非空：有左路可走；栈非空：还有人没回访
        if (p) {
            // visit(p);          // 先序在此访问
            Push(S, p);
            p = p->lchild;        // 一路向左压栈
        } else {
            Pop(S, p);
            visit(p);             // 中序在此访问：左子树已处理完
            p = p->rchild;        // 转向右子树
        }
    }
}

中序遍历样例树的分步栈状态表（栈内容从底到顶书写）：

规律：出栈序 = 中序序。选择题问"某时刻栈中内容"，按此表机械模拟，不要凭感觉。

#非递归后序：last 指针法（待动画化）

后序的难点：结点第一次回到栈顶时还不能访问（右子树未处理），需借助指向前一个刚访问结点的指针 r 判断右子树是否已完成：

void PostOrder(BTNode *t) {
    BTNode *p = t, *r = NULL;
    while (p || !IsEmpty(S)) {
        if (p) { Push(S, p); p = p->lchild; }        // 阶段1：一路向左
        else {
            GetTop(S, p);                             // 窥视，不出栈
            if (p->rchild && p->rchild != r)          // 右子树存在且未访问过
                p = p->rchild;                        //   → 转向右子树（不入栈先走）
            else {                                    // 无右子树或右子树刚访问完
                Pop(S, p); visit(p);
                r = p;                                // r 记录最近访问的结点
                p = NULL;                             // 强制下一轮走 else 分支回看栈顶
            }
        }
    }
}

关键陷阱：r != p->rchild 防止右子树访问完后回到同一栈顶时把右子树再走一遍（死循环/重复访问）。选择题爱问"后序非递归中结点出栈次数"——可能多次窥视，但每个结点只成功出栈一次。

#层序遍历：队列

void LevelOrder(BTNode *t) {
    if (!t) return;
    EnQueue(Q, t);
    while (!IsEmpty(Q)) {
        DeQueue(Q, p); visit(p);
        if (p->lchild) EnQueue(Q, p->lchild);
        if (p->rchild) EnQueue(Q, p->rchild);
    }
}

#由先序 + 中序重建二叉树（分步）

原理：先序首元素是根；在中序中定位根，左边全属左子树、右边全属右子树；两段长度切分先序剩余部分，递归下去。

以先序 A B D E C F、中序 D B E A C F 为例：

重建结果即样例树，后序为 D E B F C A。

#遍历序列互推可行性表（高频选择）

例 3（模拟题）：先序序列为 A B、后序序列为 B A 的二叉树（ ）

A. 只能是 A 的左孩子为 B B. 只能是 A 的右孩子为 B C. 两种都有可能 D. 不存在这样的二叉树

解答：先序 AB 说明 A 是根且 B 是 A 的孩子；后序 BA 同样；但 B 是左是右无法判定，选 C。这就是"先序+后序不能唯一确定"的最小反例，记住它可秒杀此类题。

#三、线索二叉树

#指针变化规则

$$ 个结点的二叉链表有 $$ 个指针域，其中 $$ 个为空（边只有 $$ 条）。线索化把这 $$ 个空链域改存遍历序下的前驱/后继指针（即"线索"），并增设两个标志域区分：

恒等式（选择题速答）：线索数 = 空链域数 = $$。头结点技巧（严版教材）：加一个头结点，中序首结点前驱与末结点后继都指向头结点，构成双向循环线索链表——题面画图判断时注意有没有这个头结点。

#中序线索链表的遍历

不依赖栈和递归，两个原语走全程：

BTNode *First(BTNode *t) {              // 中序第一个 = 最左下结点
    while (t->ltag == 0) t = t->lchild;
    return t;
}
BTNode *Next(BTNode *p) {               // p 的中序后继
    if (p->rtag == 1) return p->rchild; // 线索直接给后继
    return First(p->rchild);            // 否则 = 右子树最左下结点
}

核心规则（必背）：求结点 $$ 的中序后继——$$ 无右孩子（rtag=1）时后继就是 rchild 线索；有右孩子时后继是右子树中最左下的结点（一路向左到底）。

#先序/后序线索的方向不对称性

选择题常以"在 XX 线索树中找 XX 前驱/后继不需要从根出发/不需要栈"设坑：记住中序两个方向都容易，先序后继、后序前驱容易，另两个方向难。

#四、树与森林

#三种存储结构对比

#树 → 二叉树：三步机械操作（分步图）

以一棵根 R 有孩子 A、B、C（A 有孩子 X、Y）的树为例：

第 1 步连兄弟：同一双亲的相邻兄弟之间加虚线（A—B、B—C、X—Y）。

第 2 步断余线：每个结点只保留与第一个孩子的连线，抹去与其余孩子的连线（R 只留 R—A，抹 R—B、R—C；A 只留 A—X，抹 A—Y）。

第 3 步摆正：原树连线（双亲—长子）拉为左孩子，兄弟虚线拉为右孩子：

实线为左孩子指针，虚线为右兄弟指针——这棵二叉链表树就是转换结果。关键结论：树的根结点没有右兄弟，转换后二叉树的根一定没有右子树（判断"某二叉树是否可能由树转换而来"就看这条）。

#森林 ↔ 二叉树

森林 → 二叉树：先把每棵树各自转为二叉树（根均无右子树），再把第 2 棵作为第 1 棵根的右子树、第 3 棵挂到第 2 棵根的右子树……即各树的根沿右链串成一串。

二叉树 → 森林：去掉根的右链，右链上每个结点连同其左子树拆成独立树，再各自逆转换。

推论：森林中第 $$ 棵树的全部结点，转换后位于二叉树根的右链上第 $$ 个结点的左子树及自身。

#遍历对应关系表（高频选择，必背）

记忆锚点：二叉树的"后序"在树/森林体系里没有对应物；树/森林一侧凡是"后根/中序"都落到二叉树"中序"。命题陷阱正是在此：给森林先序序列问对应二叉树什么遍历——答先序；给森林"后序"序列问——答中序，不然后序。

例 4（模拟题）：设森林 F 转换为二叉树 B，则 F 的先序遍历序列与 B 的（ ）遍历序列相同，F 的中序遍历序列与 B 的（ ）遍历序列相同

A. 先序；中序 B. 先序；后序 C. 中序；先序 D. 后序；中序

解答：选 A。错因提醒：第二空是全题陷阱位，"森林的中序"对应"二叉树的中序"，与"二叉树后序"无关。

#五、哈夫曼树与哈夫曼编码

#概念与 WPL

带权路径长度：$$（$$ 叶结点权值，$$ 叶到根的路径长度）。哈夫曼树 = WPL 最小的二叉树（同样权集下）。

#构造过程（分步表）

反复从森林中取权值最小的两棵树合并为新树（新树权 = 两者之和），直到只剩一棵。以权集 {1, 2, 3, 4, 5}（模拟题）：

形态：根 15 的左子为 6（6 的左子为叶 3、右子为 3'（叶 1、叶 2）），右子为 9（叶 4、叶 5）。

WPL 计算（逐叶）：$$。

自检捷径：WPL = 所有非叶（合并新产生）结点权值之和 = $$，两条路对上才放心交卷。

#性质清单

1. $$ 个叶结点的哈夫曼树共 $$ 个结点（每次合并净增 1 个结点，共合并 $$ 次）。
2. 不存在度为 1 的结点（每次合并恰好两棵）。
3. 权值越大的叶离根越近；同权集下哈夫曼树形态不唯一（最小两棵同权时选取任意），但 WPL 唯一且最小。
4. 哈夫曼树是严格二叉树（每个非叶结点度均为 2）。因此"先序 + 后序可唯一确定哈夫曼树"。

#哈夫曼编码与前缀码判定

编码规则：左分支记 0、右分支记 1（或反之，题面说了算），叶结点即编码终点。

前缀码：任何字符的编码都不是另一个字符编码的前缀。哈夫曼编码是最优前缀码。判定方法：把每个码字沿二叉树走一遍，若任何码字中途经过或终止于另一个码字的终点（即某编码是另一编码的前缀），就不是前缀码。

例 5（模拟题）：下列编码组中，不是前缀码的是（ ）

A. {0, 10, 110, 111} B. {00, 01, 10, 11} C. {0, 1, 10, 11} D. {1, 01, 001, 000}

解答：逐组检查谁是谁的前缀。C 中 1 是 10 与 11 的前缀，不是前缀码，选 C。A 任何码字互不为前缀；B 等长码必然是前缀码；D 中 1/01/001 互不为前缀。错因提醒：等长码一定是前缀码（速判），别傻查。

#六、并查集

#双亲表示与基本操作

int parent[MAXSIZE];          // 根结点的 parent 为 -1（或负数表示集合大小/秩）
int Find(int x) {             // 找 x 所在集合的根
    while (parent[x] >= 0) x = parent[x];
    return x;
}
void Union(int a, int b) {    // 合并两个集合：把一棵根挂到另一棵根下
    int ra = Find(a), rb = Find(b);
    if (ra != rb) parent[ra] = rb;
}

工程直觉：这就是你用过的"集合合并/连通性判断"，Kruskal 的环检测就靠它。

#优化与复杂度结论（选择题速查）

必背结论：按秩合并 + 路径压缩下，$$ 次操作总代价 $$。选择题给出一串 Union 后问"parent 数组状态"或"树高"时，注意路径压缩会当场摊平路径，按最终形态作答。

#七、算法设计题精练

#题 1：求二叉树的 WPL（2014 年 408 统考算法设计题）

题面：二叉树的带权路径长度（WPL）是所有叶结点带权路径长度之和。给定含权值的二叉树（二叉链表存储，叶结点 data 为权），设计算法求 WPL。

思路：WPL = $$ 叶权 $$ 深度。对先序遍历模板做一个参数：把当前深度 $$ 一路传下去；遇到叶结点（左右孩子皆空）累加 $$。不要建哈夫曼树——题目给的是任意二叉树。

伪代码：

int WPL(BTNode *t, int d) {           // 初始调用 WPL(T, 0)，根深度为 0
    if (t == NULL) return 0;
    if (t->lchild == NULL && t->rchild == NULL)
        return t->weight * d;         // 叶结点：权 × 深度
    return WPL(t->lchild, d + 1)      // 内部结点：左右子树贡献求和
         + WPL(t->rchild, d + 1);
}

复杂度：每个结点访问一次，$$；递归栈深即树高，$$。

评分要点：深度参数起点（根为 0 还是 1）与题目 WPL 定义对齐；空树返回 0；别把内部结点也计入（只累加叶）。

#题 2：自下而上、从右到左的层序遍历（层序变形模板）

题面：对二叉树的结点，按"自下而上、同层从右到左"的顺序访问，设计算法。

思路：正常层序遍历（自上而下、从左到右）的逆序就是目标序列。用队列做正常层序，每个出队元素压栈代替直接访问；最后统一弹栈访问。入队保持"先左后右"不动——顺序的翻转全部交给栈。

伪代码：

void ReverseLevelOrder(BTNode *t) {
    if (t == NULL) return;
    InitQueue(Q);  InitStack(S);
    EnQueue(Q, t);
    while (!IsEmpty(Q)) {
        DeQueue(Q, p);
        Push(S, p);                       // 不访问，先存栈
        if (p->lchild) EnQueue(Q, p->lchild);   // 保持先左后右
        if (p->rchild) EnQueue(Q, p->rchild);
    }
    while (!IsEmpty(S)) { Pop(S, p); visit(p); }  // 逆序输出
}

复杂度：每个结点各入队、入栈一次，$$，空间 $$。

变形延伸（同一模板换问法）：每层单独一行输出（记录每层队列长度，内层循环弹出同层全部）；求树宽（每层计数取最大）；"距根最远的结点"（无权图中层序最后一个）。考场识别：凡"层"字眼，先想队列。

#常见坑

1. $$ 只对二叉树成立，$$ 叉树版本是 $$，别混用。
2. 完全二叉树 $$ 只能是 0 或 1；一般二叉树 $$ 任意。题目说"二叉树"而非"完全二叉树"时，不要套 $$ 求叶子。
3. 非递归后序的 r 指针防重复访问右子树；没有它，"出栈—看右—再入栈"框架在右子树非空时会死循环。
4. 中序线索树中 ltag/rtag 只标志本结点指针域性质，判断"结点 p 是否有前驱"看的是线索是否存在，而非 p 是否为首结点之外——头结点式线索链表中首结点前驱是头结点，不是 NULL。
5. 树转二叉树后根无右子树；森林转二叉树后根的右子树装的是除第一棵树外的所有结点。给结点数问右子树规模是常考小计算。
6. 遍历对应表里二叉树后序无对应——选项里出现"森林中序 ↔ 二叉树后序"必错。
7. 哈夫曼树形态不唯一但 WPL 唯一最小；"哈夫曼编码是最优前缀码"对，"前缀码都是哈夫曼编码"错（等长码反例）。哈夫曼编码不唯一（左右 0/1 可换、同权选取可换），但总长（WPL）唯一。
8. 并查集 Find 的路径压缩发生在 Find 过程中，只摊平被查找的路径，不动其他分支；按秩合并的"秩"在路径压缩下不再严格等于树高，但复杂度结论不受影响。

#自测

1. 某二叉树度为 2 的结点有 9 个、度为 1 的结点有 4 个，总结点数是多少？
2. 88 个结点的完全二叉树，最后一个度为 1 的结点编号是多少？它的孩子是谁？
3. 先序序列 A B C、中序序列 B C A 的二叉树，其后序序列是什么？A 的右子树上有几个结点？
4. 一棵完全二叉树第 6 层（根为第 1 层）有 8 个叶结点，该树最多有多少个结点？
5. 权集 {3, 6, 8, 2, 5} 建哈夫曼树，WPL 是多少？

答案与简析

1. $$，总数 $$。
2. $$ 为偶数 → 恰有 1 个度为 1 的结点，即最后一个分支结点，编号 $$；其左孩子为 88 号，右孩子 89 不存在。
3. 先序 ABC 首字符 A 为根，中序 B C A 中 A 居末 → 左子树含 B、C，右子树空。左子树先序 B C、中序 B C → B 为根，C 为 B 的右孩子。后序 = C B A；A 的右子树 0 个结点。
4. 求最多 → 尽量让树长高、第 6 层尽量满。前 5 层全满：$$。第 6 层最多 32 个结点，其中 8 个叶结点必须靠右（完全二叉树双亲从左到右满配，先有孩子的居左），其余靠左的 24 个结点为分支结点、各带 2 个孩子 → 第 7 层 $$ 个结点（叶）。最多总结点 $$。错因提醒：漏掉第 7 层得 63，或让 8 个叶靠左得错位形态；口诀"完全二叉树最后一层的叶居最右，倒数第二层的叶居最左"。
5. 合并序：2+3=5；5+5=10；6+8=14？不对——重算：{3,6,8,2,5} 最小两个 2、3 → 5；森林 {5(新),6,8,5}：5+5=10；{6,8,10}：6+8=14；{10,14} → 24。WPL = 内部结点和 = 5+10+14+24 = 53。逐叶复核：形态为根24（左14（叶6、叶8），右10（叶5₁、5₂（叶2、叶3）））：$$ ✓。

下一步：本章是算法大题主战场，完成讲解后立即做 测验/02-树与图-章节测，错题按规范记入 测验/00-错题本。