已知一棵二叉树的前序遍历序列为ABDECFG,中序遍历序列为DBEAFCG,则这棵二叉树的后序遍历序列是什么?
答案解析
核心考点说明:本题考察二叉树的遍历性质以及如何根据前序和中序遍历序列推导后序遍历序列。 理解三种遍历方式的访问顺序是解题关键。
解题思路分析:前序遍历的第一个节点是根节点,中序遍历中根节点左右两侧分别是左子树和右子树的中序遍历结果。 利用这两个信息可以递归地构造二叉树。 前序遍历为ABDECFG,中序遍历为DBEAFCG。A是根节点, 中序中D、B、E在A的左边,C、F、G在A的右边。因此左子树的前序是BDE, 中序是DBE,所以B是左子树的根节点,D是B的左节点,E是B的右节点,此时左子树的后序为DEB。右子树前序为CFG, 中序为FCG,所以C是右子树的根节点,F是C的左节点,G是C的右节点,此时右子树的后序是FGC。最后将左子树的后序和右子树的后序以及根节点拼接,得到整体后序遍历结果。
每个选项的详细分析:
A. DEBFGCA:通过分析可以得到,这是正确的后序遍历序列。
B. EDBFGCA:左子树后序错误。根节点应该最后遍历
C. DEBGFCA:右子树的后序遍历错误
D. EDCBGFA:部分子树的后序错误,根节点不正确
易错点提醒:注意前序遍历和中序遍历的特点,结合起来递归分析,先确定根节点,然后递归分析左右子树。区分三种遍历访问结点的顺序。
正确答案的关键依据:前序遍历的第一个结点是根节点,中序遍历中根节点将序列分为左右子树,结合递归思想和后序遍历的访问顺序。
正确答案:A