GESP 六级 · GESP 202506 C++ 六级 第 19 题

对一棵二叉排序树进行中序遍历，可以得到一个递增的有序序列。

比较不同排序算法的核心区别：冒泡（相邻交换）、选择（选最值）、插入（插入有序序列）、归并（分治合并）、快排（划分递归）。

二叉排序树（BST）的中序遍历结果是递增有序序列。最好情况O(log n)发生在树平衡时，最坏O(n)发生在树退化为链时。

【考点】二叉排序树定义｜中序遍历性质｜数据结构基础

GESP 六级 C++ 大纲「数据结构」模块明确要求掌握 BST 基本性质。命题人以此题卡住大量考生——他们能写出中序遍历代码，却对 BST 结构约束缺乏直觉认知。此题本质考的是「结构约束与遍历顺序的耦合关系」，而非单纯记忆遍历结果。若考生混淆「二叉树」与「二叉排序树」，会误选 B，因为普通二叉树的中序遍历确实不保证排序。

思考链：BST 定义要求左子树节点值均小于根，右子树均大于根。中序遍历遵循「左根右」顺序，恰好按此约束依次访问节点。因此遍历结果必然升序。通法：任何 BST 的中序遍历都是排序操作，这是 BST 的核心用途之一。若遇「求二叉排序树中第 k 小元素」，中序遍历是必选策略。若遇「判断一棵树是否为 BST」，中序遍历是高效验证手段。

选项 B 设计陷阱：将「二叉树」与「二叉排序树」偷换概念。若题目说「任意二叉树中序遍历得递增序列」，这明显错误。但命题人只限定了 BST，让考生误以为中序遍历本身保证排序。若考生只背「中序遍历是排序」而不理解 BST 结构约束，就会掉进这个语义陷阱。更阴险的是，若考生混淆「二叉树」与「二叉排序树」，会误选 B，因为普通二叉树的中序遍历确实不保证排序。命题人特意用「二叉树」一词作为干扰项，考验考生对术语的精确理解。

若改成「前序遍历 BST 得递增序列？」答案变错，因为前序是「根左右」，根值会出现在中间。若改成「对二叉树中序遍历得递增序列？」答案也错，因二叉树无排序约束。若改成「后序遍历 BST 得递增序列？」答案更错，后序是「左右根」，根值在最后。刷到类似题先问：命题人想考我什么？是 BST 定义？是遍历顺序？还是两者结合？若改成「中序遍历二叉树得递增序列？」答案也错，因为二叉树无排序约束。命题人特意用「二叉树」一词作为干扰项，考验考生对术语的精确理解。若改成「中序遍历 BST 得递增序列？」答案正确，但命题人可能改成「前序遍历 BST 得递增序列？」来测试考生对遍历顺序的理解。

|