"遍历"就是把树拉直成一条序列——差别只在于：自己排在"前、中、后"哪个位置
想象你是一个"打卡员"，要走进一棵家谱树，给每个人拍一张照片，一个都不能漏、一个都不能重复。
走到每个人面前时，你有三种"拍照时机"可选：先拍自己再去孩子家（前序）、拍完左孩子再拍自己（中序）、拍完所有孩子最后拍自己（后序）。
规则一旦定了，就要对每个节点一视同仁——这就是"递归"：对左子树用同一套规则，对右子树也用同一套规则。
树是二维的（有层次、有分支），但打印、发送、存进文件都是一维的序列。想把一棵树"搬"到一维世界里，就得先定好访问顺序。
三个真实场景：① 打印家谱名单（按某种顺序念出来）；② 把树通过网络发给别人（序列 + 规则 = 对方能还原整棵树）；③ 统计、计算都要"把每个节点看一遍"。
规则：前序 = 先访问自己，再左子树，再右子树。对"左子树"和"右子树"内部，也用同一套规则（递归！）。跟着打卡员走一遍：
① 站在根 1：先拍自己 → 输出 1。
② 去左孩子 2：先拍自己 → 输出 2。
③ 2 的左孩子 4：拍 → 输出 4。4 没有孩子，原路退回 2。
④ 2 的右孩子 5：拍 → 输出 5。退回 2，再退回 1。
⑤ 1 的右孩子 3：拍 → 输出 3。结束！
三种遍历的代码长得几乎一样，差别只有一处：打印（访问）那行代码放在递归调用的前面、中间、还是后面。先"查空"，再"左、自己、右"——顺序一换，世界大变。
// 前序：先访问自己 void pre(Node* t) { if (t == nullptr) return; // 空树：啥也不做（递归出口） cout << t->val << " "; // ① 自己 pre(t->left); // ② 左子树（同样规则） pre(t->right); // ③ 右子树（同样规则） } // 中序：先左，再自己，后右 void ino(Node* t) { if (t == nullptr) return; ino(t->left); // ① 左 cout << t->val << " "; // ② 自己 ino(t->right); // ③ 右 } // 后序：左、右都完成后，最后自己 void post(Node* t) { if (t == nullptr) return; post(t->left); post(t->right); cout << t->val << " "; // 最后才是自己 }
对示例树运行：pre 输出 1 2 4 5 3，ino 输出 4 2 5 1 3，post 输出 4 5 2 3 1——和大图完全一致。
t == nullptr 时再访问 t->val 就会"拆一个不存在的盒子"（段错误）。空树 = 递归的终点，就像 GESP5 递归课里"队首的人说前面 0 个人"。cout 放在两个递归调用之间，得到的是哪种序？两条序列各给一半信息：前序第一个数 = 根（子任务 2 的规律）；中序里，根左边的 = 左子树，右边的 = 右子树（中序 = 左→根→右 决定的）。
还原示例：前序 [1,2,4,5,3]，中序 [4,2,5,1,3]。
① 前序首位 = 1 → 根是 1。
② 在中序里找 1：它左边 [4,2,5] 是左子树，右边 [3] 是右子树。
③ 对左子树 [4,2,5] 重复同样的两步：前序对应段 [2,4,5] 首位 = 2 → 左子树的根是 2；中序里 2 左边 [4]、右边 [5] → 2 的左孩子 4、右孩子 5。完成！
#include <iostream> using namespace std; struct Node { int val; Node* left; Node* right; }; // 小工具：造一个节点 Node* makeNode(int v, Node* l, Node* r) { Node* t = new Node(); t->val = v; t->left = l; t->right = r; return t; } void pre(Node* t) { if (t == nullptr) return; cout << t->val << " "; pre(t->left); pre(t->right); } void ino(Node* t) { if (t == nullptr) return; ino(t->left); cout << t->val << " "; ino(t->right); } void post(Node* t) { if (t == nullptr) return; post(t->left); post(t->right); cout << t->val << " "; } int main() { // 建示例树：1 为根，2/3 为左右孩子，4/5 是 2 的孩子 Node* n4 = makeNode(4, nullptr, nullptr); Node* n5 = makeNode(5, nullptr, nullptr); Node* n2 = makeNode(2, n4, n5); Node* n3 = makeNode(3, nullptr, nullptr); Node* root = makeNode(1, n2, n3); cout << "前序: "; pre(root); cout << endl; cout << "中序: "; ino(root); cout << endl; cout << "后序: "; post(root); cout << endl; // 前序: 1 2 4 5 3 // 中序: 4 2 5 1 3 // 后序: 4 5 2 3 1 return 0; }