问题
单项选择题
若某二叉树的先序遍历序列和中序遍历序列分别为QBACD、BAQCD,则该二叉树的后序遍历序列为()。
A.QBCDA
B.DACBQ
C.ABDCQ
D.ABQDC
答案
参考答案:C
解析:
[要点解析] 本题考查二叉树的遍历运算特点。 先序遍历二叉树时,先访问根结点,然后先序遍历根的左子树,最后先序遍历根的右子树。因此,二叉树的先序遍历序列中第一个结点是树的根结点。 中序遍历二叉树时,首先中序遍历根结点的左子树,然后访问根结点,最后中序遍历根的右子树。因此,若已知二叉树的根结点,则依据中序遍历序列可将根的左、右子树结点区分开。 综上,首先根据先序序列确定根结点,然后依据中序遍历序列划分左、右子树,反复使用该规则,即可将每个结点的位置确定下来。 对于本题,首先从先序遍历序列QBACD可知,Q为树根,再由中序序列得知,B、A为左子树上的结点,C、D为右子树上的结点。 对Q的左子树进行先序遍历的序列为BA,即B是Q的左子树的根结点,在以Q为根的左子树中序序列中,A在B之后,所以A应在B的右子树上。依此类推,可知Q的右子树的树根为C,D为C的右子树上的结点。因此,对所得二叉树进行后序遍历,得到的序列是ABDCQ。