GESP 八级 · GESP 八级样题（C++ 组） 第 13 题

对于具有 $n$ 个元素的二叉排序树（又名二分查找树）进行前序遍历，其时间复杂度是( )？

这题别被"排序树"的名头带偏，核心就抓一点：遍历是必须把树里每个节点都摸一遍，不管树长得再歪，节点总数n不变，操作次数就是n，直接锁定O(n)。

最容易栽在选项B上，看到"二叉排序树"就下意识想成二分查找的最优情况O(log n)，把"搜索"的复杂度安到了"遍历"头上。还有一种是把树想得太完美，以为前序遍历能像中序遍历那样利用有序性优化，其实前序只是按根左右顺序把n个元素全吐出来，输出n个数本身就耗O(n)。

【考点】二叉树遍历本质｜二叉排序树与平衡二叉树的区别｜时间复杂度基础

前序遍历的定义非常死板：先访问根，再递归遍历左子树，最后递归遍历右子树。不管这棵树是完美的平衡二叉树，还是退化成一条长长的链表，也管它是不是二叉排序树（BST），只要树里有n个节点，遍历算法就必须且只能访问这n个节点各一次。访问操作本身是O(1)，所以总时间复杂度铁定是O(n)。

很多考生一看到"二叉排序树"这四个字，脑子里蹦出来的第一个反应是O(log n)。这是典型的思维定势陷阱：O(log n)是二叉排序树在查找特定元素时的最优时间复杂度，前提是树是平衡的。但题目问的是遍历，遍历的任务是把整棵树的所有数据都取出来，这跟"找没找得到"完全是两码事。哪怕树退化成链表（最坏情况），前序遍历依然要顺着链走一遍，步数还是n，复杂度依然是O(n)。选项B就是把"搜索"的复杂度偷换成"遍历"，命题人挖这个坑就是为了看你能不能分清"操作对象"。

再看选项D的O(n²)，这通常出现在嵌套循环且内外层都随n增长的场景。二叉树遍历是递归或显式栈实现，递归深度最坏是n，但每一层递归只做常数次工作（打印当前节点+压栈/弹栈），没有嵌套循环让复杂度平方化，所以D可以秒排。

从命题视角看，这道题其实是在考你对"遍历"和"搜索"这两个基本操作的区分度。刷树相关题目时，拿到题先问自己：我要访问的是整棵树的所有节点，还是只找满足某个条件的节点？如果是前者，答案几乎永远是O(n)；如果是后者，才需要结合树的结构（平衡与否）去算O(log n)或O(n)。

考频趋势方面，二叉树基础在题库里是高频考点，2023年、2024年、2025年分别考了20题、60题、67题，呈爆发式增长，说明近年对树结构的考察力度非常大。二叉树遍历更是重中之重，2025年单年考了67题，几乎每场考试都会涉及。二叉排序树（BST）作为树的一种重要应用，2025年也考了67题，和遍历考频几乎持平。排序基础虽然总量大（249题），但多集中在算法实现细节。

基于这些数据预测，未来GESP八级、NOIP普及组等考试中，关于"树的操作复杂度"的题目大概率会持续高频出现。命题人可能会继续用"BST"、"AVL"、"红黑树"等不同树结构来包装同一个"遍历"或"搜索"的问题，试图混淆视听。但万变不离其宗：遍历整棵树必为O(n)，搜索特定值在平衡树上才可能是O(log n)。只要记住这个核心区分点，这类送分题就不会失手。