第 9 题

中序遍历按“左子树→根结点→右子树”进行。根为 A，将中序序列 BDACFE 分为左子树 BD 和右子树 CFE。

左子树只有 B、D 两个结点，只能有 1 个叶子结点。整棵树有 3 个叶子结点，因此右子树必须有 2 个叶子结点。右子树共 3 个结点，只能由一个根和左右两个叶子组成；结合中序序列 CFE，可确定根为 F，左孩子为 C，右孩子为 E，其前序序列为 FCE。

左子树的中序序列为 BD，可以是 B 的右孩子为 D，也可以是 D 的左孩子为 B，对应的前序序列分别为 BD、DB。因此整棵树的前序序列只能为 ABDFCE 或 ADBFCE，选项中只有 ADBFCE 符合。其树形如下：

flowchart TB
    A((A)) --- D((D))
    A --- F((F))
    D --- B((B))
    D ~~~ X((空))
    F --- C((C))
    F --- E((E))
    style X fill:transparent,stroke:transparent,color:transparent

图中叶子结点为 B、C、E，按“根结点→左子树→右子树”遍历，得到 A、D、B、F、C、E。