单选题 若二叉树的先序遍历序列为ABDECF,中序遍历序列为DBEAFC,则其后序遍历序列为______。
【正确答案】 D
【答案解析】此题要求根据二叉树的先序遍历和中序遍历求后序遍历。我们可以根据这棵二叉树的先序和中序遍历画出这棵二叉树。
根据先序和中序遍历来构造二叉树的规则是这样的:首先看先序,先序遍历中第一个访问的节点是A,这说明A是二叉树的根节点(因为先序遍历顺序是:根、左、右)。然后看中序,中序中A前面有节点D、B、E,后面有节点F、C。这说明D、B、E是A的左子树,F、C是A的右子树。我们再回到先序遍历中看D、B、E的排列顺序(此时可以不看其他节点),我们发现在先序中B排在最前,所以B是A左子树的根节点。接下来又回到了中序,中序中D在B前面,E在B后面,所以D是B的左子树,E是B的右子树。依此规则可构造二叉树,如图所示。然后对这棵二叉树进行后序遍历得到DEBFCA。