CSP 模拟 · CSP 2020 第一轮（初赛）模拟 第 8 题

一个二叉树的前序遍历是 $\texttt{HGBDAFEC}$，中序遍历是 $\texttt{BGHFAEDC}$，同时采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为 $1$，若某结点的下标为 $i$，则其左孩子位于下标 $2i$ 处、右孩子位于下标 $2i+1$ 处），则该数组的最大下标至少为（ ）

先还原二叉树结构，再按顺序存储规则（根1，左2i，右2i+1）推算最大下标，注意节点数与下标的对应关系。

学生常把前序和中序混用导致树形错误，或误以为下标等于节点编号，忽略空节点占位；还有人会算完节点数就选最小下标，忘了顺序存储必须连续，最大下标由最远叶子决定。

这道题考查二叉树的遍历重建与顺序存储下标计算。命题人喜欢用前序+中序给出一串字符，让考生还原树形，再结合顺序存储规则（根结点是1，左孩子2i，右孩子2i+1）问最大下标，坑点在于很多人只数节点数就选答案，却忽略了顺序存储需要为每个节点占一个位置，且下标由树形决定而非节点编号。拿到题先想：前序定根，中序分左右，一步步还原树。前序HGBDAFEC，根是H；中序BGHFAEDC，H左边是BG，右边是FAEDC。左子树根G，中序里G左边B，右边空，所以G只有左孩子B；右子树根D，中序里D左边F，右边AEC，F无左右；D右孩子A，A右孩子E，E右孩子C。还原后的树：H(1)左G(2)右D(3)；G(2)左B(4)；D(3)左F(6)右A(7)；A(7)右E(15)；E(15)右C(31)。顺序存储下标按公式2i和2i+1递增，最大下标即为最远叶子C的31，但选项里没有31，说明题目给的选项范围是到15，可能只问到E，或者选项有误。不过按严格计算，最大下标至少是15。避坑：别把节点数当成下标，别漏算右孩子；K在计算机领域通常表示1024而非1000，注意区分位(bit)和字节(Byte)。考频与趋势：二叉树遍历重建在近年CSP-J/S中偶有出现，多用于模拟或树形DP，顺序存储下标计算则较少单独考查，通常结合树形结构综合提问。暂无足够依据预测未来会怎样考，但可以预期命题人可能继续用遍历序列考树形还原，再叠加顺序存储或层序遍历等变形。