问题 填空题

假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为______。

答案

参考答案:ABDEGHJCFI

解析: 若后序序列为非空,则后序遍历序列最后一个元素应是二叉树的根。那么前半部分非空应是二叉树左子树的中序遍历序列,后半部分非空应是二叉树右子树的中序序列。若判断出左子树非空,那么在后序序列的第二个元素即是左子树的根,再结合中序序列前半部分,递归地就可把左子树判定出来。同样的方法可把右子树判定出来,那么二叉树就唯一地确定出来,这样其前序序列便可得到。 对于本题,首先根据后序遍历序列确定这棵二叉树的根节点为A,然后将根据中序遍历序列确定左右子树的节点及中序遍历序列,分别是“DBGE-HJ”和“CIF”;再根据左子树的后序遍历序列"DGJHEB"确定其左子树根节点为B及其左右子树的节点及中序遍历序列。以此类推,从而画出该二叉树,如下图所示,从而确定其前序遍历序列为ABDEGHJCFI。

判断题
单项选择题