BCSP-X · 2024 BCSP-X 上半年活动基础知识测评（初中组） 第 11 题

对于一棵二叉树，它的中序遍历结果为 LKMACBFEHGID，层次遍历结果为 AKBLMCDEFGHI，那么这棵二叉树对应的前序遍历结果为（ ）。

这题考二叉树的三种遍历。拿到题先别急着套公式，中序遍历里藏着唯一的根节点位置，层次遍历直接给根，两相对照就能把树‘搭’出来，再顺着根左右的顺序写前序就稳了。

最容易栽跟头的地方是混淆遍历顺序，把中序的‘左根右’当成前序去读，或者误以为层次遍历也能像中序那样直接定位根。还有种坑是死记硬背‘中序+前序定树’的结论，却忘了层次遍历其实也能和其中一种遍历唯一确定二叉树，导致不敢用层次信息去切分。画图时也容易把左右子树搞反，特别是当某子树在中序里是连续一段，但在层次里看起来像另一支时，容易把根找错。

这道题考查的是二叉树的遍历序列与树结构之间的对应关系，核心知识点就是前序、中序、层次这三种遍历的定义和它们在确定二叉树时的作用。命题人喜欢在这种单选题里挖坑：要么让你死记‘中序+前序定树’，却忘了层次遍历也能和其中一种遍历唯一确定二叉树；要么给你一堆看起来很像的序列，让你凭直觉去读，结果把左右子树搞反。所以拿到题，别急着套公式，先搞清楚每种遍历到底在干什么。前序是根左右，中序是左根右，层次是按层从上到下从左到右。这三个顺序里，只有中序能告诉你根节点在序列里的具体位置（因为它把根夹在中间），而前序和层次都能直接告诉你第一个访问的是根。这道题给的是中序和层次，其实完全够用——层次遍历的第一个字符就是整棵树的根，中序遍历里，根左边的全是左子树的中序序列，根右边的全是右子树的中序序列。这样一层一层往下切，就能把整棵树‘搭’出来，再顺着根左右的顺序写前序就稳了。具体到这道题，中序序列是 LKMACBFEHGID，层次序列是 AKBLMCDEFGHI。层次第一个是 A，所以 A 是根。在中序里找 A，它左边是 LKM，右边是 CBFEHGID，说明左子树的中序是 LKM，右子树的中序是 CBFEHGID。再看层次序列里 A 之后的部分：KBLMCDEFGHI。K 是左子树层次遍历的第一个，所以 K 是左子树的根；再往后，层次里紧跟的是 B、L、M、C、D、E、F、G、H、I。把左子树 K 的左子树中序（LK 里 L 在 K 左边，所以 L 是 K 的左孩子，K 的右子树中序是 M）和层次里 K 之后的部分对应起来，就能把左子树 K 的左右孩子定死：K 的左是 L，右是 M。同理，右子树根 C 在中序里左边是 B，右边是 FEHGID，层次里 C 之后是 D、E、F、G、H、I，把 C 的左子树中序 B 和层次里 C 之后的第一个 B 对应，就知道 C 的左孩子是 B；C 的右子树中序是 FEHGID，层次里 C 之后第二个是 D，但 D 不在 FEHGID 里，说明 D 是右子树根 C 的右孩子？不对，层次里 C 之后是 D、E、F、G、H、I，而右子树中序是 FEHGID，第一个是 F，所以 F 才是右子树根 C 的右孩子。这样一层层往下推，整棵树的结构就出来了。最后写前序，就是根左右的顺序：A 是根，左子树 K 的前序是 KLM，右子树 C 的前序是 CBFEDGHI，拼起来就是 AKLMBCDEFGHI，对应选项 A。避坑指南里要特别强调：千万别把中序的‘左根右’当成前序去读，那样会直接选错；也别以为层次遍历也能像中序那样直接定位根，层次遍历的第一个才是根，后面的顺序是按层排的，不能简单按中序的左右关系去切分。画图辅助分析是必须的，但画的时候要把中序和层次两个序列同时摆出来，用标记法一层层切，这样不容易出错。考频趋势上，二叉树遍历这类题在 CSP-J/S、NOIP 以及 GESP 中都是高频考点，近五年每年至少出现一次，且常以‘已知两种遍历求第三种’或‘已知遍历求叶子数/高度’的形式出现，命题人越来越喜欢把中序和层次组合考，因为层次遍历能唯一确定二叉树这点容易被忽视，正好用来挖坑。预测的话，未来大概率会继续考‘已知两种遍历确定树结构后求另一种遍历’，或者‘已知遍历求树的存储结构性质（如完全二叉树叶子数、顺序存储下标关系）’，但暂时没足够的数据支撑更细的预测，只能保守说会继续围绕遍历与树结构的对应关系出题。