问题 单项选择题

若二叉树的先序遍历序列为ABDECF,中序遍历序列为DBEAFC,则其后序遍历序列为()。

A.DEBAFC

B.DEFBCA

C.DEBCFA

D.DEBFCA

答案

参考答案:D

解析:

本题要求根据二叉树的先序遍历和中序遍历求后序遍历。我们可以根据这棵二叉树的先序和中序遍历画出这棵二叉树,然后再得出其后序遍历结果。

根据先序和中序来构造二叉树的规则是这样的:

首先看先序遍历序列ABDECF,先序遍历中第一个访问的结点是A,这说明A是二叉树的根结点(因为先序遍历顺序是:根,左,右)。然后看中序遍历序列DBEAFC,中序中A前面有结点DBE,后面有结点FC。这说明DBE是A的左子树,FC是A的右子树(因为中序遍历顺序是:左,根,右)。

再回到先序遍历序列中看DBE的排列顺序(此时可以不看其他的结点),我们发现在先序遍历序列中B排在最前面,所以 B是A的左子树的根结点。

接下来又回到了中序遍历序列,中序遍历序列中D在B的前面,E在B的后面,所以D是B的左子树,E是B的右子树。

对于A的右子树,可同样依此规则得出。由此,可构造二叉树,如图4-8所示。

[*]

然后对这棵二叉树进行后序遍历,得到DEBFCA。

单项选择题
问答题 简答题