选择题 16.某二叉树的中序遍历序列为CBADE,后序遍历序列为CBADE,则前序遍历序列为
【正确答案】 A
【答案解析】后序遍历次序是“左右根”,中序遍历次序是“左根右”。由定义可知:①后序遍历中最后一个就是树根结点,即E结点;②在中序遍历中,根结点左边的是左子树集,右边的是右子树集,即CBAD是根结点E的左子树集合。问题就会转化为:求后序遍历是CBAD,中序遍历是CBAD的子树,方法同上。因为中序遍历中,D结点右边没有结点了,所以D结点不包含右子树,否则就会被分为2个子问题。以下是这道题的详细推理过程:
步骤l:由CBADE得出根结点为E,由中序遍历可知{CBAD}E,右子树为空;
步骤2:由CBAD得出左子树集合的根节点为D,由中序可知{CBA}D,右子树为空;
步骤3:同理,二叉树更新后如下图所示。