GESP 八级 · GESP 202312 C++ 八级 第 8 题

对有 $n$ 个元素的二叉排序树进行中序遍历，其时间复杂度是（ ）。

别被「二叉排序树」这个定语绕晕了，直接看动作：中序遍历就是左根右，n 个节点每个都得摸一遍，次数固定为 n，常数操作叠加就是 O(n)。

最容易掉进 B 选项 O(log n) 的坑里，那是把「遍历所有节点」和「在平衡树上查找某个节点」搞混了。命题人就是利用你看到 BST 就下意识想树高低的直觉，让你以为能跳过大部分节点。还有少数人会把 O(1) 当成「访问根节点」，或者瞎编 O(n²) 觉得递归有平方，其实递归每层只是简单访问，没有嵌套循环，根本凑不出平方。记住：只要题目要求遍历完所有元素，不管树多歪多直，复杂度都是线性的。

【考点】二叉树遍历｜时间复杂度分析

这道题考的是二叉树遍历的时间复杂度，核心在于理解「遍历」的本质：必须访问树中每一个节点，且每个节点只访问一次。

先理清概念。二叉排序树（BST）的中序遍历规则是固定的：左子树→根节点→右子树。无论树长得多么奇怪——是完美的平衡树，还是退化成一条单链的斜树——这个访问顺序和访问次数都不会变。n 个节点，每个节点都要被「摸」一下，总共就是 n 次访问。每次访问（打印、计数、比较等）都是常数时间操作 O(1)，所以总时间就是 n × O(1) = O(n)。

命题人最喜欢在这里挖坑，就是利用考生的直觉偏差。看到「二叉排序树」，学生容易联想到「树高 O(log n)」，进而错误地认为遍历也只要 O(log n)，选了 B 选项。其实 O(log n) 是 BST 上「查找」「插入」「删除」这些只访问部分节点的操作的复杂度。而「遍历」是要把整棵树扫一遍，跟树高无关，只跟节点总数有关。哪怕树退化成链表，遍历依然是 O(n)；哪怕树平衡得像金字塔，遍历还是 O(n)。树形影响的是查找效率，不影响遍历效率。

再来看其他干扰项。A 选项 O(1) 是把「遍历」偷换成「访问根节点」，显然不对。D 选项 O(n²) 是凭空捏造，通常对应嵌套循环或某些二次算法，但本题没有任何嵌套结构，递归深度虽为 O(n)，但每层只做常数工作，不会变成平方。

思考心法：拿到遍历题，先问自己——题目要求访问全部节点吗？如果是，不管树形如何，答案几乎肯定是 O(n)。只有当题目要求「找某个节点」「统计满足条件的节点数」且利用 BST 性质剪枝时，才可能出现 O(log n) 或更优的复杂度。

考频与趋势：二叉树基础在题库中占比最高，共 220 题，覆盖 8 个级别。其中 2025 年考了 67 题，2024 年 60 题，2026 年 28 题，2023 年 20 题，呈现逐年上升态势。二叉树遍历单独考了 201 题，2025 年同样高达 67 题，2024 年 58 题，2023 年 19 题，说明「遍历」是高频考点。二叉搜索树（BST）考了 183 题，2025 年 67 题、2024 年 57 题，与遍历高度重合，命题人常把 BST 作为背景来考遍历或查找。

预测：基于 2023-2025 年的数据，BST 相关题目（遍历、查找、插入、删除）在八级及 GESP 六级、七级中持续高频出现，且 2025 年达到峰值（67 题）。未来几年（2026-2027）大概率仍会保持这一热度，可能继续以 BST 为背景考察遍历变体（如中序遍历生成有序序列、层序遍历统计等）或 BST 操作的时间复杂度辨析。暂无足够依据预测具体题型变化，但「BST+ 遍历/查找」的组合仍是必考方向。