GESP 六级 · GESP 202412 C++ 六级 第 6 题

以下关于树的说法，（ ）是正确的。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】树｜二叉树｜遍历

1. 考纲定位：本题出自 GESP 六级"树与二叉树"模块，命题人专攻二叉树结构认知盲区。树是数据结构核心，但二叉树是树在代码中的具体形式，学生常把"树"和"二叉树"混为一谈，导致概念混淆。

2. 解题思维：先看 A——二叉树叶子结点度为 0，命题人故意写 2 诱导学生把"满二叉树"和"普通二叉树"混淆；B 是满二叉树定义直接推导，每一层结点数正好是 2^(层数-1)，这是满二叉树的数学本质；C 项偷换概念，度之和等于所有结点度之和，叶子结点度为 0，显然不相等；D 项先序中序遍历结果相同只有当树退化成单链表才成立，命题人用"一定"制造陷阱。

3. 陷阱拆解：A 项利用学生把"叶子结点"与"度为 2 的结点"混淆，命题人故意写"度一定是 2"；B 项是满二叉树标准定义，命题人用 O(2^(层数-1)) 的数学表达，考察学生是否掌握满二叉树的数学本质；C 项把"所有结点的度之和"与"所有叶子结点的度之和"混为一谈，叶子结点度为 0，命题人诱导学生把"度"当成"数量"；D 项"一定相同"是绝对化表述，命题人让考生误以为先序中序遍历结果相同是二叉树性质，实际上只有单链表才相同。先序遍历顺序是根左右，中序遍历是左根右，若树是单链表，先序遍历是根，中序遍历也是根，所以相同；否则不同。

4. 反命题思维：命题人若把 B 改成"完全二叉树"，答案会因层数定义不同而变；若把 D 改成"先序后序遍历结果相同"，会考察树退化成单链表的情形。刷到类似题先问自己：这是考定义、考数学推导、还是考遍历逻辑？命题人想区分学生是否真正理解二叉树的结构，还是仅仅记忆遍历顺序。