【软考备考】数据结构详解：二叉树的性质与遍历、堆与栈队列（附 10 道练习）

上午题知识版图的最后一块高地数据结构。这块每年 2~4 分考法集中在二叉树性质叶子节点和度为 2 节点的关系一条公式走天下遍历序列给两种遍历序列还原二叉树四步套路堆为什么是顶最大却整体无序概念坑集中地栈与队列出栈序列哪个不可能模拟判断。一、二叉树的三个计数性质第 i 层最多 2^(i-1) 个节点第 1 层 1 个第 2 层 2 个第 3 层 4 个……深度为 k 的二叉树最多 2^k − 1 个节点满二叉树的情形任意二叉树中叶子节点数 n₀ n₂ 1n₂ 是度为 2 的节点数。第三条是软考的宠儿推导很简单理解了就忘不掉总节点 n n₀n₁n₂除根外每个节点头上都顶着一条边所以总边数 n−1而边只能从 n₁发 1 条和 n₂发 2 条发出总边数 n₁2n₂。两式一联立n₁ 恰好消掉得到n₀ n₂1——叶子永远比双孩节点多一个和 n₁ 无关。二、完全二叉树数组编号的规律满二叉树的最后一层只缺右边若干节点左边必须连续排满就是完全二叉树。它的价值在于可以无缝塞进数组编号规律节点 i从 1 开始左孩子 2i右孩子 2i1父节点 ⌊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~51.二叉树前序遍历的访问顺序是 。A. 左子树 → 根 → 右子树 B. 根 → 左子树 → 右子树 C. 左子树 → 右子树 → 根 D. 右子树 → 根 → 左子树2.栈的存取特点是 。A. 先进先出 B. 只能在中间插入 C. 按优先级进出 D. 先进后出3.完全二叉树按层从 1 编号节点 i 的左孩子编号为 。A. 2i B. 2i1 C. ⌊i/2⌋ D. i14.对二叉排序树进行中序遍历得到的序列是 。A. 无序序列 B. 层次序列 C. 升序序列 D. 逆序序列5.大顶堆的堆顶元素是堆中所有元素的 。A. 最小值 B. 最大值 C. 中间值 D. 任意值进阶题6~10带坑6.某二叉树中有 10 个度为 2 的节点则该二叉树的叶子节点数为 。A. 10 B. 9 C. 20 D. 117.某二叉树的前序遍历序列为 ABDEC中序遍历序列为 DBEAC则其后序遍历序列为 。A. DBECA B. DEBCA C. ABEDC D. DCEBA8.仅已知某二叉树的前序遍历序列和后序遍历序列能否唯一确定该二叉树 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、右 2i1、父 ⌊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、中序 DBEB 为根左 D 右 E → 后序DEBCA。建议自己在草稿纸上把这棵树画出来对一遍。8. A前序 后序不能唯一确定二叉树——没有中序提供左右分家的信息单孩节点挂在左边还是右边无法区分。规律两种序列里必须含中序。9. D本题大坑。D 是堆的定义父 ≥ 子。A、B 同义反复地错——堆只约束父子、不约束兄弟整体并不有序堆里完全可能左子树的某个节点比右子树的还小。堆顶最大 ≠ 全树有序考的就是这个。10. C模拟312想第一个出 31、2、3 必须全部入栈栈顶到栈底为 3、2、1——出 3 之后只能出 2出不了 1故312不可能。其余三个都能模拟出来123入一个出一个、231、321全入再全出。八、五句话带走二叉树计数第 i 层最多 2^(i-1) 个深度 k 最多 2^k−1 个n₀ n₂ 1完全二叉树编号左 2i、右 2i1、父 ⌊i/2⌋——堆的存储地基遍历还原四步前序找根、中序分家、递归、拼装前后不能唯一还原必须含中序堆父 ≥ 子 大顶堆顶最大但整体无序栈先进后出、队列先进先出出栈序列拿不准就逐个模拟。下一篇预告数据结构收官篇——查找与排序二分查找为什么必须先有序、八大排序算法的时间复杂度表、以及哪些排序是稳定的这个千年考点快排、堆排为什么不稳冒泡、归并为什么稳。