先序遍历。ABDFCEGH,中序遍历:BFDAGEHC，画出二叉树

我们可以通过已知的先序遍历和中序遍历来构造二叉树。具体步骤如下：

1. 先序遍历的第一个节点是根节点，即 A。
2. 在中序遍历中找到根节点 A，它将中序遍历分为两部分：BFD 和 GEHC。
3. 根据步骤 2 中的结果，我们可以分别得到左子树和右子树的先序遍历和中序遍历：
- 左子树的先序遍历为 BDF，中序遍历为 BFD。
- 右子树的先序遍历为 CEGH，中序遍历为 GEHC。
4. 重复步骤 1~3，递归构造左右子树。

最终得到的二叉树如下：

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

相关问题

设一棵二叉树的先序、中序遍历序列分别为： 先序：ABDFCEGH 中序：BFDAGEHC 则该二叉树的后序序列为：

根据先序遍历的性质，可以知道该二叉树的根节点是 A。然后根据中序遍历的性质，可以将其分为左子树和右子树：

左子树的中序遍历序列为 BFD，对应的先序遍历序列为 BDF。

右子树的中序遍历序列为 AGEHC，对应的先序遍历序列为 EGHAC。

然后对左右子树分别递归处理，得到左右子树的后序遍历序列，最后再加上根节点 A，即为整棵二叉树的后序遍历序列：

左子树的后序遍历序列为：DFB
右子树的后序遍历序列为：BGHECA
整棵二叉树的后序遍历序列为：DFBGHECA

设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：ABDFCEGH 中序遍历序列：BFDAGEHC （1)画出这棵二叉树。（2)画出这棵二叉树的后序线索树。（3)将这棵二叉树转换成对应的树（或森林）。

（1) 根据给定的先序遍历（A B D F C E G H）和中序遍历（B F D A G E H），我们可以推断出树的结构。先序遍历通常根节点在前，左子树再右子树，而中序遍历则是左子树到根再到右子树。通过比较，我们得知A是根节点，B在根的左边，D、F在B下面，C在F右边，E和G在D和F之间，H在最右边。

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

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

（2) 后序遍历线索树是通过在每个节点添加指向前两个兄弟节点的线索来表示后序遍历顺序的。对于这棵树，后序遍历为DBGEHFCA，所以我们可以在节点上添加相应的线索：

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

- 空白处代表空节点，有向线表示连接。
- `D`指向`B`和`E`，`B`指向`D`和`H`，`E`无线索，`F`指向`G`，`G`指向`F`和`C`，`C`指向`G`和`A`。

（3) 将这棵二叉树转换成对应的树（或森林），也就是恢复原始的二叉树形式，就是上述已经描述的结构。