第5章 树与二叉树
第5章 树与二叉树¶
以选择题和综合题为主，也可能出现与树遍历相关的算法题。 高频考点：树与二叉树的基本性质、遍历、相互转换、存储结构及操作特性，以及满二叉树、完全二叉树、线索二叉树、哈夫曼树的定义与性质。
b_136_5【知识树】第5章骨架¶
- 树的基本概念：术语、五条性质
- 二叉树
- 定义、五种形态、特殊二叉树（满/完全/二叉排序/平衡/正则）
- 性质：n₀ = n₂+1、层结点数、完全二叉树编号八条
- 存储：顺序 / 二叉链表（n+1 个空链域）
- 遍历：先序/中序/后序/层序、由遍历序列构造二叉树
- 线索二叉树
- 树、森林
- 存储结构：双亲表示、孩子表示、孩子兄弟表示
- 树↔二叉树、森林↔二叉树的转换
- 树和森林的遍历
- 应用：哈夫曼树与哈夫曼编码、并查集、堆
b_136_0；PDF 第 136 页 · b_136_25.1 树的基本概念¶
树的递归定义和两个特征？¶
树是 n（n ≥ 0）个结点的有限集，n = 0 时为空树。 非空树必须满足： - 有且仅有一个特定的根结点 - n > 1 时，其余结点可分为 m（m > 0）个互不相交的有限集，每个集合本身又是一棵树，称为根的子树
⚠️ 树的定义是递归的 —— 定义中引用了自身。
两个特征： - ⚠️ 根结点没有前驱，除根外每个结点有且仅有一个前驱 - 所有结点均可拥有零个或多个后继
💡 由此得出：n 个结点的树恰好有 n − 1 条边。
b_136_9；PDF 第 137 页 · b_137_0；PDF 第 137 页 · b_137_1；PDF 第 137 页 · b_137_2；PDF 第 137 页 · b_137_3；PDF 第 137 页 · b_137_4层次、深度、高度、度怎么区分？¶
- 层次：根为第 1 层，其孩子为第 2 层，以此类推
- 结点的深度 = 其所在的层次（自顶向下数）
- 树的高度（深度） = 树中结点的最大层数
- ⚠️ 结点的高度 = 以其为根的子树的高度（自底向上数）
- 结点的度 = 该结点的孩子个数；树的度 = 所有结点的度的最大值
- 分支结点（非终端结点）：度 > 0；叶结点（终端结点）：度 = 0
其他术语：祖先/子孙、双亲/孩子、兄弟（同一双亲）、堂兄弟（⚠️ 双亲位于同一层）、路径长度（⚠️ 路径上边的数目）。 ⚠️ 有序树：各结点的子树从左到右次序固定、不可互换。
b_137_5；PDF 第 137 页 · b_137_6森林和树怎么互相转化？ ★1考¶
森林是 m（m ≥ 0）棵互不相交的树的集合。 - 树 → 森林：⚠️ 移除树的根结点，其各子树构成一个森林 - 森林 → 树：⚠️ 为 m 棵树添加一个新结点作为它们的共同根
★ 考过 2016
b_138_2树的五条性质？ ★3考¶
- ⚠️ 结点数 n = 所有结点的度数之和 + 1（因为度数之和 = 边数，而 n = 边数 + 1）
- 度为 m 的树，第 i 层至多 m^(i−1) 个结点（i ≥ 1）
- 高度为 h 的 m 叉树至多 (m^h − 1)/(m − 1) 个结点
- ⚠️ 度为 m、n 个结点的树，最小高度 h = ⌈log_m(n(m−1)+1)⌉
- ⚠️ 最大高度 h = n − m + 1；逆推：高度为 h、度为 m 的树至少有 h + m − 1 个结点
💡 最小高度的推导：要高度最小，树应尽可能饱满 → 由 (m^(h−1)−1)/(m−1) < n ≤ (m^h−1)/(m−1) 解得。 💡 最大高度的推导：至少有一个结点有 m 个孩子（同层），其他层各只放一个结点。
★ 考过 2010、2016、2022
b_138_95.2 二叉树的概念¶
二叉树和度为 2 的有序树有什么本质区别？¶
二叉树：每个结点至多两棵子树，且左右之分固定、不可交换；二叉树也是递归定义的，有 5 种基本形态。
⚠️ 两点本质区别： - 度为 2 的树至少包含 3 个结点，而二叉树可以为空 - ⚠️ 度为 2 的有序树中，某结点只有一个孩子时无须区分左右（左右是相对另一个孩子而言的）；二叉树中无论有几个孩子，左右位置都是确定且不可省略的 —— 这种次序是结构本身的固有属性，不是相对概念
b_141_19；PDF 第 141 页 · b_141_20五种特殊二叉树的定义？ ★3考¶
- 满二叉树：⚠️ 高度 h 且含 2^h − 1 个结点；所有叶结点都在最下层，除叶结点外其余结点的度均为 2
- 层序编号（根为 1）下：双亲 ⌊i/2⌋，左孩子 2i，右孩子 2i+1
- 完全二叉树：⚠️ 高度 h、含 n 个结点，当且仅当其每个结点与高度为 h 的满二叉树中编号 1~n 的结点一一对应
- 二叉排序树：左子树所有关键字 < 根 < 右子树所有关键字，且左右子树本身也是二叉排序树
- 平衡二叉树：任意结点的左右子树高度之差的绝对值不超过 1
- 正则二叉树：⚠️ 每个分支结点都有 2 个孩子，即树中仅有度为 0 或 2 的结点
★ 考过 2009、2011、2016、2018、2025
b_142_8n₀ = n₂ + 1 怎么证明？ ★1考¶
非空二叉树的叶结点数等于度为 2 的结点数加 1。
推导（必须会）： - n = n₀ + n₁ + n₂（按度分类） - n = B + 1（除根外每个结点都有一个分支进入，B 为分支总数） - B = n₁ + 2n₂（分支由度为 1 或 2 的结点射出） - 联立：n₀ + n₁ + n₂ = n₁ + 2n₂ + 1 → n₀ = n₂ + 1
⚠️ 教材原话：该性质在选择题中经常出现，务必牢记并灵活应用。
★ 考过 2025
b_142_18二叉树的层结点数与高度性质？¶
- 第 k 层最多 2^(k−1) 个结点（k ≥ 1）
- 高度为 h 的二叉树至多 2^h − 1 个结点
- ⚠️ 可拓展到 m 叉树：第 k 层最多 m^(k−1)；高度 h 至多 (m^h − 1)/(m − 1)
⚠️ 校订/边界：满二叉树是第 k 层有 2^(k-1) 个结点；只有最下面的第 h 层才是 2^(h-1)，不能写成“每层都有 2^(h-1)”。
完全二叉树的高度：h = ⌈log₂(n+1)⌉ 或 ⌊log₂n⌋ + 1 💡 推导：由 2^(h−1) − 1 < n ≤ 2^h − 1（或 2^(h−1) ≤ n < 2^h）解出。
b_143_3完全二叉树按层序编号的八条结论？ ★4考¶
- ① ⚠️ 最后一个分支结点的编号为 ⌊n/2⌋；i ≤ ⌊n/2⌋ 是分支结点，否则是叶结点
- ② 叶结点只可能出现在最后两层上
- ③ ⚠️ 若存在度为 1 的结点，最多只有一个，且只有左孩子没有右孩子（它只可能是编号 ⌊n/2⌋ 的那个）
- ④ 一旦某结点 i 为叶结点或仅有左孩子，则所有编号大于 i 的结点均为叶结点
- ⑤ ⚠️ n 为奇数 → 每个分支结点都有左右孩子；n 为偶数 → 编号 n/2 的分支结点只有左孩子
- ⑥ i > 1 时，结点 i 的双亲编号为 ⌊i/2⌋
- ⑦ 左孩子 2i，右孩子 2i + 1
- ⑧ ⚠️ 结点 i 所在层次（深度）为 ⌊log₂i⌋ + 1
★ 考过 2009、2011、2018、2025
b_143_6二叉树顺序存储的适用范围和代价？ ★2考¶
做法：按自上而下、自左至右的层序存储，⚠️ 编号 i 的结点存在数组下标 i−1 的位置（教材建议从下标 1 开始存，使下标与编号一致）。
⚠️ 只适合完全二叉树和满二叉树 —— 它们的编号能唯一反映逻辑关系，既省空间又能直接由下标确定父子兄弟关系。
⚠️ 一般二叉树的代价：需要插入若干"空结点"使结构与同高度的完全二叉树一致 —— 最坏情况下一个高度为 h 且仅有 h 个结点的单叉树，要占用近 2^h − 1 个存储单元。
★ 考过 2020、2025
b_144_1二叉链表有多少个空链域？¶
二叉链表结点：lchild | data | rchild
⚠️ 重要结论：含 n 个结点的二叉链表中共有 n + 1 个空链域（常出选择题）。 💡 推导：总链域 2n，非空的有 n − 1 个（每个非根结点被一个指针指向）→ 空的 2n − (n−1) = n + 1。 💡 下一节的线索二叉树正是利用这些空链域构造的。
⚠️ 扩展：增加指向父结点的指针域就形成三叉链表。
b_145_15.3 二叉树的遍历¶
三种遍历的"序"指的是什么？ ★5考¶
遍历的关键是确定根（N）、左子树（L）、右子树（R）的访问顺序。⚠️ 在"先左后右"的原则下有三种： - 先序遍历 NLR：访问根 → 先序遍历左子树 → 先序遍历右子树 - 中序遍历 LNR - 后序遍历 LRN
⚠️ "序"指的是根结点在遍历序列中的位置。
★ 考过 2009、2011、2012、2014、2017、2022
b_152_9先序、中序、后序的递归模板怎样只改一行位置？¶
三种递归遍历都先判断空树，且递归访问左右子树的先后次序始终是“先左后右”；唯一变化是 visit(T) 放在两次递归调用的前、中、后。
void PreOrder(BiTree T) {
if (T != NULL) {
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void InOrder(BiTree T) {
if (T != NULL) {
InOrder(T->lchild);
visit(T);
InOrder(T->rchild);
}
}
void PostOrder(BiTree T) {
if (T != NULL) {
PostOrder(T->lchild);
PostOrder(T->rchild);
visit(T);
}
}
💡 自检：把 visit(T) 读成“访问根”，它在前就是 NLR，在中就是 LNR，在后就是 LRN。⚠️ 三种模板都不能调换左右递归的顺序。
b_152_17；PDF 第 153 页 · b_153_0；PDF 第 153 页 · b_153_8；PDF 第 153 页 · b_153_9；PDF 第 153 页 · b_153_16；PDF 第 153 页 · b_153_17三种遍历的复杂度和栈深度？ ★2考¶
三种遍历递归遍历左右子树的顺序都固定，区别仅在于访问根结点的时机。
- ⚠️ 每个结点都被访问一次且仅一次，时间复杂度均为 O(n)
- ⚠️ 递归实现中，系统工作栈的深度等于树的高度 → 最坏情况（如单支树）空间复杂度 O(n)
教材例（同一棵树）：先序 124635，中序 264135，后序 642531。
★ 考过 2017、2024
b_153_5层次遍历的模板？¶
⚠️ 借助一个队列：根入队 → 出队并访问队头 → 把它的左右孩子依次入队 → 直到队空。
void LevelOrder(BiTree T) {
InitQueue(Q); BiTree p;
EnQueue(Q, T);
while(!IsEmpty(Q)) {
DeQueue(Q, p); visit(p);
if(p->lchild != NULL) EnQueue(Q, p->lchild);
if(p->rchild != NULL) EnQueue(Q, p->rchild);
}
}
💡 教材要求：把它当模板，达到熟练手写的程度。
需要层号/宽度/高度时，再加一层边界：
while (!IsEmpty(Q)) {
int levelSize = QueueLength(Q); // 本层结点数，必须在本层出队前固定
if (levelSize > maxWidth) maxWidth = levelSize;
while (levelSize-- > 0) {
DeQueue(Q, p);
if (p->lchild) EnQueue(Q, p->lchild);
if (p->rchild) EnQueue(Q, p->rchild);
}
++level;
}
⚠️ 边界：普通队列模板只保证层序访问次序；要分层必须加 levelSize（或 last/nextLast、哨兵）。判断完全二叉树还需额外记录“已遇到空孩子”，之后不得再出现非空孩子。
⚠️ 一句方法论：求双亲、查孩子、算深度、数叶结点、判断两棵树是否相同，本质上都是在某种遍历过程中完成的。
b_154_0；PDF 第 154 页 · b_154_1哪些遍历序列组合能唯一确定二叉树？ ★4考¶
⚠️ 仅凭任意一种遍历序列无法唯一确定二叉树。 ⚠️ 必须已知中序序列，再辅以先序、后序、层序中的任意一种，才能唯一重构。
反例（必须记住）：先序都是 AB、后序都是 BA、层序都是 AB 的两棵不同二叉树 → ⚠️ 先序、后序、层序中任意两种组合通常无法唯一确定一棵二叉树。
★ 考过 2015、2017、2020、2021
b_154_7由先序+中序构造二叉树的思路？ ★2考¶
- 先序序列的第一个结点必是根
- 该根在中序序列中把序列划分为左右两个子序列：左边是左子树的中序序列，右边是右子树的中序序列
- ⚠️ 左右子树的结点数在先序和中序中一致 → 据此从先序序列中分离出左右子树各自的先序子序列
- 递归重复
教材例：先序 ABCDEFGHI、中序 BCAEDGHFI → A 是根；中序中 A 左边的 BC 是左子树、右边的 EDGHFI 是右子树 → 再由先序知 B 是左子树的根，D 是右子树的根，以此类推。
★ 考过 2020、2021
b_154_9；PDF 第 154 页 · b_154_11；PDF 第 154 页 · b_154_14；PDF 第 155 页 · b_155_0后序+中序、层序+中序怎么构造？ ★2考¶
- 后序 + 中序：⚠️ 后序序列的最后一个结点是根，同样用它划分中序序列，再按结点数从后序中分离左右子树的后序序列，递归
- 层序 + 中序：⚠️ 层序第一个结点是根；若有左子树，层序的第二个结点一定是左子树的根；若有右子树，紧接着的下一个结点一定是右子树的根 —— 逐层确定各子树的根并递归划分
💡 三种构造的共同套路：先在"非中序"序列里找到根，再用它劈开中序序列。
★ 考过 2017、2023
b_155_45.3.2 线索二叉树¶
线索二叉树的空指针数怎么算？ ★1考¶
⚠️ 传统二叉链表只能反映父子关系，无法直接获取遍历序列中的前驱后继。
空指针总数推导：每个叶结点贡献 2 个空指针，每个度为 1 的结点贡献 1 个 → 2n₀ + n₁；又 n₀ = n₂ + 1 → = n₀ + n₁ + n₂ + 1 = n + 1。
线索化的规定： - ⚠️ 无左子树 → lchild 指向该结点在指定遍历序列中的前驱 - ⚠️ 无右子树 → rchild 指向其后继
★ 考过 2010
b_156_1ltag / rtag 各表示什么？¶
结点结构：lchild | ltag | data | rtag | rchild - ⚠️ ltag = 0 → lchild 指向左孩子；ltag = 1 → lchild 指向前驱 - ⚠️ rtag = 0 → rchild 指向右孩子；rtag = 1 → rchild 指向后继
术语：这种二叉链表称为线索链表，指向前驱后继的指针称为线索，带线索的二叉树称为线索二叉树。
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag;
}ThreadNode, *ThreadTree;
b_156_6中序线索化的两个 if 分别做什么？ ★1考¶
⚠️ 线索化本质上就是对二叉树进行一次遍历 —— 因为前驱后继关系只能在遍历过程中确定。
设 pre 指向刚访问过的结点，p 指向当前结点（pre 即 p 的中序前驱）：
InThread(p->lchild, pre);
if (p->lchild == NULL) { p->lchild = pre; p->ltag = 1; } // 建当前结点的前驱线索
if (pre != NULL && pre->rchild == NULL) { pre->rchild = p; pre->rtag = 1; } // 建前驱的后继线索
pre = p;
InThread(p->rchild, pre);
⚠️ 主过程收尾必须处理最后一个结点：
★ 考过 2014
b_156_14加头结点的线索链表有什么好处？¶
- 头结点的 lchild 指向根结点
- 头结点的 rchild 指向中序序列的最后一个结点
- 中序序列第一个结点的 lchild 和最后一个结点的 rchild 均指向头结点
⚠️ 这样就形成一个双向循环线索链表，支持正向与反向的高效遍历。
b_157_5中序线索二叉树怎么找后继？¶
⚠️ 遍历时无须借助栈或递归 —— 先找到中序序列的第一个结点，然后依次找后继。
找后继的规则： - rtag = 1 → rchild 直接指向后继 - ⚠️ rtag = 0 → 后继是右子树中最左下的结点（右子树的中序第一个结点）
找中序第一个结点：
ThreadNode *Firstnode(ThreadNode *p) {
while (p->ltag == 0) p = p->lchild; // 沿左孩子链走到最左下结点
return p;
}
b_157_6先序线索二叉树找后继容易吗？¶
容易： - 有左孩子 → 左孩子就是后继 - 无左孩子但有右孩子 → 右孩子是后继 - 叶结点 → rchild 直接指向后继
教材例（先序序列 ABCDF）：C 无左孩子 → lchild 指前驱 B，无右孩子 → rchild 指后继 D；⚠️ F 无右孩子且无后继 → rchild 置为空。
b_158_3；PDF 第 158 页 · b_158_4后序线索二叉树找后继为什么麻烦？ ★1考¶
⚠️ 要分三种情况： - ① x 是整棵树的根 → 后继为空 - ② x 是双亲的右孩子，或是双亲的左孩子且该双亲无右子树 → 后继就是其双亲 - ③ x 是双亲的左孩子且双亲有右子树 → 后继是该右子树中按后序访问的第一个结点（右子树中最左下结点）
⚠️ 致命处：教材例中结点 B 的后继是 A，但无法直接通过线索找到，需要回溯到双亲 → 后序线索二叉树中高效查找后继通常需要知道父结点信息，⚠️ 所以通常采用带父指针的三叉链表，而非标准的二叉线索链表。
★ 考过 2013
b_158_115.4 树、森林¶
三种树的存储结构各自的强弱？¶
- 双亲表示法：数组存结点，每个结点增设 parent 伪指针（⚠️ 根的双亲域为 −1）
- ⚠️ 查双亲高效，查孩子要遍历整个数组，效率低
- 孩子表示法：每个结点的所有孩子用单链表存储，头指针集中存在一个数组中（叶结点对应空链表）
- ⚠️ 查孩子方便，查双亲要遍历所有孩子链表，效率低
-
孩子兄弟表示法（二叉树表示法）：⚠️ "左孩子 - 右兄弟"
-
⚠️ 最大优点是能自然地把树转换为二叉树，复用二叉树算法；查孩子高效，但回溯双亲困难（可增设 parent 域成为三叉链表）
⚠️ 易混：树的双亲表示法中下标只是标识，父子关系靠 parent 域显式记录；二叉树顺序存储中下标本身隐含父子关系。⚠️ 一般的树不能直接用二叉树的顺序存储方式。
b_180_5树转二叉树的规则和手工画法？ ★2考¶
规则（左孩子 - 右兄弟）：每个结点的左指针指向其第一个孩子；右指针指向其在原树中的下一个右兄弟。 ⚠️ 由树转换而来的二叉树，根结点必无右子树（因为根没有兄弟）。
手工三步： - ① 在所有兄弟结点之间添加连线 - ② 对每个结点只保留与第一个孩子的连线，删除与其他孩子的连线 - ③ 以树根为轴心顺时针旋转 45°
★ 考过 2009、2011
b_182_7森林转二叉树怎么做？ ★1考¶
- ① 将森林中每棵树分别转换为二叉树
- ② ⚠️ 每棵树的根视为兄弟，在各根之间依次添加连线（因为每棵转换后的二叉树根都无右子树，正好把第二棵作为第一棵根的右子树，以此类推）
- ③ 以第一棵树的根为轴心顺时针旋转 45°
💡 等效做法：先在各树的根之间连线，再整体套用"树转二叉树"。
★ 考过 2014
b_182_15二叉树怎么还原成森林？ ★2考¶
- 二叉树的根及其左子树 → 对应第一棵树
- ⚠️ 把根的右指针断开，其右子树代表剩余森林转换后的二叉树
- 对右子树递归应用相同规则，不断分离下一棵树，直至右子树为空
- 最后把每棵分离出的二叉树还原为普通树
⚠️ 边界：“断开根的右链”是把右子树分离为后续树的编码，不是删除或丢弃那些结点。
⚠️ 二叉树转换为树或森林的结果是唯一的。
★ 考过 2020、2021
b_183_3树、森林、二叉树的遍历如何对应？ ★2考¶
| 树 | 森林 | 二叉树 |
|---|---|---|
| 先根遍历 | 先序遍历 | 先序遍历 |
| 后根遍历 | 中序遍历 | 中序遍历 |
- 树的先根遍历：先访问根，再依次遍历每棵子树
- 树的后根遍历：先依次遍历每棵子树，再访问根
- 森林的先序遍历：访问第一棵树的根 → 先序遍历第一棵树的子树森林 → 先序遍历剩余森林
- 森林的中序遍历：中序遍历第一棵树的子树森林 → 访问第一棵树的根 → 中序遍历剩余森林
💡 为什么能对应：⚠️ 森林转二叉树时，第一棵树的子树森林变成左子树，剩余森林变成右子树。
教材例：图 5.22 树的先根 ABEFCDG，后根 EFBCGDA；图 5.23 森林的先序 ABCDEFGHI，中序 BCDAFEHIG。 ⚠️ 命名注意：有些教材把森林的中序遍历称为后序遍历（因为根确实最后才被访问）。
★ 考过 2019、2020
b_183_115.5 树与二叉树的应用¶
WPL 怎么算？什么是哈夫曼树？¶
- 权：结点被赋予的数值
- 结点的带权路径长度 = 根到该结点的路径长度 × 该结点的权值
- 树的带权路径长度 WPL = ⚠️ 所有叶结点的带权路径长度之和
- 加权平均长度 = WPL ÷ 各叶结点权值之和
⚠️ 含 n 个带权叶结点的二叉树中，WPL 最小的称为哈夫曼树（最优二叉树）。
教材对照例（叶结点权值 7、5、2、4）：(a) WPL=36，(b) WPL=46，(c) WPL=35 → (c) 是哈夫曼树。
b_192_8哈夫曼树的构造四步？ ★1考¶
- ① 把 n 个结点各视为一棵只含一个结点的二叉树，构成森林 F
- ② 从 F 中选取两棵根结点权值最小的树作为新结点的左右子树，⚠️ 新结点的权值 = 左右子树根结点权值之和
- ③ 从 F 中删除这两棵树，把新树加入 F
- ④ 重复 ②③ 直到 F 中仅剩一棵树
★ 考过 2010
b_193_10哈夫曼树的三条性质？ ★2考¶
- ⚠️ 每个初始结点最终都成为叶结点；若两个叶结点权值有严格大小关系，则较小权值的路径长度不短于较大权值。不同权值仍可能位于同层，所以这里不是“权值越小就必定严格更深”
- ⚠️ 构造中共新建 n − 1 个结点（双分支结点） → 哈夫曼树的结点总数为 2n − 1
- ⚠️ 不存在度为 1 的结点（每次合并都取两棵树）→ 是严格（正则）二叉树
💡 由此可反推常考结论：若哈夫曼树共有 m 个结点，则叶结点数 n = (m+1)/2。
★ 考过 2010、2019
b_193_14什么是前缀编码？为什么能唯一译码？ ★3考¶
⚠️ 前缀编码 = 编码集合中没有任何一个编码是另一个编码的前缀。
例：A、B、C 编码为 0、10、110 是前缀编码 —— 从左到右扫描码串，一旦识别出有效编码即可立即译出，码串 0010110 唯一译为 A A B C。 ⚠️ 反例：若再给 D 分配 11，则 11 是 110 的前缀 → 上述码串后 3 位无法确定是 D A 还是 C，唯一可译性被破坏。
用二叉树设计前缀编码：叶结点对应字符，左分支标 0、右分支标 1，根到叶结点路径上的标记拼接即为编码 —— ⚠️ 如此生成的编码必为前缀编码。
★ 考过 2014、2017、2020
b_194_5哈夫曼编码的压缩效果怎么算？ ★5考¶
做法：每个字符作为一个叶结点，权值为其出现频度 → 构造哈夫曼树 → 根到叶的路径标记即为该字符的编码。
教材算例（6 个字符，共 100 个字符）：
- ⚠️ WPL 就是编码后的二进制总长度 = 224 位
- 固定长度编码：6 个字符至少需 3 位 → 3 × 100 = 300 位
- ⚠️ 压缩率约 25%
💡 结论：利用哈夫曼树可以设计出总长度最短的二进制前缀编码。
★ 考过 2012、2018、2021、2022、2023
b_194_4哈夫曼树的形态唯一吗？¶
⚠️ 不唯一。 两个原因： - 左右分支表示 0 还是 1 并无强制规定 - ⚠️ 存在多个权值相同的结点时，合并顺序不同也会导致结构不同
⚠️ 但无论形态如何，WPL 始终相同且达到最小值 —— 最优性不受影响。
💡 这是选择题的经典陷阱："哈夫曼树唯一"是错的，"哈夫曼树的 WPL 唯一"才对。
b_194_185.5.2 并查集¶
并查集的三个基本操作？¶
- Initial(S)：把每个元素初始化为一个独立的单元素子集合
- Union(S, Root1, Root2)：把子集合 Root2 并入 Root1；⚠️ 要求两者属于不同子集合，否则不执行
- Find(S, x)：查找 x 所属的子集合，返回该子集合的根结点
💡 并查集是处理不相交集合的合并与查询问题的树状数据结构。
b_195_1并查集的数组里存的是什么？根为什么是负数？¶
⚠️ 采用树的双亲表示法：每个子集合是一棵树，所有树构成森林，统一存在一个数组中。 - 数组下标 = 元素编号 - 元素存的值 = 其双亲结点的下标 - ⚠️ 根结点的双亲域设为负数 —— 通常取该子集合元素数量的相反数，⚠️ 既标识它是根，又记录了集合规模
初始化：所有位置都置为 −1（每个元素自成一个集合）。 合并：把一个子集合根在数组中的值设为另一个子集合的根下标。
b_195_4Find 和 Union 的基本实现与复杂度？¶
int Find(int S[], int x) {
while (S[x] >= 0) x = S[x]; // 循环找根
return x; // 根的 S[] 小于 0
}
void Union(int S[], int Root1, int Root2) {
if (Root1 == Root2) return;
S[Root2] = Root1;
}
⚠️ Find 是 O(d)，Union 是 O(1)，其中 d 为树的深度。 💡 判断两个元素是否属于同一集合：分别 Find 出根，比较根是否相同。
b_196_1；PDF 第 196 页 · b_196_4并查集的两个优化各把深度降到多少？¶
⚠️ 最坏情况：n 个元素的集合树退化为一条链，深度达 n，Find 最坏 O(n)。
- 优化一：按集合大小合并（小树并入大树）
-
Union 前先比较两个子集合的规模，⚠️ 利用根结点值的绝对值即集合大小
-
⚠️ 构造的集合树深度不超过 ⌊log₂n⌋ + 1
- 优化二：路径压缩
- ⚠️ 找到根后，把从 x 到根路径上的所有中间结点直接挂到根下
⚠️ 两种优化都用上后，深度不超过 O(α(n))，其中 α(n) 增长极其缓慢，常见 n 下 α(n) ≤ 4。
💡 注意代码细节：S[Root2] > S[Root1] 表示 Root2 结点数更少 —— 因为存的是负数，值越大反而元素越少。
b_196_12【原书试题精选与答案方法】第5章¶
树和森林的“结点—边—度”题，怎样用一组等式统一求解？（2010、2016 统考；5.1 综合 02、03）¶
先把结点按度分类。设度为 \(i\) 的结点数为 \(n_i\)，总结点数为 \(n\)，边数为 \(e\)，则
消去 \(n\)、\(e\)，立即得到最常用的叶结点公式
- 2010 统考第 09 题：\(n_0=1+(2-1)\times1+(3-1)\times10+(4-1)\times20=82\)，选 B。
- 2016 统考第 10 题：森林有 \(k\) 棵树时，\(e=n-k\)，所以 \(k=25-15=10\)，选 C。
- 综合 02：由 \(n=23+n_4\) 与 \(n=17+4n_4\)，得 \(n_4=2,n=25\)。
- 综合 03：直接写出上面的通式即可。
💡 这类题不要数图，先写“总结点数 = 总分支数 + 1”；森林则改成“总结点数 = 总边数 + 树的棵数”。
b_140_19；PDF 第 140 页 · b_140_21；PDF 第 141 页 · b_141_7；PDF 第 141 页 · b_141_10含有 n 个结点的三叉树，最小高度怎样反推？（5.1 综合 01）¶
要让高度最小，应让每层尽可能满。高度为 \(h\) 的三叉树至多含
个结点；而第 \(h\) 层至少出现一个结点，因此
于是
💡 通用到 \(m\) 叉树：\(h_{\min}=\lceil\log_m(n(m-1)+1)\rceil\)。核心不是背公式，而是先写“前 \(h-1\) 层装不下、前 \(h\) 层装得下”。
b_141_1；PDF 第 141 页 · b_141_2；PDF 第 141 页 · b_141_5完全二叉树的叶结点、总结点数怎样互推？（2009、2011、2018 统考）¶
先记住两个入口：完全二叉树最后一个分支结点编号为 \(\lfloor n/2\rfloor\)；非空二叉树恒有 \(n_0=n_2+1\)。
- 2009 第 25 题：第 6 层有 8 个叶结点且求结点数最大，应令树高为 7；相对 7 层满二叉树，末层缺 \(8\times2=16\) 个结点，故 \(n=2^7-1-16=111\)，选 C。
- 2011 第 26 题：\(n=768\) 时，叶结点编号从 \(\lfloor768/2\rfloor+1\) 到 768，共 \(768-384=384\) 个，选 C。
- 2018 第 27 题：所有叶在同层且每个非叶都有两个孩子，实际就是满二叉树；若叶结点有 \(k\) 个，则总结点数为 \(2k-1\)，选 A。
⚠️ “叶结点只在最后一层”只对满二叉树成立；一般完全二叉树的叶结点可能分布在最后两层。
b_150_4；PDF 第 150 页 · b_150_6；PDF 第 150 页 · b_150_9一般 m 叉树的最小高度怎样判断？（2022 统考）¶
高度一定时，结点最多的形态是满 \(m\) 叉树。不要试画 244 个结点，只需比较容量：
2022 第 29 题中 \(m=3,n=244\)：高度 5 至多容纳 \(121\) 个结点，高度 6 至多容纳 \(364\) 个，因此最小高度为 6，选 C。
💡 题目给“叶结点高度为 1”是在说明本题按层数计高度；答题时要先统一高度口径。
b_150_12；PDF 第 150 页 · b_150_13二叉树顺序存储要多少空间，数组是否合法，分别看什么？（2020、2025 统考）¶
两类题要分开判断：
- 问任意形态所需的最少容量：按同高度满二叉树预留。2020 第 28 题高度为 5，最坏位置编号可到 \(2^5-1=31\)，故至少 31 个单元，选 A。
- 问给定数组能否表示二叉树：每个非空结点的祖先链必须全部非空。下标从 0 开始时，结点 \(i\) 的双亲是 \(\lfloor(i-1)/2\rfloor\)。2025 第 30 题 D 中 \(R[8]=19\)，但其双亲 \(R[3]=-1\)，出现“空双亲有非空后代”，不合法。
⚠️ 顺序存储并不要求数组连续非空；它要求的是：只要当前位置非空，从它沿双亲下标回到根的整条路径都非空。
b_150_10；PDF 第 150 页 · b_150_11；PDF 第 150 页 · b_150_14；PDF 第 150 页 · b_150_15；PDF 第 150 页 · b_150_16已知完全二叉树的叶结点数和度为 1 的结点数，怎样求高度？（5.2 综合 01）¶
利用
再代入完全二叉树高度公式 \(h=\lceil\log_2(n+1)\rceil\)。
- 若 \(n_1=1\)，则 \(n=2n_0\)，故 \(h=\lceil\log_2(2n_0+1)\rceil\)。
- 若 \(n_1=0\)，则 \(n=2n_0-1\)，故 \(h=\lceil\log_2(2n_0)\rceil=\lceil\log_2n_0\rceil+1\)。
💡 完全二叉树的 \(n_1\) 只能是 0 或 1；总结点数奇偶性常可反推出它。
b_150_19；PDF 第 150 页 · b_150_20；PDF 第 150 页 · b_150_21；PDF 第 150 页 · b_150_22n 个结点的满二叉树有多少分支结点、叶结点和高度？（5.2 综合 02）¶
满二叉树中没有度为 1 的结点，且 \(n_0=n_2+1\)，所以
又因为 \(n=2^h-1\)，所以
⚠️ 题目已说明“满二叉树”，因此 \(n\) 必为 \(2^h-1\) 形式；若代入后 \(h\) 不是整数，说明给定条件本身不能构成满二叉树。
b_150_23；PDF 第 150 页 · b_150_24；PDF 第 151 页 · b_151_0完全二叉树第 9 层有 240 个结点，怎样求总结点数和叶结点数？（5.2 综合 03）¶
第 9 层满时应有 \(2^8=256\) 个结点；现在只有 240 个，说明第 9 层就是未满的最后一层，前 8 层全满。
- 总结点数：\(2^8-1+240=495\)。
- 第 9 层 240 个结点由第 8 层最左侧 120 个双亲产生；第 8 层共有 \(2^7=128\) 个结点，余下 8 个也是叶结点。
- 叶结点总数：\(240+8=248\)。
💡 校验法：\(495\) 为奇数，所以完全二叉树没有度为 1 的结点，\(n_0=(n+1)/2=248\)。
b_151_1；PDF 第 151 页 · b_151_2；PDF 第 151 页 · b_151_3；PDF 第 151 页 · b_151_4满 m 叉树按层序编号时，双亲、孩子和右兄弟编号怎样统一推导？（5.2 综合 04）¶
根从 1 编号，按层、自左向右排列：
- 第 \(i\) 层有 \(m^{i-1}\) 个结点。
- 结点 \(i>1\) 的双亲编号：\(\left\lfloor\frac{i-2}{m}\right\rfloor+1\)。
- 结点 \(i\) 的第 \(k\) 个孩子编号：\((i-1)m+k+1\)，其中 \(1\le k\le m\)；仅当该孩子确实存在（算出的编号不超过总结点数 \(N\)）时才有效，叶结点不能凭公式制造孩子。
- 若 \(i\) 不是双亲的第 \(m\) 个孩子，则有右兄弟，编号为 \(i+1\)；等价判据是 \((i-1)\bmod m\ne0\)。
⚠️ 这些式子对应“根编号为 1”的约定；若数组下标从 0 开始，必须整体换一套下标关系，不能混用。
b_151_7；PDF 第 151 页 · b_151_8顺序存储的二叉树，怎样求两个结点的最近公共祖先？（5.2 综合 05）¶
下标从 1 开始时，结点 \(i\) 的双亲为 \(\lfloor i/2\rfloor\)。因此不断把编号较大的结点上移即可：
为什么可行？完全二叉树的层序编号随层次总体递增，编号较大的结点不会比编号较小的结点更靠近根；每次上移都保留原结点的祖先集合，第一次相等的位置就是最近公共祖先。
⚠️ 先检查两个位置确实存在；若下标从 0 开始，双亲公式应改为 \(\lfloor(i-1)/2\rfloor\)。
b_151_9；PDF 第 151 页 · b_151_10；PDF 第 151 页 · b_151_11；PDF 第 151 页 · b_151_12正则 k 叉树的叶结点数，以及给定高度时的最多、最少结点数怎样求？（2016 统考；5.2 综合 06）¶
正则 \(k\) 叉树只有叶结点和度为 \(k\) 的分支结点。若有 \(m\) 个非叶结点，则边数既是 \(n-1\)，又是 \(mk\)：
高度为 \(h\) 时：
- 最多：每一层都尽量满，\(N_{\max}=\dfrac{k^h-1}{k-1}\)。
- 最少：每层只让一个分支结点继续向下，其余 \(k-1\) 个孩子都成为叶结点；除根外每层恰有 \(k\) 个结点，故 \(N_{\min}=1+(h-1)k\)。
💡 这道 2016 统考综合题同时考“边数守恒”和“极值树形”：最多画满树，最少画一条继续生长的主链。
b_152_1；PDF 第 152 页 · b_152_2；PDF 第 152 页 · b_152_4；PDF 第 152 页 · b_152_5遍历次序不是 NLR/LNR/LRN 时，怎样照样分析？（2009、2017、2023 统考）¶
先把字母规则机械展开，不要只背三种标准遍历。
- 2009 第 32 题：序列中根在中间，且右子树先于左子树，故次序为 RNL，选 D。
- 2017 第 39 题：后序是“左—右—根”，由末尾逐层确定根，再把前段分给左右子树；还原后与 \(a\) 同层的是 \(d\)，选 B。
- 2023 第 42 题：题目给出树形与后序，可先按“左右根”把字母填回树，再做“根左右”，得到先序 aedfbc，选 A。
💡 统一方法：把每个子树都当成一个整体，先确定“根在序列哪一端或哪一段”，再递归拆分。
b_168_9；PDF 第 168 页 · b_168_10；PDF 第 169 页 · b_169_11；PDF 第 169 页 · b_169_13；PDF 第 170 页 · b_170_9；PDF 第 170 页 · b_170_12只有先序和后序时，能确定哪些信息、不能确定什么？（2011、2012、2015 统考）¶
先序和后序通常不能唯一确定左右孩子方向，但能稳定判断一部分祖先关系。
- 若两结点在先序中为 \(X\cdots Y\)，在后序中为 \(Y\cdots X\)，则 \(X\) 是 \(Y\) 的祖先。
- 2012 第 35 题据此可知 \(a\) 是根，\(e\) 是其唯一孩子，选 A。
- 2011 第 34 题中先序与后序正好相反，树必为单支链；每个结点的唯一孩子可左可右，据此逐项检验中序，不能出现的是 C。
- 2015 第 38 题：固定先序 \(a,b,c,d\)，不同中序序列与合法出栈序列一一对应，数量为 Catalan 数 \(C_4=14\)，选 B。
⚠️ “能判断祖先关系”不等于“能唯一确定树形”；左右方向仍可能有多种选择。
b_168_13；PDF 第 168 页 · b_168_14；PDF 第 168 页 · b_168_17；PDF 第 168 页 · b_168_18；PDF 第 169 页 · b_169_9；PDF 第 169 页 · b_169_10怎样用遍历中的相对位置反推孩子方向和相邻关系？（2017、2022、2024 统考）¶
- 2017 第 40 题：先序是“根左右”，中序是“左根右”。两序列完全相同，只能让每个非叶结点都没有左子树、只有右子树，选 B。
- 2022 第 41 题：中序中 \(p,q\) 相邻。若二者是左右兄弟，中间一定夹着双亲，所以“\(q\) 是 \(p\) 的右兄弟”不可能；其余关系均可构造特例，选 B（仅 III）。
- 2024 第 43 题：在 \(v\) 的中序片段中，\(p\) 是左子树最后访问者，故 \(p\) 不能有右孩子；\(q\) 是右子树最先访问者，故 \(q\) 不能有左孩子，选 A。
💡 做“必然/不可能”题时，先用局部中序模板 左子树—根—右子树；不能直接推出的选项就画最小反例验证。
b_169_14；PDF 第 169 页 · b_169_15；PDF 第 169 页 · b_169_16；PDF 第 169 页 · b_169_17；PDF 第 170 页 · b_170_0；PDF 第 170 页 · b_170_13；PDF 第 170 页 · b_170_14；PDF 第 170 页 · b_170_15线索题怎样先写遍历序列、再判断指针指向？（2010、2013、2014 统考）¶
线索只补原本为空的孩子指针，并指向指定遍历序列中的前驱或后继；因此第一步永远是写出完整遍历序列。
- 2010 第 33 题：写出后序
dbca，逐个检查空左链是否指前驱、空右链是否指后继，选 D。 - 2013 第 36 题：后序线索树中，叶结点 \(X\) 是右孩子且有左兄弟时，\(X\) 的后继就是双亲，因此右线索指向父结点，选 A。
- 2014 第 37 题：先写中序
debxac，\(x\) 左右相邻者分别为 \(b,a\)，所以左右线索指向 \(b,a\)，选 D。
⚠️ 若对应孩子真实存在，该指针是孩子链而不是线索；不能只看序列相邻就强行改指针。
b_168_11；PDF 第 168 页 · b_168_12；PDF 第 169 页 · b_169_4；PDF 第 169 页 · b_169_5；PDF 第 169 页 · b_169_7；PDF 第 169 页 · b_169_8先序与后序正好相反或正好相同，树形分别是什么？（5.3 综合 01、02）¶
- 正好相反：先序
NLR等于后序LRN的逆序NRL，每层只能有一棵非空子树；整棵树是一条单支链，高度等于结点数。每个唯一孩子可在左也可在右。 - 正好相同：要让
NLR=LRN，根既要最先又要最后，只可能没有左右子树；非空树只能有一个根结点。
⚠️ “先序和后序相反”只能推出每个结点至多一个孩子，不能推出它一定全左斜或全右斜。
b_170_17；PDF 第 170 页 · b_170_18；PDF 第 170 页 · b_170_20；PDF 第 170 页 · b_170_21不用递归，怎样用层次遍历求二叉树高度？（5.3 综合 03）¶
用队列做层次遍历，并维护当前层的结束边界：
- 根入队，
last指向当前层最右结点，level=0。 - 每出队一个结点，就把它的非空左右孩子入队。
- 当出队位置到达
last，说明本层结束：level++，并令last指向此时队尾，也就是下一层最右结点。 - 队空时返回
level。
时间复杂度 \(O(n)\)，队列最坏占 \(O(n)\)。同一边界思想还可用于统计每层结点数和最大宽度。
b_170_22；PDF 第 170 页 · b_170_23；PDF 第 170 页 · b_170_24；PDF 第 170 页 · b_170_25；PDF 第 171 页 · b_171_0；PDF 第 171 页 · b_171_1；PDF 第 171 页 · b_171_2怎样用一个队列判定二叉树是否完全？（5.3 综合 04）¶
按层序把非空结点和空孩子位置都入队：
- 正常出队非空结点，并把它的左右孩子（可为空）依次入队。
- 一旦第一次出队空结点，后续队列中就只能再出现空结点。
- 若其后仍出现非空结点，说明层序编号中出现“空位之后又有结点”，不是完全二叉树；否则是。
💡 等价写法是设 seenNull=true；之后遇到任何非空结点立即返回 false。时间 \(O(n)\)，空间 \(O(n)\)。
b_171_3；PDF 第 171 页 · b_171_4；PDF 第 171 页 · b_171_5；PDF 第 171 页 · b_171_6怎样递归统计二叉树中的双分支结点数？（5.3 综合 05）¶
后序式分解最自然：先统计左右子树，再判断当前根是否同时有左右孩子。
空树返回 0。每个结点只访问一次，时间 \(O(n)\)；递归栈为 \(O(h)\)。
⚠️ 题目问的是双分支，条件必须是左右孩子都非空；不能把度为 1 的结点也计入。
b_172_0；PDF 第 172 页 · b_172_1；PDF 第 172 页 · b_172_2；PDF 第 172 页 · b_172_4；PDF 第 172 页 · b_172_5交换二叉树所有结点的左右子树，为什么适合后序递归？（5.3 综合 06）¶
递归处理当前结点的左右子树，再交换当前结点的两个孩子指针：
先处理孩子、后处理根，正是后序遍历思想。时间 \(O(n)\)，递归栈 \(O(h)\)。
💡 先交换当前结点再递归也能实现，但递归目标必须跟着交换后的指针变化；考试中采用书上的后序模板更直观、不易写乱。
b_172_6；PDF 第 172 页 · b_172_7；PDF 第 172 页 · b_172_8怎样找到先序遍历中的第 k 个结点？（5.3 综合 07）¶
在先序模板中增加访问计数器 i：访问根时先判断 i==k，否则 i++，再依次递归左、右子树。
- 空树返回未找到标志。
- 左子树若已找到，立即向上返回，不能继续进入右子树。
- 初始调用前必须把计数器重置为 1。
时间最坏 \(O(n)\)，递归栈 \(O(h)\)。同样方法可迁移到中序、后序的“第 \(k\) 个结点”，只需把计数与判断放到相应的访问位置。
b_172_9；PDF 第 172 页 · b_172_10；PDF 第 172 页 · b_172_11；PDF 第 172 页 · b_172_13；PDF 第 173 页 · b_173_0；PDF 第 173 页 · b_173_1怎样删除所有值为 x 的结点所对应的整棵子树？（5.3 综合 08）¶
问题包含两个动作：找到其双亲并断链，再释放整棵目标子树。
DeleteXTree(p)用后序递归：先释放左右子树，再释放根。- 若整棵树的根值就是 \(x\)，直接删除整棵树并把根指针置空。
- 否则层序遍历双亲：若某个左/右孩子值为 \(x\)，删除该孩子子树并把对应孩子指针置空；不匹配的孩子才继续入队。
⚠️ 不能先释放目标根再访问它的孩子；也不能忘记把双亲的孩子指针置空，否则留下悬空指针。
b_173_2；PDF 第 173 页 · b_173_3怎样打印值为 x 的结点的所有祖先？（5.3 综合 09）¶
采用非递归后序遍历。沿搜索路径入栈，并用标志区分“左子树已访问”与“右子树已访问”。
- 当到达值为 \(x\) 的结点时，栈中保存的正是从根到其双亲的全部结点。
- 按栈底到栈顶输出，可得到根到双亲的祖先顺序。
- 后序遍历适合本题，是因为一个结点真正出栈前，其整条祖先路径仍保留在栈中。
时间最坏 \(O(n)\)，栈深不超过树高 \(h\)，空间 \(O(h)\)。
b_173_4；PDF 第 173 页 · b_173_5；PDF 第 174 页 · b_174_0；PDF 第 174 页 · b_174_1二叉链表中怎样求两个给定结点的最近公共祖先？（5.3 综合 10）¶
书中沿用非递归后序遍历的“栈保存祖先路径”性质：
- 原书为叙述方便假设后序遍历先遇到 \(p\)；若实际先遇到 \(q\)，交换两者角色即可。遇到第一个目标时，把当前栈复制到辅助栈。
- 继续遍历到另一个目标时，当前栈保存它的路径。两次复制都要包含目标结点本身，这样当一个目标正是另一个的祖先时，最近公共祖先可以正确返回该目标。
- 从靠近结点的一端开始匹配两条祖先链，第一个相同结点就是最近公共祖先。
核心不是死背长代码，而是理解：后序遍历访问当前结点时，栈内尚未退出的结点就是它的祖先。最坏时间 \(O(n)\)，辅助空间 \(O(h)\)。
b_174_2；PDF 第 174 页 · b_174_3；PDF 第 174 页 · b_174_4；PDF 第 175 页 · b_175_0怎样用层次遍历求二叉树的最大宽度？（5.3 综合 11）¶
把结点及其层号一起入队；扫描时统计同一层的结点数，取最大值。
书中做法是用一个非循环队列保存全部已访问结点及层号，遍历结束后按层扫描计数。也可在每层开始时固定当前队长 levelSize，本层出队结束后更新最大值。
⚠️ 若照书中“遍历后再扫描队列”的实现，队列元素出队后仍要保留，因此不能用会覆盖旧位置的循环队列。时间 \(O(n)\)，空间 \(O(n)\)。
b_175_1；PDF 第 175 页 · b_175_2；PDF 第 176 页 · b_176_0；PDF 第 176 页 · b_176_1；PDF 第 176 页 · b_176_2已知满二叉树的先序序列，怎样直接得到后序序列？（5.3 综合 12）¶
一般二叉树只给先序不能唯一恢复；满二叉树的左右子树结点数相等，所以可以递归等分。
对先序片段 pre[l1..h1] 和对应后序片段 post[l2..h2]：
- 根
pre[l1]放到post[h2]。 - 令
half=(h1-l1)/2，先序中随后half个结点属于左子树，其余属于右子树。 - 分别递归写入后序片段的前半和后半。
每个结点写一次，时间 \(O(n)\)，递归栈 \(O(h)\)。
b_176_3；PDF 第 176 页 · b_176_4；PDF 第 176 页 · b_176_6；PDF 第 176 页 · b_176_7；PDF 第 176 页 · b_176_8；PDF 第 176 页 · b_176_9怎样把二叉树叶结点从左到右串成单链表？（5.3 综合 13）¶
先序、中序、后序对叶结点的访问顺序都保持从左到右，书中选中序递归。
- 设全局
head和pre，初值均为空。 - 遍历到叶结点：若
pre==NULL，它是首叶，令head=pre=p；否则令pre->rchild=p，再更新pre=p。 - 遍历结束后令最后一个叶结点的
rchild=NULL。
时间 \(O(n)\)，递归栈 \(O(h)\)。⚠️ 链接使用原叶结点的右指针域，会改变原树结构；题目若要求保留原树，就应另建链表结点。
b_176_14；PDF 第 176 页 · b_176_15；PDF 第 176 页 · b_176_16；PDF 第 177 页 · b_177_0；PDF 第 177 页 · b_177_1怎样递归判断两棵二叉树是否相似？（5.3 综合 14）¶
“相似”只比较结构，不比较数据值。递归分三种情况：
- 两棵都空：相似，返回真。
- 一空一非空：不相似，返回假。
- 两棵都非空：左子树互相相似且右子树互相相似时才返回真。
即
最坏时间 \(O(\min(n_1,n_2))\) 到发现差异为止，递归栈由较高树的高度决定。
b_177_2；PDF 第 177 页 · b_177_3；PDF 第 177 页 · b_177_4；PDF 第 177 页 · b_177_5二叉链表的 WPL 怎样写成递归算法？（2014 统考；5.3 综合 15）¶
有两条书中方法：
- 按定义：根深度取 0；遍历到叶结点时返回
weight*depth，非叶返回左右子树结果之和。 - 按分支权值：若每个分支结点权值等于其左右子树叶权之和，则整棵树的 WPL 等于所有分支结点权值之和，可用后序递归累计。
考试最稳的是第一种：参数携带深度，每个结点访问一次，时间 \(O(n)\)，递归栈 \(O(h)\)。
⚠️ 书后特别说明官方示例对度为 1 的结点可能出现空指针。对“按定义”方法，在入口先令空树返回 0，再判断叶结点即可；对“按分支权值”方法还必须只递归非空孩子，并把缺失孩子的叶权和视为 0，不能继续直接写 root->left->weight + root->right->weight。
b_177_6；PDF 第 177 页 · b_177_7；PDF 第 177 页 · b_177_9；PDF 第 177 页 · b_177_10；PDF 第 178 页 · b_178_0表达式树怎样输出带必要括号的等价中缀表达式？（2017 统考；5.3 综合 16）¶
以中序遍历为骨架：左子表达式 → 运算符 → 右子表达式。为显式保留树所规定的运算次序：
- 叶结点直接输出操作数，不加括号。
- 根结点对应整个表达式的最外层，不必加括号。
- 其余分支结点在遍历左子树前输出
(，遍历右子树后输出)。
可向递归函数传入深度 deep，用 deep>1 判断是否加括号。时间 \(O(n)\)，递归栈 \(O(h)\)。
⚠️ 题目要求“等价且由括号反映次序”，并不要求删到运算符优先级意义下的最少括号；按书中规则输出最稳。
b_178_10；PDF 第 178 页 · b_178_11；PDF 第 178 页 · b_178_12；PDF 第 179 页 · b_179_0；PDF 第 179 页 · b_179_1；PDF 第 179 页 · b_179_3顺序存储的二叉树，怎样尽可能高效地判断是否为二叉排序树？（2022 统考；5.3 综合 17）¶
首选“二叉排序树的中序序列严格递增”：
- 下标从 0 开始，左孩子为 \(2i+1\)，右孩子为 \(2i+2\)；越界或值为
-1时返回真。 - 中序递归左子树。
- 当前值必须严格大于已访问最大值
val，否则返回假；随后更新val。 - 中序递归右子树。
题设结点值均为正整数，可把 val 初始化为 0；更一般时应使用足够小的哨兵或“尚未访问”标志。最坏时间 \(O(\text{ElemNum})\)，递归栈 \(O(h)\)。
书中还给出自底向上维护子树最小值、最大值的解法；本题中序法更简洁。
b_179_5；PDF 第 179 页 · b_179_7；PDF 第 179 页 · b_179_8；PDF 第 179 页 · b_179_9；PDF 第 179 页 · b_179_12；PDF 第 180 页 · b_180_0；PDF 第 180 页 · b_180_1“左孩子—右兄弟”转换后，原树/森林中的数量关系怎样读？（2009、2011、2014 统考）¶
先把二叉树中的指针翻译回森林语义：左指针指第一个孩子，右指针指下一个兄弟。
- 2009 第 15 题：二叉树中连续两层父子关系，翻回森林后可能对应原父子关系，也可能对应兄弟链上的关系；I、II 可能，III 不可能，选 B。
- 2011 第 16 题：原树每个分支结点的最后一个孩子转换后无右孩子，根也无右孩子，所以无右孩子数 = 分支结点数 + 1 = \(2011-116+1=1896\)，选 D。
- 2014 第 17 题：森林叶结点没有孩子，转换后正好表现为二叉树中左孩子指针为空，选 C。
💡 数量题不必完整画图，只要逐个翻译“左空/右空”各代表什么。
b_189_3；PDF 第 189 页 · b_189_4；PDF 第 189 页 · b_189_5；PDF 第 189 页 · b_189_16；PDF 第 189 页 · b_189_18；PDF 第 189 页 · b_189_20；PDF 第 190 页 · b_190_0树和森林的遍历，怎样转换成对应二叉树的遍历？（2019、2020、2021 统考）¶
必须记住两组对应：
- 树/森林的先根遍历 ↔ 对应二叉树的先序遍历。
- 树/森林的后根遍历 ↔ 对应二叉树的中序遍历。
据此：
- 2019 第 18 题选 B：树的后根 = 二叉树的中序。
- 2020 第 19 题：把给定先根、后根当成二叉树的先序、中序，重建后得到后序
b,f,e,d,c,a，选 C。 - 2021 第 20 题：由二叉树先序、中序重建后，从根沿右孩子链数森林各树根，共 3 棵，选 C。
⚠️ 森林中各树的根在转换后二叉树里沿根的右链相连。
b_190_1；PDF 第 190 页 · b_190_2；PDF 第 190 页 · b_190_4；PDF 第 190 页 · b_190_5；PDF 第 190 页 · b_190_7；PDF 第 190 页 · b_190_8；PDF 第 190 页 · b_190_10关于完全二叉树、森林转换和表达式树，怎样快速排除概念陷阱？（2025 统考）¶
2025 第 21 题选 B：任意森林都能按“左孩子—右兄弟”唯一转换成一棵二叉树。
其余三项的错因：
- 完全二叉树至多有一个度为 1 的结点，并非一定没有。
- 二叉树只有 \(n_0=n_2+1\)；分支结点还包含度为 1 的结点，所以分支结点总数不一定比叶结点少。
- 表达式树根保存的是最后执行的运算符，不是最先执行的。
💡 多命题选择题应逐句回到定义，不要把“满二叉树”的性质偷换给“完全二叉树”。
b_190_11；PDF 第 190 页 · b_190_12；PDF 第 190 页 · b_190_13给定树的先根和后根序列，能否唯一确定这棵树？（5.4 综合 01）¶
按本书的有序树口径，可以唯一确定。
理由是：树的先根序列等于其左孩子—右兄弟二叉树的先序序列；树的后根序列等于该二叉树的中序序列。二叉树的“先序 + 中序”能唯一确定结构，因此可先唯一重建对应二叉树，再唯一还原为原树。
⚠️ 证明时不要直接套“二叉树先序 + 后序不能唯一确定”；这里树的后根映射到对应二叉树的中序，不是后序。
b_191_1；PDF 第 191 页 · b_191_2；PDF 第 191 页 · b_191_3；PDF 第 191 页 · b_191_5；PDF 第 191 页 · b_191_6手工把森林转换成二叉树，三步怎样保证不漏边？（5.4 综合 02）¶
按固定顺序画：
- 先把森林中每棵树的根也视为兄弟，并连接各兄弟。
- 对每个结点，只保留它与第一个孩子的连线；其他孩子改由兄弟链连接。
- 以第一棵树的根为轴顺时针旋转 \(45^\circ\)，得到“左孩子—右兄弟”的二叉树。
自检：每个结点的左指针只能指向第一个孩子，右指针只能指向下一个兄弟；第一棵树之后各树的根应出现在根的右链上。
b_191_7；PDF 第 191 页 · b_191_8；PDF 第 191 页 · b_191_9已知二叉树的先序和中序，怎样画出对应森林？（5.4 综合 03）¶
分两段完成：
- 由先序首元素确定根，在中序中切分左右子树，递归重建二叉树。
- 还原森林：若 \(x\) 是 \(y\) 的左孩子，则 \(x\) 及其连续右兄弟链都应成为 \(y\) 的孩子；把这些结点分别与 \(y\) 连线，再删除二叉树中表示兄弟关系的右孩子边。
⚠️ 二叉树根的连续右链对应森林中不同树的根；不要把它们误接成第一棵树的孩子。
b_191_10；PDF 第 191 页 · b_191_11；PDF 第 191 页 · b_191_12孩子兄弟链表中，怎样递归统计森林叶结点数？（5.4 综合 04）¶
在孩子兄弟表示法中，fch==NULL 表示当前结点没有孩子，因此它是原森林中的叶结点。
这里必须同时递归“第一个孩子”和“下一个兄弟”，因为一个指针进入当前结点的孩子森林，另一个指针进入与当前结点并列的剩余森林。时间 \(O(n)\)，递归栈最坏 \(O(n)\)。
b_192_0；PDF 第 192 页 · b_192_1；PDF 第 192 页 · b_192_2；PDF 第 192 页 · b_192_3孩子兄弟链表中，为什么树高是 max(孩子高+1，兄弟高)？（5.4 综合 05）¶
设 Height(t) 处理以 \(t\) 开始的孩子兄弟结构：
- 空指针返回 0。
- 进入
firstchild才真正向原树的下一层走，所以候选高度是Height(firstchild)+1。 - 进入
nextsibling仍处于原树同一层，所以候选高度是Height(nextsibling)，不能再加 1。 - 返回二者最大值。
⚠️ 最常见错误是给兄弟子树也加 1，导致把横向兄弟链误算成深度。
b_192_4；PDF 第 192 页 · b_192_5；PDF 第 192 页 · b_192_6哈夫曼树的结构性质怎样快速判断？（2010、2015、2019 统考）¶
- 2010 第 14 题：哈夫曼树不一定是完全二叉树，错误项为 A；它没有度为 1 的结点，最小两权结点可作为兄弟，父权等于孩子权之和。
- 2015 第 16 题：沿同一棵哈夫曼树路径检查“父权 = 两孩子权之和”及根的左右子树权和，只有 D 可成立。
- 2019 第 19 题：\(n\) 个符号产生 \(n\) 个叶和 \(n-1\) 个分支，总结点数 \(2n-1=115\)，故 \(n=58\)，选 C。
⚠️ 哈夫曼树可能不唯一，但最小 WPL 相同；左右孩子次序也不影响 WPL。
b_201_5；PDF 第 201 页 · b_201_6；PDF 第 201 页 · b_201_9；PDF 第 201 页 · b_201_10；PDF 第 201 页 · b_201_16；PDF 第 201 页 · b_201_17前缀编码、哈夫曼译码和编码方案判断怎样做？（2014、2017、2018 统考）¶
- 2014 第 15 题：逐个检查是否有码字成为另一较长码字的前缀；D 中
110是1100的前缀，故选 D。 - 2017 第 17 题：从左到右按已有码字贪心切分；前缀特性保证每次到叶就唯一译出，结果为
afeefgd，选 D。 - 2018 第 18 题：先按频次构造哈夫曼树，再比较各字符的码长与共同前缀关系；可行方案为 A。
💡 只检查“码长不同”不够；前缀码允许不同长度，真正禁止的是某个完整码字落在另一码字的路径中途。
b_201_7；PDF 第 201 页 · b_201_8；PDF 第 201 页 · b_201_11；PDF 第 201 页 · b_201_12；PDF 第 201 页 · b_201_13；PDF 第 201 页 · b_201_14哈夫曼树的 WPL、平均码长和码长分布怎样从合并过程读出？（2021、2023、2025 统考）¶
每次取当前最小的两个权合并；所有新产生权值之和就是 WPL，叶深度就是码长。
- 2021 第 20 题：权值 \(10,12,16,21,30\) 构造后 WPL 为 200，选 B。
- 2023 第 22 题：4 个字符码长 3、2 个字符码长 2，加权平均长度为 \([(3+4+5+6)\times3+(8+10)\times2]/36=2.5\)，选 B。
- 2025 第 23 题：依次合并 \(2+3,4+5,6+8,9+10,11+14,19+25\)；码长不小于 3 的字符为 \(4,2,3,6,8\)，共 5 个，选 D。
💡 要统计码长，可记录每个初始权值所在合并树后续又被合并了几次。
b_202_0；PDF 第 202 页 · b_202_1；PDF 第 202 页 · b_202_2；PDF 第 202 页 · b_202_9；PDF 第 202 页 · b_202_10；PDF 第 202 页 · b_202_11；PDF 第 202 页 · b_202_12；PDF 第 202 页 · b_202_13；PDF 第 202 页 · b_202_14哈夫曼编码树和定长编码树，哪些性质一定不同？（2022 统考）¶
定长编码中所有字符的码长相同，所以它们在编码二叉树中必位于同一层且都是叶结点；因此 2022 第 21 题选 D。
其余说法都不一定：
- 两棵编码树结点数未必相同。
- 哈夫曼树高度未必严格大于定长编码树。
- 频次不同的字符在哈夫曼树中也可能具有相同码长、位于同层。
⚠️ “频次越大，码长越短”是整体优化倾向，不是任意两字符之间都严格单调。
b_202_3；PDF 第 202 页 · b_202_4；PDF 第 202 页 · b_202_5；PDF 第 202 页 · b_202_6；PDF 第 202 页 · b_202_7；PDF 第 202 页 · b_202_8给定权集，怎样构造哈夫曼树并计算 WPL？（5.5 综合 01）¶
权集 \(\{5,7,2,3,6,8,9\}\) 每次选两个最小权值合并，并把新权值放回集合，直到只剩一个根。左右次序可互换，因此树形不唯一。
本题构造后，各叶深度可读为：\(2,3\) 的深度为 4，\(5,6,7\) 的深度为 3，\(8,9\) 的深度为 2：
💡 也可直接把每次合并产生的新权值相加，结果同样是 108。
b_203_1；PDF 第 203 页 · b_203_2；PDF 第 203 页 · b_203_3；PDF 第 203 页 · b_203_4；PDF 第 203 页 · b_203_5；PDF 第 203 页 · b_203_6多个不等长有序表怎样安排两两合并，才能使最坏比较次数最少？（2012 统考；5.5 综合 02）¶
把表长当作叶权，采用哈夫曼思想：每次合并当前最短的两个表。
本题顺序为：\(10+35=45\)，\(40+45=85\)，\(50+60=110\)，\(85+110=195\)，\(195+200=395\)。
长度分别为 \(m,n\) 的有序表合并，最坏比较 \(m+n-1\) 次，因此总次数为
一般策略：反复选择两个最短表合并。因为越早合并的元素会在后续多次参与比较，这正对应“让较小权值承担不浅于较大权值的层数”的最小 WPL 原理；权值不同也允许最终位于同层。
b_203_8；PDF 第 203 页 · b_203_10；PDF 第 203 页 · b_203_11；PDF 第 203 页 · b_203_12；PDF 第 203 页 · b_203_13；PDF 第 203 页 · b_203_14；PDF 第 203 页 · b_203_15；PDF 第 204 页 · b_204_0；PDF 第 204 页 · b_204_1怎样保存、译码并判定一组不等长二进制编码是否具有前缀特性？（2020 统考；5.5 综合 03）¶
使用二叉字典树：左、右边分别表示 0、1，字符只保存在叶结点。
- 译码：从根扫描比特并沿 0/1 边下移；到叶时输出字符并回到根，直到输入结束。
- 判定/建树：逐个插入码字。若尚未读完当前码字就遇到已有叶结点，说明已有短码是当前码的前缀；若当前码全部读完却没有创建任何新结点，则要看落点：落在内部结点说明当前码是已有长码的前缀，落在叶结点说明与已有码重复。三种情况都失败。
- 若最后一位创建新叶且全体码字均通过，则具有前缀特性。
时间与所有码字总长度成正比，树高不超过最长码长 \(L\)。
b_204_2；PDF 第 204 页 · b_204_3；PDF 第 204 页 · b_204_4；PDF 第 204 页 · b_204_5；PDF 第 204 页 · b_204_6；PDF 第 204 页 · b_204_7；PDF 第 204 页 · b_204_8；PDF 第 204 页 · b_204_9；PDF 第 204 页 · b_204_10；PDF 第 204 页 · b_204_11【原书归纳总结与思维拓展】第5章¶
树的数量题，最稳的“建模顺序”是什么？¶
先列三张账，再消元：
- 结点账：\(n=\sum n_i\)。
- 出度账：\(e=\sum i n_i\)。
- 连通账：一棵树 \(n=e+1\)；含 \(k\) 棵树的森林 \(n=e+k\)。
二叉树再加特式 \(n_0=n_2+1\)；正则 \(k\) 叉树只保留 \(n_0,n_k\)。极值题则先画形态：最小高度让每层尽量满，最大高度让除必要分叉外每层尽量只有一个继续向下的结点。
💡 先建模再代数，能避免“看见完全二叉树就乱套编号公式”。
b_141_13；PDF 第 141 页 · b_141_14；PDF 第 141 页 · b_141_15；PDF 第 141 页 · b_141_16；PDF 第 141 页 · b_141_17完全二叉树的计数题，怎样按固定顺序做？¶
建议按以下顺序：
- 先判断最后一层是否满，确定高度范围。
- 用层序编号：最后一个分支结点是 \(\lfloor n/2\rfloor\)，叶结点从其后开始。
- 若只给 \(n_0\)，用 \(n=2n_0+n_1-1\)，并记住 \(n_1\in\{0,1\}\)。
- 最后用奇偶性或最后一层形态校验。
⚠️ 完全二叉树只有最底层可能不满，前面各层必须满；这是绝大多数极值计算的起点。
b_151_5；PDF 第 151 页 · b_151_6；PDF 第 149 页 · b_149_9；PDF 第 149 页 · b_149_10二叉树算法题怎样从“三个访问位置”快速落笔？¶
把递归框架先写出来，再决定处理当前结点的语句放在哪：
- 位置①：先序，适合携带路径、层次和首次访问状态。
- 位置②：中序，适合二叉排序树有序性、表达式输出。
- 位置③：后序，适合删除、释放、汇总左右子树结果。
层次、宽度、完全性等问题则换成队列。答题时先说明“遍历策略 + 额外状态 + 终止条件”，再写代码。
b_204_14；PDF 第 204 页 · b_204_15；PDF 第 204 页 · b_204_16；PDF 第 205 页 · b_205_0；PDF 第 205 页 · b_205_1线索二叉树找前驱后继时，哪两类边界最容易错？¶
- 中序线索树中，若结点有左孩子，其前驱是左子树中最右结点，不一定是最右叶结点。
- 后序线索树中，叶结点若是双亲的右孩子，或虽是左孩子但双亲无右子树，则后继是双亲；但一般后序后继常需回溯双亲，单靠二叉线索不总能高效得到。
统一检查顺序：先看对应孩子是否真实存在；若不存在才使用线索；最后再对照完整遍历序列验证。
b_168_0；PDF 第 168 页 · b_168_1；PDF 第 168 页 · b_168_2；PDF 第 168 页 · b_168_3；PDF 第 168 页 · b_168_4“左孩子—右兄弟”怎样在图和代码之间双向翻译？¶
看到二叉树指针时立刻翻译：
left：当前结点的第一个孩子；left==NULL：原树中的叶结点。right：当前结点的下一个兄弟；right==NULL：当前兄弟组的最后一个结点。- 根的连续右链：森林中各棵树的根。
遍历对应也随之得到：树/森林先根 = 二叉树先序；树/森林后根 = 二叉树中序。数量、遍历、递归算法都先做这层语义翻译，再套二叉树模板。
b_188_7；PDF 第 188 页 · b_188_8；PDF 第 188 页 · b_188_9；PDF 第 188 页 · b_188_10；PDF 第 188 页 · b_188_14哈夫曼树和最优合并，为什么本质上是同一个贪心模型？¶
一个对象越早被合并，之后参与累计的次数越多，相当于在合并树中深度越大。要使总成本最小，应优先让较小权值承担较深层、避免让小权值比大权值更靠近根，因此每一步选择当前最小的两个权合并；并列或结构约束下，不同权值仍可同层。
- 编码中：权值是字符频次，总成本是 WPL。
- 多路表合并中：权值是表长，总成本是所有元素反复参与比较的累计代价。
哈夫曼树可能因并列权值而不唯一，但最小代价相同。
b_203_5；PDF 第 203 页 · b_203_6；PDF 第 204 页 · b_204_1并查集题应抓住哪三个动作和两个优化？¶
并查集用双亲表示法存储一组互不相交的树：
Find(x)沿双亲找到根，根是集合标志。Union(a,b)先找两根，不同才合并。- 判环/连通：处理无向边 \((u,v)\) 时，若两端根相同则加边成环；否则合并。Kruskal 正是用它排除成环边。
两种优化是按规模/高度合并和路径压缩。未优化时最坏树高可达 \(n\)，一次查找为 \(O(n)\)；不能机械写成 \(O(\log n)\)。
b_201_1；PDF 第 201 页 · b_201_2；PDF 第 201 页 · b_201_3；PDF 第 201 页 · b_201_4根到叶路径和等于 data，怎样用先序递归和回溯解决？¶
维护一个保存当前路径的数组或栈，以及路径和 sum：
- 先序访问当前结点时，把它压入路径并加入
sum。 - 若当前是叶结点且
sum==data，输出整条路径。 - 递归左右子树。
- 返回双亲前弹出当前结点，并从
sum中减去它的值。
⚠️ 回溯撤销不可漏，否则右子树会继承左子树的路径和。忽略打印本身时，遍历时间为 \(O(n)\)；若计入输出，时间应写成 \(O(n+\text{所有输出路径的总长度})\)，最坏可达 \(O(nh)\)。路径栈与递归栈均不超过树高 \(h\)。
b_205_13；PDF 第 205 页 · b_205_14；PDF 第 205 页 · b_205_15；PDF 第 205 页 · b_205_16；PDF 第 205 页 · b_205_17算法题以王道/考试口径为主时，代码边界应怎样处理？¶
先保证书中评分核心完整：遍历次序正确、递归含义明确、状态更新位置正确。若时间允许，再补工程边界，例如空树、度为 1 的结点、全局变量重置和指针置空。
本章 WPL 官方示例的核心思想正确，但书后明确指出：对度为 1 的结点会遇到空指针。“按定义”递归可在入口先处理 root==NULL；“按分支权值”递归还要分别判左右孩子，缺失一侧按 0 计，不能直接解引用两个孩子。这样既保留王道/统考的解题口径，也补全明显的边界。
b_178_8；PDF 第 178 页 · b_178_9【易混点】第5章成对概念对照¶
| 概念 A | 概念 B | 一句话切分 |
|---|---|---|
| 结点的深度 | 结点的高度 | 自顶向下数层次 vs 以它为根的子树高度 |
| 结点的度 | 树的度 | 孩子个数 vs 所有结点度的最大值 |
| 兄弟 | 堂兄弟 | 同一双亲 vs 双亲在同一层 |
| 二叉树 | 度为 2 的有序树 | 可为空、左右固有 vs 至少 3 结点、只有一个孩子时不分左右 |
| 满二叉树 | 完全二叉树 | 2^h − 1 个结点 vs 与满二叉树编号 1~n 一一对应 |
| 正则二叉树 | 完全二叉树 | 只有度 0 和 2 vs 编号连续 |
| n₀ = n₂ + 1 | n = n₀+n₁+n₂ | 两个式子联立解题 |
| 顺序存储 | 二叉链表 | 只适合完全/满二叉树 vs 通用，有 n+1 个空链域 |
| 先序/中序/后序 | — | "序"指根的位置，左右顺序永远先左后右 |
| 中序 + 任一种 | 先序/后序/层序两两组合 | 可唯一确定 vs 通常不能 |
| ltag=0 | ltag=1 | 指向左孩子 vs 指向前驱 |
| 中序线索找后继 | 后序线索找后继 | rtag=0 时取右子树最左下 vs 要分三种情况且常需父指针 |
| 双亲表示法 | 孩子表示法 | 查双亲快查孩子慢 vs 查孩子快查双亲慢 |
| 树的先根/后根 | 森林的先序/中序 | 分别对应二叉树的先序 / 中序 |
| 哈夫曼树形态 | 哈夫曼树 WPL | 可能不唯一 vs 一定唯一且最小 |
| 固定长度编码 | 哈夫曼编码 | 每字符等长 vs 高频字符通常不长于低频字符（允许等长），前缀编码 |
| 按大小合并 | 路径压缩 | 深度 ≤ ⌊log₂n⌋+1 vs 配合使用降到 O(α(n)) |
【必背数字】第5章¶
| 数字 | 含义 |
|---|---|
| n − 1 | n 个结点的树的边数 |
| m^(i−1) / (m^h−1)/(m−1) | 度为 m 的树第 i 层最多结点数 / 高 h 最多结点数 |
| ⌈log_m(n(m−1)+1)⌉ / n−m+1 | 度为 m、n 结点的树的最小 / 最大高度 |
| n₀ = n₂ + 1 | 二叉树最重要的性质 |
| 2^(k−1) / 2^h − 1 | 二叉树第 k 层最多 / 高 h 最多结点数 |
| ⌈log₂(n+1)⌉ 或 ⌊log₂n⌋+1 | 完全二叉树的高度 |
| ⌊n/2⌋ | 完全二叉树最后一个分支结点的编号 |
| ⌊i/2⌋、2i、2i+1、⌊log₂i⌋+1 | 完全二叉树的双亲 / 左孩子 / 右孩子 / 层次 |
| n + 1 | n 个结点的二叉链表中的空链域数 |
| O(n) / O(n) | 遍历的时间复杂度 / 最坏空间复杂度（单支树） |
| 2n − 1 | 含 n 个叶结点的哈夫曼树的结点总数 |
| WPL = Σwᵢlᵢ | 带权路径长度 |
| 224 位 vs 300 位，压缩约 25% | 教材哈夫曼编码算例 |
| −1 | 并查集初始化时数组各位置的值 |
| O(d) / O(1) | 并查集 Find / Union 的基本复杂度 |
| ⌊log₂n⌋+1 / O(α(n))，α(n) ≤ 4 | 按大小合并后 / 再加路径压缩后的深度 |
【口诀速记】第5章¶
| 维度 | 口诀 | 解释 |
|---|---|---|
| 二叉树第一性质 | n₀ = n₂ + 1 | 配合 n = n₀+n₁+n₂ 联立解题，见到叶结点数就写 |
| 完全二叉树编号 | 半双倍、双加一 | 双亲 ⌊i/2⌋、左孩子 2i、右孩子 2i+1、层次 ⌊log₂i⌋+1 |
| 最后分支结点 | ⌊n/2⌋ | i ≤ ⌊n/2⌋ 是分支结点，否则是叶结点 |
| 空链域 | n + 1 | n 个结点的二叉链表，线索二叉树就用它 |
| 还原二叉树 | 无中序不还原 | 必须"中序 + 先序/后序/层序"之一 |
| 三种遍历对应 | 先根=先序=先序，后根=中序=中序 | 树 / 森林 / 二叉树三者的对应关系 |
| 树转二叉树 | 左孩子-右兄弟 | 转出来的二叉树根一定无右子树 |
| 哈夫曼树 | 结点 2n−1，没有度为 1 的 | WPL = Σwᵢlᵢ = 编码总长度；形态不唯一但 WPL 唯一 |
| 并查集 | 小树并大树，路径要压平 | 分别把深度降到 ⌊log₂n⌋+1 和 O(α(n)) |
b_136_3；PDF 第 136 页 · b_136_4【解题路线】第5章：树题怎么下手¶
- ① 看到"度为 m 的树"还是"m 叉树" —— ⚠️ 前者是所有结点度的最大值为 m，后者是每个结点至多 m 个孩子，公式不同
- ② 题目出现叶结点数 → ⚠️ 立刻写 n₀ = n₂ + 1，配合 n = n₀ + n₁ + n₂ 联立，两个方程解两个未知数
- ③ 完全二叉树编号题 → ⌊i/2⌋ 双亲、2i 左孩子、2i+1 右孩子、⌊log₂i⌋+1 层次；⚠️ 最后一个分支结点是 ⌊n/2⌋
- ④ 给遍历序列还原树 → ⚠️ 必须有中序；先在另一序列里找根（先序取首 / 后序取尾 / 层序取首），再用它劈开中序，递归
- ⑤ 哈夫曼题 → 每次取两个最小权值合并；⚠️ n 个叶结点 → 结点总数 2n−1、无度为 1 的结点；WPL = Σwᵢlᵢ = 编码总长度
- ⑥ 树/森林/二叉树互转 → ⚠️ 左孩子-右兄弟；遍历对应关系：树先根 = 森林先序 = 二叉树先序；树后根 = 森林中序 = 二叉树中序
💡 线索二叉树题先问自己：是哪种线索（先序/中序/后序），再看 ltag/rtag 的取值。
b_136_5；PDF 第 136 页 · b_136_6