GESP 六级 · GESP 202509 C++ 六级 第 18 题

一个含有 100 个节点的完全二叉树，高度为 8。

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

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

【考点】二叉树高度计算｜完全二叉树与满二叉树概念辨析

🎯 考纲定位：GESP 六级《数据结构》模块，命题人专卡"完全二叉树"与"满二叉树"定义混淆。考生若按"填充层"理解完全二叉树，会误判高度；实则此处暗指满二叉树（层数 h 对应节点数 2^{h+1}-1）。

🧠 解题思维：满二叉树高度 h 时节点总数 2^{h+1}-1。当 h=8 需 2^9-1=511 个节点，100 远不足。即便按完全二叉树定义，100 个节点高度应为⌊log₂100⌋=6。命题人借"完全二叉树"之名，考的是满二叉树的节点数公式与高度关系。

🪤 陷阱拆解：错选 A 者，往往混淆"完全二叉树"与"满二叉树"。完全二叉树仅要求"最后层左满"，高度可低至 7（如 128 个节点）；满二叉树则所有层填满，高度 h 对应节点必为 2^{h+1}-1。100 个节点无法构成高度 8 的满二叉树，更无法构成高度 8 的完全二叉树（128 个节点才到第 8 层）。命题人利用术语模糊性，测试对"满二叉树"节点数公式的掌握。

🔄 反命题思维：若把 100 换成 511，问"高度为 8 的满二叉树节点数"，则 A 正确。刷题时先问：命题人是否在考"满二叉树节点数公式"？