不可不会的二叉树

二叉树前序中序后序
悬赏分：5 | 解决时间：2010-4-24 20:54 | 提问者：huangti27
关于二叉树中，对于前序、中序、后序三者中，知道知道两个，求另外的一个有什么方法？  比如题目：若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（）？
       最佳答案
对于例题的后序遍历的答案是，gdbehfca.
解答过程：
1）定义解释：树的遍历的三种情况，是根据左子树、右子树、根这3者的不同访问次序来定义的。根左右（根先访问），则为先序遍历；左根右，则为中序遍历；左右根，则为后序遍历。
2）已知先序和中序遍历结果，求树的结构和后序遍历结果：
先序遍历结果给我们带来的信息是，根在哪。
中序遍历结果给我们带来的信息是，左、右子树在哪。
所以树结构的还原过程是，根据先序找到一个根；然后根据这个根和中序遍历结果找到它的相应的左、右子树；依次往下。

对于例题而言：
先序遍历的第一个节点是a，则说明a是整棵树的根。然后在中序遍历结果中，由a断开，找到a的左子树和右子树，即dgb是a的左子树中的节点集合，echf是a的右子树集合。（dgb）a(echf)

然后开始递归求解：还原（dgb）和(echf)
（dgb）的先序遍历结果是：bdg（从题目中的先序遍历中，截取）
（dgb）的中序遍历结果是：dgb（从题目中的中序遍历中，截取）
所以b为根，（dg）为左子树，右子树为空。即（dgb）= (dg)b

同理：（echf）=（e）c（hf）

第3次递归：（dg）= d(g);(hf)= (h)f

最后得到的结果就是：
（（d(g)）b）a （(e)c((h)f)）
(在这种表示中，括号的层数代表在树中的层数)
             a
        b        c
    d          e    f
      g            h

根据这个树，后序遍历为先左、右，最后根
先访问（dgb） (echf) 然后是a
（dgb）这棵树的后序遍历为gdb
（echf）这棵树的后序遍历为ehfc
所以最后结果为gdb ehfc a