如果一棵二叉树中序序列和后序序列分别为CDBEAGHFK和DCEBHGKFA，则该树前序序列为 ( ) 。
- A.KHGFEDCBA
- B.ABDCEFKGH
- C.ABEFCDGHK
- D.ABCDEFGHK
正确答案及解析
正确答案
D
解析
本题考查二叉树遍历和二叉树一些性质。二叉树是一个结点最多只有两个儿子结点树，其二叉树遍历有3种形式：(1)前序遍历：首先访问根结点，然后按前序遍历根结点左子树，再按前序遍历根结点右子树。(2)中序遍历：首先按中序遍历根结点左子树，然后访问根结点，再按中序遍历根结点右子树。(3)后序遍历：首先按后序遍历根结点左子树，然后按后序遍历根结点右子树，再访问根结点。要解答本题，需要一些技巧，我们从后序序列中可以看到A是最后一个，可以确定 A是整个二叉树根结点。再从中序序列CDBEAGHFK可以知道，CDBE是根A左子树中结点，而GHFK是根A右子树中结点。现在我们来分析左子树中情况，同样由后序序列中DCEB可以看出B是左子树根结点，由中序序列CDBE可以看出E是B右子树结点。同理，我们可以分析出整个二叉树结点分布。此二叉树前序遍历结果为ABCDEFGHK。
