A-A+
一棵二叉树的中序遍历序列为DBGEUJOCIF 后序遍历序列为DCJHEBIPCO 则其前序
问题详情
一棵二叉树的中序遍历序列为DBGEUJOCIF,后序遍历序列为DCJHEBIPCO,则其前序遍历序列为(87)。
A.OBCDEFGHIJ
B.OBDEGHJCFI
C.OBDEGHJPIC
D.OBDECJHCFI请帮忙给出正确答案和分析,谢谢!
参考答案
正确答案:B
解析:我们知道后序遍历序列最后一个节点是根结点,所以该二叉树根节点为O;又因为前序遍历序列中,左子树在根结点前面;右子树在根结点后面,所以O,前面的部分为其左子树,后面的部分为右子树。对得到的左子树和右子树用同样的方法继续进行划分,直至子树只剩一个结点,此时可以得到树的结构,于是可得到它的前序遍历序列。