第 8 题

6个结点的完全二叉树，前两层排满，第三层从左到右放置3个结点。按层序将位置编号为1至6，树形如下：

flowchart TB
    n1((1)) --- n2((2))
    n1 --- n3((3))
    n2 --- n4((4))
    n2 --- n5((5))
    n3 --- n6((6))
    n3 ~~~ x((" "))
    style x fill:transparent,stroke:transparent,color:transparent

位置1、2的度为2，位置3的度为1，其余位置的度为0。因此A只能位于位置1或2，B必须位于位置3。按“左子树→根结点→右子树”进行中序遍历，位置顺序为4、2、5、1、6、3，所以A应出现在中序序列的第2位或第4位，B必须在第6位。四个序列中，只有DEFACB同时满足这两个条件。其对应的层序标签为A、E、B、D、F、C，满足题设。