GESP 六级 · GESP 202603 C++ 六级 第 22 题

在 C++ 中使用栈来非递归地实现二叉树的前序遍历时，为了保证遍历顺序正确，在处理完当前结点后，应该先将该结点的左孩子压入栈中，然后再将右孩子压入栈中。

递归问题关注两点：① 递归边界（终止条件）；② 递归关系（递推公式）。分析时展开前几步即可看出规律。

注意递归深度过大会导致栈溢出。递归必须包含终止条件，否则造成无限递归。

【考点】二叉树遍历｜栈的应用｜前序遍历顺序

1. 考纲定位 本题考查 GESP 六级"数据结构与算法"模块中栈与树遍历的综合应用。命题人刻意把"栈的后进先出"和"前序遍历的根左右"两个概念绑定，卡住那些只会背"非递归遍历要压栈"但没理解压栈顺序如何影响遍历顺序的考生。

2. 解题思维 前序遍历的正确序列是根→左→右。栈是后进先出，所以左子树必须先压入栈，这样弹出时才能优先访问左子树。因此入栈顺序必须是"先压右孩子，再压左孩子"，才能保证弹出顺序是左先于右。若按题干说的"先左后右"，弹出时就会先访问右子树，遍历序列变成根→右→左，违背前序定义。用递归类比：递归是先访问根，再递归左，再递归右；非递归时栈的压入顺序恰好与递归的调用顺序相反。

3. 陷阱拆解 错误选项 A 利用的是"直觉性误区"：很多考生认为"压栈顺序和访问顺序一致"，却忽略了栈的 LIFO 特性。命题人还埋了"边界条件"陷阱——空树或单节点树时顺序看似无关，但一旦树有左右子树，顺序就决定遍历结果。如果你只背"非递归遍历要压栈"，不理解"为什么先压右"，就会掉进这个坑。

4. 反命题思维 如果把题目改成"中序遍历"，正确压栈顺序会变成"先左再根再右"，非递归实现时需要在压栈前判断左孩子。若问"后序遍历"，栈中要压入根和右孩子，但弹出时还要处理左右顺序，导致实现更复杂。刷到类似题，先问自己：遍历顺序是什么？栈的弹出顺序必须符合该顺序，所以入栈顺序一定是其逆序。