【软考备考】数据结构详解：二叉树的性质与遍历、堆与栈队列（附 10 道练习）
上午题知识版图的最后一块高地：数据结构。这块每年 2~4 分，考法集中在：
二叉树性质：叶子节点和度为 2 节点的关系（一条公式走天下）；
遍历序列：给两种遍历序列还原二叉树（四步套路）；
堆：为什么是"顶最大"却"整体无序"（概念坑集中地）；
栈与队列：出栈序列哪个不可能（模拟判断）。
一、二叉树的三个计数性质
第 i 层最多 2^(i-1) 个节点（第 1 层 1 个，第 2 层 2 个，第 3 层 4 个……）；
深度为 k 的二叉树最多 2^k − 1 个节点（满二叉树的情形）；
任意二叉树中，叶子节点数 n₀ = n₂ + 1（n₂ 是度为 2 的节点数）。
第三条是软考的宠儿，推导很简单，理解了就忘不掉：总节点 n = n₀+n₁+n₂；除根外每个节点头上都顶着一条边，所以总边数 = n−1；而边只能从 n₁（发 1 条）和 n₂（发 2 条）发出，总边数 = n₁+2n₂。两式一联立，n₁ 恰好消掉，得到n₀ = n₂+1——叶子永远比"双孩节点"多一个，和 n₁ 无关。
二、完全二叉树：数组编号的规律
满二叉树的最后一层只缺右边若干节点（左边必须连续排满），就是完全二叉树。它的价值在于：可以无缝塞进数组，编号规律：
节点 i（从 1 开始）：左孩子 = 2i，右孩子 = 2i+1，父节点 = ⌊i/2⌋
不用指针，纯按下标算，就能在树里上蹿下跳——堆就是用数组存储的完全二叉树，这套编号是堆操作的地基。
三、遍历与还原：四步套路
三种深度优先遍历，差别只在"根什么时候访问"（左右永远是先左后右）：
前序：根左右；
中序：左根右；
后序：左右根。
由两种遍历序列还原二叉树的套路（以前序 + 中序为例）：
前序：A B D E C 中序：D B E A C 第1步：前序第一个 = 根 → A 是根 第2步：在中序里找 A → 左边 DBE 是左子树，右边 C 是右子树 第3步：递归处理左子树：前序 BDE、中序 DBE → B 是根，中序里 B 左 D、右 E 第4步：拼起来： A / \ B C / \ D E 后序遍历：D E B C A能/不能唯一确定的结论（直接考）：
| 已知序列 | 能否唯一还原 |
|---|---|
| 前序 + 中序 | ✓ |
| 中序 + 后序 | ✓ |
| 前序 + 后序 | ✗（分不清某节点是左孩子还是右孩子） |
规律：必须含中序——中序提供"左右分家"的信息，前序/后序只提供"谁是根"。
四、堆：顶最大，但整体无序
大顶堆：每个父节点的值≥两个孩子；小顶堆反之。它是一棵满足这个大小关系的完全二叉树，用数组存。
本篇最大的概念坑：堆只约束父子关系，不约束兄弟关系。所以：
堆顶一定是最大（小）值 ✓；
但整棵树不是有序的✗——左子树和右子树之间谁大谁小，堆根本不管。
"堆顶最大 ≠ 全树有序"，这句话值 1 分。正因为取顶快（O(1)）、调整快（O(log n)），堆被用于堆排序、优先队列、Top-K 问题。
五、栈与队列：两句话加一类题
栈：先进后出（弹盘子），应用：函数调用、递归、表达式求值；
队列：先进先出（排队买票）；循环队列长度 =(rear − front + 容量) % 容量。
出栈序列判断是固定题型：元素 1,2,3 依次入栈（入栈过程中随时可以出栈），哪个出栈序列不可能？逐个模拟，比如序列312：要第一个出 3，必须 1、2、3 全入栈，此时栈里从顶到底是 3、2、1——出完 3 只能出 2，轮不到 1。312不可能。判断诀窍：出栈序列中，若某元素之后要出比它先入栈的元素，那些元素必须按逆序出来。
六、10 道练习题
基础题（1~5）
1.二叉树前序遍历的访问顺序是（ ）。
A. 左子树 → 根 → 右子树 B. 根 → 左子树 → 右子树 C. 左子树 → 右子树 → 根 D. 右子树 → 根 → 左子树
2.栈的存取特点是（ ）。
A. 先进先出 B. 只能在中间插入 C. 按优先级进出 D. 先进后出
3.完全二叉树按层从 1 编号，节点 i 的左孩子编号为（ ）。
A. 2i B. 2i+1 C. ⌊i/2⌋ D. i+1
4.对二叉排序树进行中序遍历，得到的序列是（ ）。
A. 无序序列 B. 层次序列 C. 升序序列 D. 逆序序列
5.大顶堆的堆顶元素是堆中所有元素的（ ）。
A. 最小值 B. 最大值 C. 中间值 D. 任意值
进阶题（6~10，带坑）
6.某二叉树中有 10 个度为 2 的节点，则该二叉树的叶子节点数为（ ）。
A. 10 B. 9 C. 20 D. 11
7.某二叉树的前序遍历序列为 ABDEC，中序遍历序列为 DBEAC，则其后序遍历序列为（ ）。
A. DBECA B. DEBCA C. ABEDC D. DCEBA
8.仅已知某二叉树的前序遍历序列和后序遍历序列，能否唯一确定该二叉树？（ ）
A. 不能唯一确定 B. 能唯一确定 C. 需要补充层次遍历才能确定 D. 一定能
9.关于大顶堆，下列说法正确的是（ ）。
A. 堆中所有元素按从大到小排列 B. 堆中元素整体完全有序 C. 任意子树的根节点不大于其兄弟节点 D. 每个父节点的值都不小于其孩子节点的值
10.元素 1、2、3 依次入栈（入栈过程中可随时出栈），下列出栈序列中不可能出现的是（ ）。
A. 123 B. 231 C. 312 D. 321
七、答案与详解
1. B前序 =根左右。三种遍历左永远在右前，只是根的位置：前序根最前、中序根中间、后序根最后。
2. D栈 =先进后出（FILO），弹盘子。先进先出是队列，别串。
3. A编号规律：左 2i、右 2i+1、父 ⌊i/2⌋。三个公式是一套，记一个就能推另外两个。
4. C二叉排序树中序遍历 = 升序序列——这是 BST 的招牌性质（左 < 根 < 右，中序正好"左根右"），软考反复考。
5. B大顶堆堆顶 =最大值；小顶堆堆顶 = 最小值。
6. D套公式n₀ = n₂ + 1 = 10 + 1 = 11。和度为 1 的节点数量完全无关——推导时 n₁ 被消掉了，所以题目给不给 n₁ 都是干扰。
7. B四步还原：前序首元素 A 为根 → 中序中 A 左 DBE（左子树）、右 C（右子树）→ 左子树前序 BDE、中序 DBE，B 为根，左 D 右 E → 后序DEBCA。建议自己在草稿纸上把这棵树画出来对一遍。
8. A前序 + 后序不能唯一确定二叉树——没有中序提供"左右分家"的信息，单孩节点挂在左边还是右边无法区分。规律：两种序列里必须含中序。
9. D本题大坑。D 是堆的定义：父 ≥ 子。A、B 同义反复地错——堆只约束父子、不约束兄弟，整体并不有序（堆里完全可能左子树的某个节点比右子树的还小）。"堆顶最大 ≠ 全树有序"，考的就是这个。
10. C模拟312：想第一个出 3，1、2、3 必须全部入栈，栈顶到栈底为 3、2、1——出 3 之后只能出 2，出不了 1，故312不可能。其余三个都能模拟出来：123（入一个出一个）、231、321（全入再全出）。
八、五句话带走
二叉树计数：第 i 层最多 2^(i-1) 个，深度 k 最多 2^k−1 个，n₀ = n₂ + 1；
完全二叉树编号：左 2i、右 2i+1、父 ⌊i/2⌋——堆的存储地基；
遍历还原四步：前序找根、中序分家、递归、拼装；前+后不能唯一还原，必须含中序；
堆：父 ≥ 子 = 大顶堆；顶最大但整体无序；
栈先进后出、队列先进先出；出栈序列拿不准就逐个模拟。
下一篇预告：数据结构收官篇——查找与排序：二分查找为什么必须先有序、八大排序算法的时间复杂度表、以及"哪些排序是稳定的"这个千年考点（快排、堆排为什么不稳，冒泡、归并为什么稳）。
