GESP 七级 · GESP 202503 C++ 七级 第 25 题

按照下面的规则生成一棵二叉树：以一个人为根节点，其父亲为左子节点，母亲为右子节点。对其父亲、母亲分别用同样规则生成左子树和右子树。以此类推，记录 30 代的直系家谱，则这是一棵满二叉树。

根据二叉树的遍历特性，先/前序遍历确定根节点，中序遍历确定左右子树范围，从而重构整棵树，再输出后序遍历结果。

易混淆三种遍历的顺序。先序：根左右；中序：左根右；后序：左右根。注意遍历结果中相邻节点的关系。

【考点】二叉树构造规则｜满二叉树定义｜递归计数

命题人利用"满二叉树"这一易混概念卡住考生：递归构造确实得到二叉树，但"满二叉树"要求每一层节点数都达到 2^k，30 代二叉树节点数 2^31-1 远超人类家族规模，题干却断言为"满二叉树"，属于绝对化表述陷阱。

解题关键在于区分"二叉树"与"满二叉树"：按规则每节点生左、右子，形成完美二叉树结构，但节点数量指数增长，命题人把结构特征偷换为"满二叉树"定义，若只背"二叉树=满二叉树"就会掉坑。

陷阱拆解：选项 A 看似合理，实则是把"树形结构"偷换为"满二叉树"，利用考生对"满二叉树"定义模糊（误以为只要每个节点有两个孩子就算满）；题干"30 代"是干扰项，无论几代都非满二叉树。命题人故意用"满二叉树"这一术语制造概念混淆，提醒刷到类似题先问"命题人想考定义还是结构"。

反命题视角：若把规则改为"每个节点最多一个子节点"，则生成的是链式树而非满二叉树；若问"节点总数"，答案应为 2^31-1，远超人类家族，故命题人故意用"满二叉树"这一术语制造概念混淆，提醒刷到类似题先问"命题人想考定义还是结构"。