二叉树与四种遍历

一句话定义

二叉树（Binary Tree）是每个节点至多有两个孩子（左、右）的层次结构；遍历（Traversal）按确定顺序访问全部节点——前序（根左右）、中序（左根右）、后序（左右根）为深度优先，层序为广度优先（队列实现）。

为什么重要

树是表达层级关系（文件系统、组织架构、DOM、表达式）的通用结构，而遍历是树上一切算法的骨架：BST 的有序输出靠中序、堆靠完全树形、回溯是带状态的树遍历、图的 DFS 本质是遍历一棵「生成树」。遍历的递归/迭代双写法也是把 kp-008 的栈用活的第一个场合。

前置知识

kp-008（栈与队列）；递归调用模型。

核心概念

• 基本量：节点数 n、深度 depth（根为 0 或 1，需自定约定）、高度 height（最深叶子的深度）。
• 形状家族：满二叉树（每节点 0 或 2 孩子）、完全二叉树（只有最底层可缺且靠左——堆的形状）、平衡二叉树（任意节点左右子树高度差有界）。
• 数量关系：高度 h 的完全二叉树节点数在 2^h ~ 2^(h+1)−1 之间 ⇒ 高度 Θ(log n)；n 节点二叉树恰有 n+1 个空指针（线索树的动机）。
• 四种遍历：前/中/后序（DFS，递归或显式栈）、层序（BFS，队列）。
• 还原问题：前序/后序 + 中序可唯一重建树；前序 + 后序不能唯一重建。

直观类比

树的遍历像参观一栋多层小楼：前序是「每到一层先登记再下探」，中序是「左翼逛完、正厅登记、再逛右翼」，后序是「先收尾所有孩子再收自己」，层序是「按楼层从下往上逐层参观」。

原理与机制

递归遍历统一模板（换位置即得三种序）：

函数 visit(node):
    若 node 为空: 返回
    // 前序位置: 输出 node
    visit(node.left)
    // 中序位置: 输出 node
    visit(node.right)
    // 后序位置: 输出 node

复杂度：每个节点进出各一次 ⇒ 时间 Θ(n)；递归栈深为树高 h ⇒ 空间 O(h)，最坏（链状树）O(n)。层序用队列：出队时把两个孩子入队，同样 Θ(n)。迭代化 DFS 用显式栈模拟递归，前序直接压右后压左；中序需「沿左链下压、弹出到中序位、转向右子」的双阶段循环。

图示

           1
         /   \
        2     3
       / \     \
      4   5     6

前序: 1 2 4 5 3 6      （根左右）
中序: 4 2 5 1 3 6      （左根右）
后序: 4 5 2 6 3 1      （左右根）
层序: 1 2 3 4 5 6      （逐层，队列实现）

实例或案例

• 表达式树：(a+b)*c 存成树，中序（加括号）还原表达式、后序直接做后缀求值——编译器的抽象语法树同源。
• 文件系统 du 统计目录大小是后序（先算子目录）；目录树打印是前序。
• 层序遍历求树的最大宽度/按层分组输出（LeetCode 102），是队列的经典用法。
• 完全二叉树用数组存（父子下标 2i+1/2i+2），正是 kp-014 堆的形状基础。

常见误区

• 以为「前序 + 后序」能唯一重建二叉树：当只有单孩子时无法区分左右，必须配中序。
• 忽视递归栈深：链状 10⁵ 节点的树会栈溢出，需迭代化。
• 混淆高度/深度/层数的定义约定，导致结论差一；写代码前先钉死约定。
• 认为 O(h) 空间是 O(log n)：只有平衡树才 log n，一般树最坏是 O(n)。

自测题

1. 已知前序 A B D E C、中序 D B E A C，重建这棵树。

答案要点：根 A，中序左子树 {D,B,E} 右子树 {C}；左子树前序 B D E ⇒ B 为根、D 左 E 右。结果：A(B(D,E),C)。

1. n 个节点的完全二叉树高度（根记 0 层）是多少？

答案要点：⌊log₂n⌋；因为前 h 层满时节点数 2^(h+1)−1 < n+1 约束成立。

1. 写出层序遍历伪代码并说明为什么用队列而不是栈。

答案要点：根入队；出队时访问并把左右孩子入队；队列的先进先出保证「第 k 层全部处理完才进入第 k+1 层」，栈会变成 DFS 顺序。

与其他知识点的关系

kp-012 在中序有序性上建立 BST；kp-014 堆依赖完全树形状；kp-016 的 DFS/BFS 是树遍历带 visited 的推广；kp-027 回溯是「树上做选择并撤销」的遍历变体。

延伸阅读

《算法导论》第 12.1 节；《算法（第 4 版）》二叉树遍历小节；Morris 遍历（O(1) 空间中序）作为进阶。