问题
填空题
假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为______。
答案
参考答案：ABDEGHJCFI
解析： 若后序序列为非空，则后序遍历序列最后一个元素应是二叉树的根。那么前半部分非空应是二叉树左子树的中序遍历序列，后半部分非空应是二叉树右子树的中序序列。若判断出左子树非空，那么在后序序列的第二个元素即是左子树的根，再结合中序序列前半部分，递归地就可把左子树判定出来。同样的方法可把右子树判定出来，那么二叉树就唯一地确定出来，这样其前序序列便可得到。
[*]
对于本题，首先根据后序遍历序列确定这棵二叉树的根结点为A，然后将根据中序遍历序列确定左右子树的结点及中序遍历序列，分别是“DBGEHJ”和“CIF”；再根据左子树的后序遍历序列“DGJHEB”确定其左子树根结点为B及其左右子树的结点及中序遍历序列。以此类推，从而画出该二叉树，如图所示，从而确定其前序遍历序列为ABDEGHJCFI。