题18

题18

题目

已知一裸二叉树的先序遍历结果为 ,中序遍历结果为 ,则后序遍历的结果为 ( ) .
A. CBEFDA
B. FEDCBA
C.
D. 不确定

分析

对于这种遍历序列问题, 先根据遍历的性质排除若干项, 若还无法确定答案, 则再根据遍历结果得到二叉树, 找到对应遍历序列。例如, 在本题中, 已知先序和中序遍历结果, 可知本树的根结点为 ,左子树有 和 ,其余为右子树,则后序遍历结果中, 一定在最后,并且 和 一定在前面,排除答案 和 。又因先序中有 ,中序中有 ,则 为这个子树的根,所以 在后序中排在 之后。
根据二叉树的递归定义, 要确定二叉树, 就要分别找到根结点和左、右子树。因此, 根据遍历结果, 必定要确定根结点位置和如何划分左、右子树, 才可以确定最终的二叉树。因此, 仅有先序和后序遍历不能唯一确定一棵二叉树, 而二者之一加上中序遍历都可以唯一确定一棵二叉树。如在本题中, 根据先序和中序遍历的结果确定二叉树的过程如下图所示。

解

A