A-A+

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

2022-08-05 21:24:07 问答库 阅读 172 次

问题详情

若二叉树的先序遍历序列为ABDECF,中序遍历序列为DBEAFC,则其后序遍历序列为(8)。
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。

考点:序列