NOIP 普及 2012 第一轮 第 6 题：由中序遍历判断不可能的先序遍历

题目

如果一棵二叉树的中序遍历是 $\texttt{BAC}$，那么它的先序遍历不可能是（ ）。

选项

• A. $\texttt{ABC}$
• B. $\texttt{CBA}$
• C. $\texttt{ACB}$
• D. $\texttt{BAC}$

答案

C

题解

考点定位

本题考「中序/先序互推」,对应大纲 3.2.2 遍历（难度【3】）。

解题过程

中序 BAC：B 是最左（无左子），A 为根。可能的树：根 A、左子 B、右子 C ⇒ 先序 ABC ✓；根 A、左子树含 B、C（B 为根 C 为其右子）⇒ 先序 BAC？先序=根先：A,B,C ✓；右子树含 B、C（C 为根 B 为左）⇒ 先序 A,C,B=ACB ✓。

不可能的是 CBA：C 先于 A 输出意味着 C 在根的上方？先序首个必是根。若根是 A（中序中 B|A|C 分割），先序必以 A 开头；CBA 以 C 开头 ⇒ 根为 C，中序中 C 应分割左右——中序 BAC 里 C 在最后，左子树=B,A 两点，则先序 C 后接 BA 的某序=CBAX？只有 3 点：C 根，左子树含 B,A：先序 C,?,? 不可能等于 CBA（B、A 顺序需先序：C 先，子树先序=BA 意味着子树根 B——中序 BAC 的左段是 BA，其根是 B ✓ 先序 C,B,A？=CBA ✓！）。

再看 D（BAC）：根 B，中序 B 分割空|AC——左空右子 AC；先序 B,A,C ✓ 可能。

重新检验 A（ABC）：根 A，左 B 右 C ✓ 可能。C（ACB）：根 A，右子树含 B,C：中序右段=BC? 中序 BAC：左段 B、根 A、右段 C——右子树只有 C，先序 A,C,B 要求 B 在右子树……B 在中序里位于 A 左边，是左子树。先序 ACB 里 B 最后出现=右子树之后访问——矛盾？先序 ACB：A 根、C 是左子树先序（左子树={B}只有 1 点 ✗）。矛盾——但左段是 B 一点，先序 A 后应紧跟左子树根 B ⇒ ACB 不可能 ✓。

答案为 C 的官方口径：不可能的是 ACB。

选 C。

易错提醒

① 中序根分割左右；先序首=根；② 三结点树逐一画（5 种形态）对照最快。