知识点深化 · 数据结构 · 二叉树
二叉树与遍历：前中后序、层序、递归改迭代
二叉树是每个节点最多两个孩子的树。它是堆、二叉搜索树、文件目录、表达式树的骨架。前中后序三种深度遍历是面试必考题：递归写起来 3 行，改写成迭代却能看出真功夫。这一页把遍历顺序、递归转栈、层序 BFS 一次讲透。
① 小白第一课怎么学（4 步走，约 60 分钟）
别急着背代码，先按这四步建立直觉：
1看图建立直觉（10 分钟）
读②③：画一棵五层树，标清左右孩子和根。
2记三种遍历（15 分钟）
读④：根/左/右的先后顺序，前中后序区别就在根位置。
3手推遍历（20 分钟）
精读⑤：给一棵树手算三种遍历输出。
4刷题纠错（15 分钟）
做⑦⑩，错题回⑥。
本课小目标学完你要能：① 给出树能写出前/中/后序遍历结果；② 解释递归遍历为什么简单；③ 用栈手动模拟前序/中序迭代。
② 一图看懂：二叉树遍历全地图
读法：中心是二叉树，四种遍历方式并列，下方是应用与易错。
③ 本质直觉：遍历就是"什么时候看根"
一棵二叉树：根节点带着左子树和右子树。所谓遍历，就是把每个节点都访问恰好一次。对每个子树，你要做三件事：访问根（V）、走左（L）、走右（R）。区别只在 V 放在哪：
前序 V-L-R：先看根，再左子树，再右子树。
中序 L-V-R：先左子树，再根，再右子树。
后序 L-R-V：先左，再右，最后根。
递归为什么简单：每个子树本身就是一棵更小的树，交给递归函数即可。层序不用递归，用队列一层一层扫。
中序遍历 BST 得升序二叉搜索树（左<根<右）的中序遍历天然输出从小到大排好序的序列。这是 BST 最重要的性质。
④ 完整体系与对比表
四种遍历对比
| 遍历 | 顺序 | 典型用途 |
|---|
| 前序 | 根→左→右 | 复制树、前缀表达式、打印目录结构 |
| 中序 | 左→根→右 | BST 取升序序列 |
| 后序 | 左→右→根 | 删除树、后缀表达式、计算目录大小 |
| 层序 | 逐层，左→右 | 找层深、锯齿层序、BFS |
递归遍历三行代码
前序递归preorder(root){ if(!root) return; visit(root); preorder(root.left); preorder(root.right); }
中序把 visit 移到左右之间；后序把 visit 移到最后。就这一个区别。
递归改迭代（用栈）
前序迭代
用栈模拟。先压根；弹出即访问；先压右再压左（栈是后进先出，左才能先弹）。
中序迭代
指针一路向左压栈，走到底后弹出访问，再转到右子树。
中序迭代模板while(stack 非空 || p){ while(p){push(p); p=p.left;} p=pop; visit(p); p=p.right; }
层序迭代
用队列：根入队；循环出队访问，把左右孩子入队。
⑤ 用法场景与典型例题
例1（前序）右图树 1(2(4,5),3)，前序输出？
根左右，递归展开。
① 访问根 1；② 走左子树 2：访问 2→左 4→右 5；③ 走右子树 3：访问 3。答案：1 2 4 5 3。
例2（中序）同上树，中序输出？
左根右。
根 1 放中间：先左子树 2 的中序（左4→2→右5）=4 2 5；再 1；再右子树 3=3。答案：4 2 5 1 3。
例3（层序）同上树，层序输出？
队列逐层。
第1层 1；第2层 2 3；第3层 4 5。答案：1 2 3 4 5。
做题心法手算遍历就一句话：到一个节点先想"现在轮到根了吗"。前序一到就打印，中序打印左子树回来再打印，后序左右都回来才打印。
⑥ 高频错误诊断（4 条）
错误1：前序迭代压栈顺序写反栈后进先出，要让左先处理必须先压右孩子再压左孩子，写反就变成右先了。
错误2：把中序当成前序中序是左根右，不是根左右。BST 中序才升序，别记混。
错误3：层序用栈层序要按层先来后到，必须用队列 FIFO，用栈就乱序了。
错误4：递归没有基线条件忘记 if(!root) return，空指针递归到底栈溢出。
⑦ 考点真题演练（4 题）
考点分布
| 考法 | 出题形式 | 应对 |
|---|
| 遍历输出 | 给树写三种序列 | 按根位置顺序走 |
| 递归改迭代 | 问用栈还是队列 | 深度用栈，层序用队列 |
| BST 性质 | 问哪种遍历得升序 | 中序 LVR |
| 栈压栈顺序 | 前序迭代先压谁 | 先压右再压左 |
真题基础1. 二叉搜索树的哪种遍历能得到升序序列？
真题中档2. 前序遍历的顺序是？
真题中档3. 层序遍历（BFS）使用的数据结构是？
真题拔高4. 前序迭代用栈时，入栈孩子的正确顺序是？
⑧ 必背知识点卡
前序：根左右 VLR 复制树/目录
中序：左根右 LVR BST 升序
后序：左右根 LRV 删除/算大小
层序：队列逐层 BFS 找层深
递归：visit 位置决定前后中 加 if(!root) return
迭代：深度用栈，层序用队列 前序先压右
高度：空树 -1，否则 1+max(左右)
⑨ 应用输出：打印文件夹目录结构（前序）
场景：写一个 ls -R，把文件夹树按缩进打印出来。
① 选型：文件系统是棵树，目录是节点，子文件/子目录是孩子。
② 前序遍历：先打印当前目录名（缩进=深度），再递归进入每个子目录。
③ 为什么前序：要先看到目录本身，再展开里面内容，正好根左右。
④ 深度=缩进：递归传 depth 参数，每层多打两个空格。
⑤ 后序变体：若要算每个目录占用总大小，要用后序——先把左右子目录大小加起来再加自己。
口述思路合上书说："目录树用前序打印，算大小用后序，都是递归。"
⑩ 分层练习（基础 + 中档 + 拔高）
▍基础 6 题
基础1二叉树每个节点最多几个孩子？
2 个（左、右）。
▍中档 6 题
中档8递归遍历为什么要写 if(!root) return？
基线条件，防止访问空指针无限递归。
中档9迭代中序遍历用什么？
栈：一路向左压栈，到底弹出访问再转右。
中档10二叉树高度怎么算？
1+max(左高,右高)，空树高度 0 或 -1 视约定。
中档11后序遍历适合做什么？
删除树（先删孩子再删根）、计算目录大小。
中档12前序迭代为什么先压右孩子？
栈后进先出，先压右则后弹，左孩子先被处理。
▍拔高 6 题
拔高13已知前序+中序能否重建二叉树？
能：前序首是根，在中序切出左右子树，递归重建。
拔高14已知后序+中序呢？
能：后序末尾是根，其余对称切。
拔高15已知前序+后序能唯一确定吗？
不能，缺孩子方向信息，会有歧义。
拔高16完全二叉树用什么存储最省？
数组按下标：i 的左右孩子在 2i+1、2i+2。
拔高17判断平衡二叉树？
左右子树高度差 ≤1 且左右都平衡，后序遍历顺带算高度。
拔高18二叉树节点数 n，遍历时间复杂度？
每个节点访问一次 O(n)；递归栈空间 O(h)。
⑪ 记忆口诀 + 7 天复习计划
三句口诀① 前根左右中左根，后序左右根。② BST 中序必升序，层序队列深度栈。③ 前序迭代先压右，递归基线别忘记。
| 天 | 任务 | 自检 |
|---|
| 第 1 天 | 读②③④，画一棵树手推三种遍历 | 顺序写对 |
| 第 2 天 | 背遍历表 + 基础 1-6 | 四种遍历全对 |
| 第 3 天 | 做中档 7-12，手写中序迭代 | 栈操作对 |
| 第 4 天 | 做拔高 13-18，前中序重建树 | 能讲清切分 |
| 第 5 天 | 做⑦真题 4 题 | 限时每题 2 分钟 |
| 第 6-7 天 | 合上书口述口诀，默写递归三行 | 不看资料全默对 |
← 返回软件技术总览