GESP 七级 · GESP 202403 C++ 七级 第 7 题

以下关于二叉排序树的说法，正确的是（ ）。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】二叉排序树中序遍历｜BST 最坏时间复杂度｜二叉平衡树性质

考纲定位 本题考查《GESP 考试大纲》七级 数据结构与算法模块中的「树结构」考点。命题人把「二叉排序树」和「二叉平衡树」的概念混在一起，卡住的是多数考生对树结构基本性质的记忆模糊——以为所有 BST 都平衡，所以时间复杂度自动 O(log n)。

解题思维 看到「二叉排序树」三个字，先激活两个核心定义：1) 左子树所有节点值 < 根节点值；2) 右子树所有节点值 > 根节点值。由定义直接推出中序遍历（左-根-右）必然得到升序序列，所以 A 正确。B 选项「最差情况 O(log n)」是典型陷阱，只有平衡 BST 才保证 O(log n)，普通 BST 若退化成链表，查找复杂度是 O(n)。C 选项「一定是平衡树」更是概念偷换，BST 和平衡树（如 AVL）是包含与被包含关系，BST 完全可以不平衡。

陷阱拆解 A 选项看似绝对，但「中序遍历序列一定是有序的」正是 BST 的本质属性，没有反例。B 选项利用「有序」与「平衡」的语义混淆，让考生误以为 BST 自动平衡。C 选项用「一定」这种绝对化表述，把 BST 和平衡树等价化，属于命题人常用的概念偷换套路。

反命题思维 如果把「二叉排序树」改成「二叉平衡树」，B 就对了；如果把「一定」改成「通常」，C 就成立。刷到类似题时，先问自己：题目里缺了「平衡」这个定语吗？