GESP 六级 · GESP202609 C++ 六级 第 20 题

对任意一棵二叉搜索树执行中序遍历，得到的关键字序列一定是非递减的。

void inorder(TreeNode *root) {
if (!root)
return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}

先想二叉搜索树的定义：左子树所有节点值小于根节点，右子树所有节点值大于根节点。再看中序遍历顺序：左→根→右。把这两个规则叠在一起，就能推出遍历结果必然是从小到大。

容易把中序遍历和先序、后序搞混，以为任何遍历都能得到有序序列；或者误以为只要遍历二叉树就能排序，忘了前提是"二叉搜索树"。

1. 考纲定位

本题考查《GESP 六级》"数据结构与算法"模块中二叉搜索树与遍历的综合应用。命题人放这道题，就是要卡住那些只背"中序遍历是左-根-右"却不懂 BST 本质属性的考生——他们能写出遍历代码，但说不清为什么结果一定是有序的。

2. 解题思维

BST 的核心定义：对任意节点，其左子树所有节点值 < 该节点值 < 其右子树所有节点值。中序遍历的访问顺序是左子树→根节点→右子树。

把这两个规则叠在一起看：遍历到某个节点时，它左子树的所有值已经被访问过了（且都小于它），它右子树的所有值还没被访问（且都大于它）。因此访问顺序必然是从小到大。

用具体数字验证：构造一棵 BST，根节点 5，左子树节点 3，右子树节点 7。中序遍历输出：3 5 7，确实非递减。