2.已知一棵二叉树的先序序列:A B DF CE G H 和中序序列:B F DA GEH C，(1)画出得到的二叉树；(2)写出此二叉树的后序遍历序列和层次遍历序列：(3)画出由此二叉树转化的森林。

(1) 得到的二叉树如下图所示：

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

(2) 后序遍历序列为：DFBHGECA；层次遍历序列为：A B C D F E G H。

(3) 由此二叉树转化的森林如下图所示：

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

相关问题

设一棵二叉树的先序序列： a b d f c e g h ，中序序列： b f d a g e h c

这棵二叉树的结构如下：

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

其中，根节点为 a，左子树为 b d f，右子树为 c e g h。

设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C，画出这棵二叉树。

根据给定的先序遍历序列(A B D F C E G H)和中序遍历序列(B F D A G E H C)，我们可以重建这棵二叉树。先序遍历通常是根节点 -> 左子树 -> 右子树，而中序遍历则是左子树 -> 根节点 -> 右子树。

首先，我们知道B是第一个节点，也是中序遍历的第一个节点，所以它必然是根节点。然后我们从先序序列找到B，它是A的左孩子。接着，在中序序列中找到A，它位于B之后，F在其左边，说明F是A的左孩子；D紧随其后，也是A的左孩子。同样地，C在H之前，因此C是B的右孩子。

继续这个过程，我们得到：

1. 根节点B，左子树有A和F，右子树有C；
2. 节点A，左子树有F和D；
3. 节点F，无子节点；
4. 节点D，无子节点；
5. 节点C，无直接子节点，但后续的E和H属于它的子树；
6. 节点E和H作为C的子节点，由于中序遍历未给出它们之间的顺序，可以假设E在H之前。

下面是这棵树的结构示意：

        B
       / \
      A   C
     /     \
    F       E
               \
                H