板块六 · 树与搜索
一、板块定位
板块五是「一条线的算法」(数、序列、串),板块六开始处理「有分支、有层次的结构」:栈、队列、树、图,以及在上面跑的搜索(DFS/BFS)和动态规划。这一级是五级里考点最多的一级(12 个),也是孩子第一次同时面对「数据结构」和「算法策略」两个词——学完他才算真正入了算法的门。
关于家长最常问的「为什么 DP 提前在六级露面」:GESP 六级大纲本来就包含简单动态规划(cpp610)和 01/完全背包(cpp611),这是官方要求,不是我们抢跑。教学上它放在 BFS 之后也很自然——孩子刚学完「一圈圈扩的最短路」,紧接着学「记账本式的递推优化」,两种「不走回头路」的思想互相印证。七级的二维 DP、LIS/LCS 都建在这一课的地基上。
- 适用年龄:11~14 岁(小学 5 年级 ~ 初二),已通过 GESP 五级
- 前置要求:递归能独立写且不晕(板块五第 8~11 课达标);队列的 head/tail 操作熟练;理解「第一次到某点即最短」的 BFS 性质
- 总课时:35 次 × 2 小时 = 70 小时(约 1 个学年,每周 1 次)
- 对应考点:cpp601 ~ cpp612(GESP 六级大纲 12 个考点,全覆盖)
二、课程目标(学完必须达到)
| 维度 | 具体标准 | 验证方式 |
|---|---|---|
| 知识 | 说出栈和队列的区别及各自典型应用;说出三种遍历的顺序;说出 DFS 与 BFS 分别适合什么问题 | 第 34 课模拟考选择判断部分 ≥70 分 |
| 技能 | 能独立完成迷宫最短路(BFS + dist 数组);能独立写出 01 背包(f[j] 倒序);能写出三种遍历的递归三行代码;能用数组模拟栈和队列 | 第 5、12、18、24、29、33 课闯关课限时完成 |
| 习惯 | 搜索进点先标记 visited;BFS 入队即标记不重复入队;DP 先写状态含义再写转移;类定义结尾分号不忘 | 第 19 课起「代码体检单」持续检查 |
| 心态 | 拿到新题先画图(迷宫画格子、树画枝杈、背包画表格),画完再写代码 | 第 19~29 课课堂观察 |
底线标准:35 课结束时,每个孩子都能不看答案、限时 40 分钟内独立完成两道题:① N×M 迷宫,障碍物给定,输出起点到终点最少步数(BFS);② 01 背包裸题(n 件物品、容量 m,输出最大价值)。两道题本质对应「六级编程大题最常见的两类型」,缺一不可;缺哪道回补哪段(① 回第 1924 课,② 回第 2529 课)。
三、教学路径(八段式,每段一个台阶)
第一段 后进先出 / 先进先出(第 1~5 课) → 从「数组随便存」到「按规矩存」
栈 · 括号匹配与表达式求值 · 队列 · 循环队列 · 互相实现
↓
第二段 家族的谱系(第 6~8 课) → 从「一条链」到「一棵树」
树的概念 · 二叉树与完全二叉树 · 数组存树
↓
第三段 三种走法(第 9~12 课) → 从「看树」到「走树」
前中后序 · 递归三行代码 · 层序遍历 · 求深度叶子数
↓
第四段 排好序的树与编码(第 13~18 课) → 从「一般的树」到「有用的树」
BST 插入删除 · 哈夫曼树与编码 · 格雷编码 · 综合闯关
↓
第五段 走到底(第 19~21 课) → 从「会走树」到「会搜图」
DFS 递归 · 回溯(全排列/八皇后)· 剪枝
↓
第六段 一圈圈扩(第 22~24 课) → 从「一条路」到「一圈圈」
BFS 队列 · 最短步数与多源 BFS · DFS/BFS 对比选型
↓
第七段 记住算过的(第 25~29 课) → 从「重算」到「记账」
一维 DP 四步法 · 最大子段和 · 01 背包 · 完全背包 · DP 综合
↓
第八段 把数据和行为封起来(第 30~32 课) → 从「散装代码」到「一个对象」
类与对象 · 封装继承多态 · 类综合实战
↓
收口 模考与冲刺(第 33~35 课) → 从「会做」到「考得出」
全考点闯关 · 模拟考 A · 总复习速查
各段教学明细(每段教什么、用哪些例题、孩子最容易错什么)
第一段|后进先出 / 先进先出(第 1~5 课)
- 教什么:栈与数组模拟(1)、括号匹配与表达式求值(2)、队列(3)、循环队列(4)、互相实现(5)
- 关键例题:一摞盘子;括号匹配检查器;
tail=(tail+1)%MAXN假溢出现象 - 孩子最容易错:空栈 pop 崩溃;top 初值 0/-1 混用;循环队列不判满覆盖数据
- 段末验收:独立写出「用栈判断括号串是否合法」和「用数组实现循环队列」
第二段|家族的谱系(第 6~8 课)
- 教什么:树的概念与性质(6)、二叉树与完全二叉树(7)、树的存法(8)
- 关键例题:家谱图;「n 个结点 n-1 条边」性质题;完全二叉树数组存 2i/2i+1
- 孩子最容易错:深度和高度混为一谈;完全二叉树和满二叉树混淆;普通二叉树直接用 2i 访问
- 段末验收:给一棵 7 结点二叉树,口头报出每个结点的父子关系并用数组存下
第三段|三种走法(第 9~12 课)
- 教什么:前中后序定义(9)、递归三行代码与前中序还原树(10)、层序遍历(11)、深度叶子数综合(12)
- 关键例题:同一棵树三种遍历手算对比;「前序第一个是根、后序最后一个是根」定位题
- 孩子最容易错:前序写成根右左;层序不用队列硬写成递归
- 段末验收:给前序+中序序列,独立还原出树并写出后序
第四段|排好序的树与编码(第 13~18 课)
- 教什么:BST 查找插入(13)、BST 删除与退化(14)、哈夫曼树(15)、哈夫曼编码(16)、格雷编码(17)、综合(18)
- 关键例题:自动分流书架;取最小两棵合并算 WPL;
i^(i>>1)生成格雷码 - 孩子最容易错:删除双孩子结点直接删;合并后忘把新结点放回堆;格雷码写成 i&(i>>1)
- 段末验收:给 4 个权值,手算哈夫曼树、写出 WPL 和每个叶子的编码
第五段|走到底(第 19~21 课)
- 教什么:DFS 递归与 visited(19)、回溯(全排列/八皇后)(20)、剪枝(21)
- 关键例题:迷宫四方向搜索;全排列「恢复现场」;可行性剪枝省时对比
- 孩子最容易错:忘标记导致无限递归;标记时机放错(应进入即标);方向数组漏向
- 段末验收:独立完成网格连通块计数(DFS 版)
第六段|一圈圈扩(第 22~24 课)
- 教什么:BFS 队列实现(22)、最短步数与多源 BFS(23)、DFS/BFS 对比选型(24)
- 关键例题:石头入水波纹一圈圈扩;dist 数组记录步数;同一迷宫两法都跑一遍对比
- 孩子最容易错:出队才标记导致重复入队;忘记步数;边界判断写在入队后
- 段末验收:独立完成迷宫最短步数(BFS 版)——这是板块底线标准之一
第七段|记住算过的(第 25~29 课)
- 教什么:一维 DP 四步法与爬楼梯(25)、最大子段和与打家劫舍(26)、01 背包(27)、完全背包(28)、DP 综合(29)
- 关键例题:从五级记忆化斐波那契引出「记账本」;f[j] 倒序与正序的对比实验
- 孩子最容易错:状态含义含糊写不出转移;初值没设;01 背包写成正序变成完全背包
- 段末验收:独立完成 01 背包裸题——这是板块底线标准之二
第八段|把数据和行为封起来(第 30~32 课)
- 教什么:class 与对象、构造函数(30)、封装继承多态(31)、类综合实战(32)
- 关键例题:饼干模具与饼干;用类写学生成绩管理
- 孩子最容易错:构造函数写返回值类型;忘写 public: 外部访问不到;类定义漏分号
- 段末验收:独立写一个 Student 类(带构造函数和 getScore 成员函数)并使用它
收口|模考与冲刺(第 33~35 课)
- 第 33 课:全考点闯关卷(cpp601~cpp612)
- 第 34 课:模拟考 A(6 选择 + 10 判断 + 2 编程)
- 第 35 课:总复习——树/搜索/DP 三线速查表 + 错题重做
每课的固定节奏(2 小时怎么用)
| 时段 | 内容 | 页面 |
|---|---|---|
| 0~10 分 | 上节回顾 + 今天目标 | 回顾页、目标页 |
| 10~25 分 | 情境导入(一摞盘子、家谱、走迷宫、记账本) | 情境页 |
| 25~55 分 | 知识讲解(2~4 张卡 + 手画图示) | 知识页 |
| 55~75 分 | 代码演示(老师敲,孩子读,逐行讲为什么) | 演示页 |
| 75~95 分 | 动手练(跟打→填空→改错,三档星级) | 动手页 |
| 95~110 分 | 真题试炼(6 题,做完立刻对答案) | 试炼页 |
| 110~120 分 | 上机挑战 + 小结 + 留作业 | 挑战页、答案页、小结页 |
本板块 35 课里有 8 节练习/闯关课、2 节模考课,是前六个板块里「练」的比重最高的一级——考点多,必须靠闯关课收口,不接受「讲完了但没练够」。
练习与作业设计
- 动手练(drills):每课 2~3 个,按「跟打 → 填空 → 改错 → 独立」梯度,标星级
- 真题试炼(quiz):固定 6 题(易 2 / 中 2 / 难 2),答案与「为什么」当场可见
- 上机挑战(lab):每课 1 个完整编程题,附完整可运行参考答案与逐行注释
- 课后作业:2~3 项,第 1 项必为编程作业且附参考答案
- 画图专项(第 6~24 课):树、迷宫、图的题一律先画图再动键盘,草稿纸检查纳入课堂纪律
- 对比实验(第 22
24、2728 课):同一迷宫 DFS 与 BFS 都跑、01 背包倒序与正序都跑,孩子自己记录差异
模拟考与验收安排
| 课次 | 内容 | 口径 |
|---|---|---|
| 第 19 课 | 阶段闯关(栈队列树遍历段) | 20 分钟限时 |
| 第 24 课 | 搜索段闯关 | DFS+BFS 各一道网格题 |
| 第 29 课 | DP 段闯关 | 底线标准两题预演 |
| 第 33 课 | 全考点闯关卷 | 覆盖 cpp601~cpp612 |
| 第 34 课 | 模拟考 A | 6 选择 + 10 判断 + 2 编程 |
| 第 35 课 | 总复习 + 错题重做 | 三线速查表带走 |
四、考点对照表
| 考点 | 名称 | 落在哪几课 |
|---|---|---|
| cpp601 | 栈:后进先出 | 1、2、5 |
| cpp602 | 队列与循环队列 | 3、4、5、11 |
| cpp603 | 树的基本概念与二叉树 | 6、7、8、18 |
| cpp604 | 二叉树的遍历 | 9、10、11、12 |
| cpp605 | 二叉排序树 | 13、14 |
| cpp606 | 哈夫曼树与哈夫曼编码 | 15、16、18 |
| cpp607 | 格雷编码 | 17、18 |
| cpp608 | 深度优先搜索(DFS) | 19、20、21、24 |
| cpp609 | 广度优先搜索(BFS) | 22、23、24 |
| cpp610 | 简单动态规划(一维) | 25、26、29 |
| cpp611 | 01 背包与完全背包 | 27、28、29 |
| cpp612 | 面向对象与类 | 30、31、32 |
五、本板块最难的三个坎(教师用)
- 由树到图的搜索跳跃(第 19~24 课):树是「确定结构往下走」,图是「可能绕环、要防回头」,孩子容易把 DFS 直接搬到网格上然后死循环。对策:第 19 课第一件事就是让孩子指出「网格迷宫和二叉树,DFS 代码差在哪一行」——答案是 visited 标记;BFS 同理,第 22 课强调「入队即标记」并举出「出队才标记会怎样」的反例。
- DP 的状态定义(第 25~29 课):孩子会背四步法但写不出 f[i] 的含义。对策:先回到五级第 11 课的记忆化斐波那契,指出「f[i] = 第 i 阶楼梯的走法数」那个数组其实就是 DP;爬楼梯、最大子段和两课先「抄状态、读转移」,第 29 课综合课才要求「自己定义状态」。01 背包的倒序循环用「一件物品只能用一次」的情景反复追问为什么。
- 类的新语法冲击(第 30~32 课):struct 时代孩子没见过 public/private 和构造函数。对策:本段只要求「会用」——会用 class 封装成员、会写构造函数、会用继承,virtual 多态点到为止(笔试为主,不考编程大题)。
卡点速查表(贴讲台用)
| 现象 | 出现在 | 一句话诊断 | 对策 |
|---|---|---|---|
| 空栈 pop 崩溃 | 第 1~2 课 | 「盘子都没了还端什么」 | pop 前先判 top==0 |
| 循环队列数据丢了 | 第 4 课 | 「队尾追上队头了」 | 判满:(tail+1)%MAXN==head |
| 遍历漏结点 | 第 9~12 课 | 「三种走法只换了顺序」 | 根在哪个位置背口诀 |
| DFS 死循环 | 第 19~21 课 | 「迷宫里没插旗子」 | 进入结点立即 visited=1 |
| BFS 步数错/爆内存 | 第 22~23 课 | 「同一个人排了两次队」 | 入队时立刻标记 |
| 01 背包变完全背包 | 第 27 课 | 「容量反着走,东西只装一次」 | j 从大到小循环 |
| 状态写不出转移 | 第 25~29 课 | 「你还没说清 f 是什么」 | 草稿第一行先写状态含义 |
六、家长沟通要点(最常被问的 4 个问题)
Q1:六级怎么这么多东西?孩子跟得上吗? 答:12 个考点看着多,实际是四组:栈队列(2 个,一周半搞定)、树与遍历(4 个,互相连着)、搜索(2 个,是一套方法的两面)、DP 与背包(2 个)、类(1 个,纯语法)。真正的新思维只有「搜索」和「DP」两样,其余都是五级递归和数组操作的延伸。课表里我们比前几个板块多排了 2 节闯关课,就是为了兜住内容量。
Q2:DP 不是大学才学吗?为什么六级就出现? 答:GESP 六级大纲明确包含「简单动态规划」和背包问题,这是官方要求。而且我们教的版本很克制:一维 DP 和两种背包,全部从孩子四级的爬楼梯递推长出来,没有新数学。真正难的二维 DP、区间 DP 在七级,难度是分层的。
Q3:DFS 和 BFS 孩子说老是记混怎么办? 答:区分记在「用途」上而不是「代码」上:问「能不能到达 / 有几个连通块」用 DFS(一条路走到黑),问「最少几步」用 BFS(一圈圈扩,先到的就是最短)。第 24 课有专门的对比选型课,闯关题里两种混着出,练一个月自然分清。
Q4:类和对象这个,是不是提前学了大学的东西? 答:考纲里有(cpp612),而且六级笔试每年都考 class 相关的选择判断。我们只教到「能自己写一个学生类、带构造函数和成员函数」的程度,继承和多态只讲概念和两道笔试题,不搞项目。孩子写完这节课最大的收获其实是:回头看自己三级的代码,知道「数据和行为可以打包」了。
Q5:哈夫曼、格雷码这种,听着就很偏,为什么六级要学?
答:它们是六级笔试的高频题——哈夫曼考「取最小两棵合并 + 算 WPL」,格雷码考一个公式 i^(i>>1),套路固定、两周足够拿下。而且哈夫曼还是八级区间 DP(石子合并)和七级贪心思想的前奏,不是孤立知识点。孩子觉得偏,往往是因为没做过题——做完 6 道真题试炼就会发现「每年就这几种问法」。
七、遗留与衔接
- BFS 在本级只解决「边权全为 1」的最短路;带权图的最短路(Dijkstra/Floyd)是八级 cpp807 的内容,六级不提。
- 背包在本级只做 01 和完全两种、求最大价值;「恰好装满」「方案数」等变形在第 29 课综合课见一面,七级不再回头重讲基础。
- 类在本级不涉及运算符重载、STL 容器底层——链式前向星在七级第 12 课用「结构体数组」实现,不依赖这部分。
- 升板块七的门槛:模拟考(第 34 课)≥70 分且编程大题拿到一半分;底线标准两道题(迷宫 BFS、01 背包)限时 40 分钟独立通过;能不看书写出三种遍历的递归三行代码。没达标的优先回补第 19~29 课——搜索和 DP 是七级的主菜,这两块虚了,七级等于重新上课。
附:修订记录
2026-11-11 · 全部 280 份课件用修正后的生成管线重做了一遍。修的是显示缺陷:此前「中文句子夹英文」的段落,英文部分在 PPTX 里会被整段吞掉——关键字表只剩「类型只装整数」,函数名、题面里的 BFS / queue / sort 同样是空白。代码页不受影响,所以一直没被发现。
本板块涉及:第 22 课概念卡改讲 pair / make_pair / .first / .second(BFS 里「一个元素装一个坐标」的写法,此前直接使用、零讲解);第 16 课补 operator() 仿函数说明(堆比较器为什么那样写)。
校验口径:280 份逐课比对「源码里出现的英文标识与 PPTX 可见文字」完全一致,0 缺失;页数仍为每课 22~24 页,结构校验(页数区间、代码行数、真题 6 题配比)全部通过。
旧的课件包已全部被覆盖,请以 新教案 目录里的这一版为准;不要用 2026-11-10 之前导出的包上课。