试题与答案

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

题型:填空题

题目:

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

答案:

参考答案:ACBEGFD

解析: 由于在前序遍历中首先访问根结点,因此,前序序列中的第一个结点为二叉树的根结点,即D为二叉树的根结点。又由于在中序遍历中访问根结点的次序为居中,而访问左子树上的结点为居先,访问右子树上的结点为最后,因此,在中序序列中,以根结点(D)为分界线,前面的子序列(ABC)一定在左子树中,后面的子序列(EFG)一定在右子树中。同样的道理,对于已经划分出的每一个子序列的所有结点中,位于前序序列最前面的一个结点为子树的根结点,而在中序序列中位于该根结点前面的结点构成左子树上的结点子序列,位于该根结点后面的结点构成右子树上的结点子序列。这个处理过程直到所有子序列为空为止。
根据上述道理,该二叉树恢复的过程如下图所示:
[*]
根据后序遍历的方法,对该二叉树后序遍历的结果为ACBEGFD。

试题推荐
题型:单项选择题

《城乡规划法》规定,编制城乡规划必须遵守国家有关标准,下列关于对城乡规划编制单位违反国家有关标准编制城乡规划的表述中,错误的是()

A.由所在地城市、县人民政府城乡规划主管部门责令限期改正,处合同约定的规划编制费1倍以上2倍以下的罚款

B.情节严重的,责令停业整顿,由原发机关降低等级或者吊销资质证书

C.造成损失的,依法承担赔偿责任

D.规划内容有损人民群众利益的,应依法追究其法律责任

查看答案
微信公众账号搜索答案