数据结构中根据根的次序访问序列求对应的树

Question

在数据结构中，如何通过访问序列确定对应的树？例如已知树的先根次序访问序列为GFKDAIEBCHJ.后根次序访问序列为DIAEKFCJHBG，求对应的树。请问解决方法，而不是答案，谢谢

Answer 1

很经典的题目啊，呵呵。
但是我不知道你这是不是二叉树，我目前只能给出二叉树的方法。
首先很明显。
根节点为G。
那么先序遍历中第二个字符就是根节点的左子树，即F为G的左子树的根节点。
而且后序遍历中倒数第二个字符就是根节点的右子树，即B为G的右子树的根节点。
上面这两条自己画个树，很容易理解的。
那么就可以把两个序列拆成3部分即。
G|FKDAIE|BCHJ.
DIAEKF|CJHB|G
即拆成了根，左子树，右子树三个部分。
这时，想到了什么？
递归实现二分！
既然把左子树，右子树的先序遍历，后序遍历都找出来了，那么对于子树，自然可以用相同的方法来继续拆分，然后用递归实现即可。
注：上述为二叉树的方法。
多叉树就恕在下才疏学浅，不能解答了。