问题 填空题

一棵二叉树的中序遍历结果是ABCDEFG,前序遍历结果是DBACFEG,则后序遍历结果为______。

答案

参考答案:ACBEGFD

解析: 我们分4大步骤来推理:
①找到根结点:由于前序遍历首先访问根结点,那么前序遍历结果的第一个结点肯定就是整个二叉树的根结点。前序遍历结果是DBACFEG,可知D为二叉树的根结点。
②分出左、右子树;中序遍历中,访问根结点的次序为居中,先访问左子树,再访问右子树。因此,在中序遍历的结果ABCDEFG中,以根结点D为中间界线,前面的ABC在左子树,后面的EFG在右子树。
③分析左子树:首先确定左子树ABC的根点。在前序遍历中,B最靠前,应该是ABC三个结点的根结点;在中序遍历中,A靠前,应该是ABC三个结点的左子树,C为右子树。
④分析右子树:同理分析EFG三个结点,就可以完整地画出整个二叉树的原貌了。
[*]
[知识拓展] 本题看似较难,其实比较简单。考生最关键的是把握中序、前序和后序遍历的定义,通过3者不同的遍历顺序,互相对照、步步推理,就能很快得到答案。

问答题 简答题
单项选择题 案例分析题