[简答题] (2)设一 棵二叉树的先序序列: ABDFC E GH ,中序序列:BF D AGE H C 1画出这棵二叉树。 2画出这棵二叉树的后序线索树。 3将这棵二叉树转换成对应的树(或森林)

1. 二叉树的结构如下图所示：

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

2. 后序线索树的结构如下图所示（其中粗实线表示线索）：

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

3. 将二叉树转换成对应的森林，即将每个节点的左子树切断，形成多棵树。转换后的森林如下图所示：

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

相关问题

设一棵二叉树的先序序列：ABDFCEGH,中序序列:BFDAGEHC。 画出这棵二叉树

根据先序序列和中序序列构造二叉树的步骤如下：
1. 先序序列的第一个元素为根节点，即A为根节点。
2. 在中序序列中找到根节点A，A左边的为左子树的中序序列，右边的为右子树的中序序列，即BFD为左子树的中序序列，GEHC为右子树的中序序列。
3. 根据左子树的中序序列BFD，可以得到左子树的先序序列为BFD，即B为左子树的根节点，F为B的左孩子，D为F的右孩子。
4. 根据右子树的中序序列GEHC，可以得到右子树的先序序列为GHEC，即G为右子树的根节点，H为G的左孩子，E为H的右孩子，C为E的右孩子。
5. 由此得到二叉树如下：

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

一棵二叉树的先序序列： abdfcegh，中序序列：bfdagehc。后序遍历序列为

首先，我们知道先序遍历（Preorder Traversal）的顺序是根节点 -> 左子树 -> 右子树，而中序遍历（Inorder Traversal）的顺序是左子树 -> 根节点 -> 右子树。既然给出了先序序列和中序序列，我们可以利用它们重建二叉树结构并找到后序遍历。

先序序列告诉我们根节点是 'a'，然后是 'b', 'd', ..., 'g', 'h'。
中序序列可以帮助我们确定每个节点的位置，因为 'b' 和 'd' 都出现在 'f' 之前，说明 'f' 是 'b' 和 'd' 的父节点；同样，'g' 在 'e' 后面，'h' 在 'c' 后面，我们可以推断出其他节点的相对位置。

现在，我们已经知道：
- 根节点：a
- 中序遍历中，a在'b'和'd'之间，所以'a'是'e'的父节点
- 'f'是'b'和'd'的父节点

继续推理，可以得到大致的二叉树结构：

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

后序遍历的顺序通常是左子树 -> 右子树 -> 根节点，所以我们按照这个顺序从叶子节点开始往回找，得到后序遍历序列为：bdcefgh。