已知某棵二叉树的先序遍历和中序遍历的结果序列分别为ABCDEFGHI和BCAEDGHFI。
试构造出该二叉树。
【正确答案】：
【题目解析】：
第一步：可以由先序序列ABCDEFGHI确定出这棵二叉树的根结点是A；由根结点A和中序序列BCAEDGHFI可以得到A的左子树{BC}和右子树{EDGHFI}。
第二步：由A的左子树{BC}的先序序列BC可确定根结点是B；由根结点B和中序序列BC可以得到B的右子树{C}。
第三步：由A的右子树{EDGHFI}的先序序列DEFGHI可确定根结点是D；由根结点D和中序序列EDGHFI可以得到D的左子树{E}和右子树{GHFI}。
第四步：由D的右子树{GHFI}的先序序列FGHI可确定根结点是F；由根结点F和中序序列GHFI可以得到F的左子树{GH}和右子树是{I}。
第五步：由F的左子树{GH}的先序序列GH可确定根结点是G；由根结点G和中序序列GH可以得到F的左子树为空和右子树是{H}。即最终得到如图答案。