一棵二叉树的先序遍历序列为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为( )。

Question

A.CBEFDA
B.FEDCBA
C.CBEDFA
D.不确定

Answer 1

【答案】：A
二叉树的先序遍历序列和中序遍历序列一起可以确定这棵二叉树的形态。本题的解题思路是先根据题设确定这棵二叉树的形态，然后再用后序遍历此二叉树，得到后序遍历序列。根据先序遍历序列，A是二叉树的根结点。根据中序遍历序列，则二叉树的形态一定如图4—9所示。9考虑A的左子树。根据二叉树的先序遍历序列，可知由B和C构成的二叉树，B为根结点，因为在先序遍历序列中，B比C先被访问。再根据中序遍历序列，可知A是B的左孩子，因为B是由B和C构成的二叉树的根结点，C在B前被访问，根据中序遍历的顺序，可知C是B的左孩子。如图4—10所示。考虑A的右子树。根据二叉树的先序遍历序列，可知由E、D和F构成的二叉树，D为根结点，因为在先序遍历序列中，D比E、F先被访问。再根据中序遍历序列，可知E是D的左孩子，因为D是由E、D和F构成的二叉树的根结点，E在D前被访问，根据中序遍历的顺序，可知E是D的左孩子。而F是D的右孩子，F在D后被访问，根据中序遍历的顺序，可知F是D的右孩子。如图4—11所示。至此，二叉树被确定下来了。我们再对它进行后序遍历，得到后序遍历序列为：CBEFDA。因此本题答案为A。