设一棵二叉树的先序序列为：A B D E G C F H中序遍历序列为：D B G E A C H F （1）画出这棵二叉树。 （2）写出该二叉树的先序、中序、后序遍历序列。 比较你写的先序和中序序列与题目的是否一致。

(1) 画出的二叉树如下所示：

        A
       / \
      B   C
     / \   \
    D   E   F
       /     \
      G       H

(2) 该二叉树的先序、中序、后序遍历序列分别为：

先序遍历序列：A B D E G C F H

中序遍历序列：D B G E A C H F

后序遍历序列：D G E B H F C A

其中，题目给出的先序遍历序列和中序遍历序列与我们求得的一致。

相关问题

已知某二叉树的先序遍历序列是c b a d e f g h,中序遍历序列是 a b e d c g f h,则其二叉树为：

首先根据先序遍历的顺序，我们可以确定根节点为c，然后我们在中序遍历序列中找到c的位置，可以发现a b e d在它的左边，而g f h在它的右边。因此，我们可以将整个二叉树分成左右两颗子树。接下来，我们可以对左右子树分别递归构造二叉树。

左子树的先序遍历序列是b a d e，中序遍历序列是a b e d，根据同样的方法，可以得到左子树的结构是：

    b
   / \
  a   d
     / \
    e   c

右子树的先序遍历序列是f g h，中序遍历序列是g f h，同样的方法，可以得到右子树的结构是：

    f
   / \
  g   h
     / \
    c   -

其中“-”代表空节点。综合左右子树，可以得到原二叉树的结构是：

        c
       / \
      /   \
     b     f
    / \   / \
   a   d g   h
      / \
     e   c

已知某二叉树的先序遍历序列是c b a d e f g h,中序遍历序列是 a b e d c g f h,则后序遍历序列是

根据先序遍历和中序遍历序列，可以重建出原始的二叉树，然后再进行后序遍历。具体步骤如下：

1. 先序遍历的第一个元素是根节点，即c。
2. 在中序遍历中找到c的位置，c左边的是左子树，右边的是右子树。a b e d是左子树的中序遍历序列，g f h是右子树的中序遍历序列。
3. 根据左子树的中序遍历序列a b e d，可以确定左子树的先序遍历序列为b a d e，即左子树的根节点为b，左子树的左子节点为a，左子树的右子节点为d，左子树的右子节点的左子节点为e。
4. 根据右子树的中序遍历序列g f h，可以确定右子树的先序遍历序列为f g h，即右子树的根节点为f，右子树的左子节点为g，右子树的右子节点为h。
5. 重建出原始的二叉树如下：

        c
      /   \
     b     f
    / \   / \
   a   d g   h
        \
         e

6. 对重建出的二叉树进行后序遍历，得到后序遍历序列为：a e d b g h f c。

因此，后序遍历序列为：a e d b g h f c。