第 8 题

T1 的中序序列为 DBEFAGC，根为 A，因此左子树有 D、B、E、F 共 4 个结点，右子树有 G、C 共 2 个结点。删去一个叶结点后，T2 有 6 个结点，其完全二叉树形状唯一：左子树有 3 个结点，右子树有 2 个结点。所以删去的结点一定来自原左子树，右子树仍按中序 G、C 排列。

用 x、y、z 表示删除后左子树的中序序列，T2 的结构如下：

flowchart TB
    A((A)) --- y((y))
    A --- C((C))
    y --- x((x))
    y --- z((z))
    C --- G((G))
    C ~~~ empty((" "))
    style empty fill:transparent,stroke:transparent,color:transparent

由图可知，T2 的前序序列为 A、y、x、z、C、G。删除叶结点只会从中序序列中移去该结点，不改变其余结点的相对顺序。于是从 DBEF 中删去一个结点，可得到下表：

各行都能通过在相应 T2 的左子树中补回一个叶结点，恢复原中序序列。例如第一行把 D 补为 B 的左孩子，第二行把 B 补为 D 的右孩子，第三行把 E 补为 F 的左孩子，第四行把 F 补为 E 的右孩子。

选项 D 的 AEFDCG 对应左子树前序 EFD，因此该子树的中序为 FED；这改变了原序列中 D、E、F 的相对顺序，不可能只通过删除一个叶结点得到。