中序遍历

中序遍历把"喊名字"挪到了中间：先走完左子树，再访问根，最后走右子树。可以想成看戏——先看左边的演员，轮到主角登场时报出名字，再看右边的。它有一个很漂亮的性质，下一节就揭晓。

#include <iostream>
using namespace std;
struct Node { int val; Node* l; Node* r; };
void mid(Node* p) {
    if (!p) return;
    mid(p->l);
    cout << p->val << " "; // 根在中间
    mid(p->r);
}
int main() {
    Node d{1,0,0}, e{3,0,0}, b{2,&d,&e}, c{5,0,0};
    Node a{4,&b,&c};
    mid(&a); // 输出：1 2 3 4 5
}

初学者常忘：递归里少写 if (!p) return;，或者把左右两次递归的位置写反，中间那一段顺序就全错了。