设一棵二叉树的先序序列为：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

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

相关问题

设一棵二叉树的先序序列： 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

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

首先，让我们根据给定的先序遍历（Preorder）序列 A B D F C E G H 和中序遍历（Inorder）序列 B F D A G E H C 来重建这棵二叉树。

先序遍历的特点是根节点 -> 左子树 -> 右子树，所以A应该是根节点。中序遍历的特点是左子树 -> 根节点 -> 右子树，通过这个我们可以确定B、D和F应该在A的左边作为左子树，而A右边的部分就是G、E、H和C。

根据以上信息，我们可以逐步构建树结构：

1. 根节点A
- 左子树：B
- 左子树：F
- 右子树：D
- 右子树：C
- 左子树：E
- 右子树：G
- 最右子树：H

接下来，我们绘制后续线索树（Postorder Traversal Invariant），也叫线索化二叉树。线索化二叉树会添加额外的线索指针，使得每个节点都包含指向其左孩子和右孩子的直接引用，如果子节点不存在，则引用为空。按照后序遍历（根节点 -> 左子树 -> 右子树）的原则：

- A: 没有后继（因为H是右子树中最远的）
- B: 后续是F（F->D）
- D: 后续是A（A->C）
- F: 后续是B（B->空，因为下一个节点是D）
- C: 后续是G（G->H）
- E: 后续是C（C->空，因为下一个节点是G）
- G: 后续是H（H->C）

这就是按照题目描述画出的二叉树及其后续线索树。以下是简单的图形表示：

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