GESP 七级 · GESP 202506 C++ 七级 第 21 题

二叉排序树的中序遍历序列一定是有序的。

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

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

【考点】二叉排序树｜中序遍历｜递归性质

命题人专门考察二叉排序树的核心定义与遍历规律。GESP七级要求掌握树结构的基本性质，这道题就是用来卡住那些只背"二叉树遍历"却不懂"排序树约束"的考生——很多人误以为任何二叉树的中序遍历都可能是有序的，或者把"有序"理解成"节点值相等"，完全忽略了BST的严格大小关系。

看到"二叉排序树"三个字，必须立刻激活两个关键约束：左子树所有节点值<根节点<右子树所有节点值，以及中序遍历的固定顺序（左-根-右）。这两个条件叠加，就像把数值从小到大排列的链条，左子树先被访问（小值），根节点次之（中等值），右子树最后（大值）。所以，无论树多深多广，只要满足BST定义，中序遍历的输出必然是升序序列。这一类题的通法是：先定位数据结构的不变量（如BST的节点大小关系），再匹配遍历顺序对不变量的作用，最后看是否满足结论。

选B的人通常掉进三个典型坑：第一，把"二叉排序树"当成普通二叉树，以为中序遍历可以乱序；第二，对"有序"的理解偏差，误以为只要节点值相同就算有序，忽略了BST要求严格大小关系；第三，混淆遍历顺序，把中序（左-根-右）记成先序（根-左-右）或后序（左-右-根），导致逻辑链条断裂。最阴险的是题目没给示例，考生凭直觉觉得"树可能不平衡"就否定结论，但平衡性不影响排序性质。

如果把"二叉排序树"改成"普通二叉树"，中序遍历就不再保证有序；若改成"平衡二叉树"，结论依然成立，因为平衡性不破坏BST的大小约束。命题人真正想考的是：你能否区分"树的结构性质"（如平衡）和"数据的排序性质"（如BST）。刷到类似题时，先问自己"这个结构是否保证数据的某种关系"，再匹配遍历顺序是否暴露这种关系。