二叉树先序遍历（Preorder Traversal）

算法原理

先序遍历是深度优先遍历的一种，口诀是**「根左右」：先访问根，再递归遍历左子树，最后递归遍历右子树。它的关键特征是进入节点即记录**——一个节点刚被到达、还没看任何孩子时，它的值就已经写入输出序列，所以"根永远出现在它的左右子树之前"。

本动画在一棵 7 节点的完全二叉搜索树上完整走一遍（默认 2s/拍，全片 15 拍）：

树：根 5（左子 3，右子 8）；3 的孩子 1、4；8 的孩子 7、9
先序输出：5 3 1 4 8 7 9
节拍：宣告 1 + 进入即记 7 + 返回父 6 + 完成 1

看点在**"进入即记"**：焦点落到 5 的第一拍输出条就写下 5，随后一头扎进左子树——3、1、4 全部记完才回头碰 8。前半条输出全是左子树，正是"根 → 左 → 右"的字面执行。

动画怎么看

• 上半区是树：7 个节点盒 + 父子实线连线；黄色描边 = 遍历者焦点，逐拍从当前节点移到下一个节点，本拍移动的那条边青色加粗，走过的节点转绿色常驻；
• 口诀立牌：舞台左上角常驻「口诀 根左右」——每拍都可以拿画面行为对照口诀自查；
• 进入拍：焦点落到新节点，同拍输出条写入该节点的值（进入 = 记录，一拍两事合一）；
• 返回拍：状态行显示 返回 p · 查完 n，只移动不记录——这是"左右都看完了才回去"的可视化；
• 大✓：7 格输出齐了，状态行 ✓ 完成 ｜ 先序遍历 7 节点全部输出。

复杂度分析

C++ 参考代码

#include <iostream>
struct Node {
    int val;
    Node *left, *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

void preorder(Node *root) {
    if (!root) return;
    std::cout << root->val << " ";   // 根：进入即记录
    preorder(root->left);            // 左：整棵左子树
    preorder(root->right);           // 右：整棵右子树
}

int main() {
    // 完全 BST：5(3(1,4), 8(7,9))
    Node a(1), b(4), c(3), d(7), e(9), f(8), root(5);
    c.left = &a; c.right = &b;
    f.left = &d; f.right = &e;
    root.left = &c; root.right = &f;
    preorder(&root);                 // 输出 5 3 1 4 8 7 9
    return 0;
}

什么时候用先序遍历

凡是**"先处理父、再处理子"的场合都是先序的主场：树的序列化与重建**（先序 + 空节点标记能唯一还原一棵二叉树）、整棵树的深拷贝（先建父节点才有地方挂孩子）、前缀表达式（波兰式：运算符天然在操作数之前）、目录树的先根序列（先列出目录名再展开内容）。掌握它的诀窍就一句：进入即记——本动画里焦点每落到一个新节点、输出条同拍落字的那一下，就是这句话的样子。