题目
设一棵二叉树[1]的先序序列为A B D F C E G H，中序序列为B F D A G E H C。(1)画出这棵二叉树。(2)画出这棵二又树的后序线索树。(3)将这棵二叉树转换成对应的树(或森林)。
设一棵二叉树[1]的先序序列为A B D F C E G H，中序序列为B F D A G E H C。
(1)画出这棵二叉树。
(2)画出这棵二又树的后序线索树。
(3)将这棵二叉树转换成对应的树(或森林)。
题目解答
答案
(1) 二叉树的结构如下所示：
A
/ \
B C
/ / \
D E G
\ /
F H
(2) 后序线索树如下所示（节点中的箭头表示线索指针）：
F
/ \
B H
/ \ \
D E G
\
C
\
A
(3) 将二叉树转换成树（森林）如下所示：
A C
/ \ / \
B D E G
\ /
F H
这里将原二叉树的根节点A分为两棵子树，左子树以B为根，右子树以C为根。左子树以B为根，右子树以C为根，分别递归地构建了森林的结构。
解析
步骤 1：确定二叉树的结构
根据先序遍历和中序遍历的定义，先序遍历的第一个节点是二叉树的根节点，中序遍历中根节点的左侧是左子树，右侧是右子树。因此，可以确定二叉树的结构如下：
- 先序遍历：A B D F C E G H
- 中序遍历：B F D A G E H C
- 根节点：A
- 左子树：B F D
- 右子树：G E H C
步骤 2：确定后序线索树
后序线索树是将二叉树的后序遍历序列中的每个节点的左子节点和右子节点用线索指针连接起来的树。根据先序遍历和中序遍历，可以确定后序遍历序列为：F D B H G E C A。因此，后序线索树如下所示：
- F
- / \
- B H
- / \ \
- D E G
- \
- C
- \
- A
步骤 3：将二叉树转换成对应的树（或森林）
将二叉树转换成对应的树（或森林）的方法是将二叉树的根节点分为两棵子树，左子树以B为根，右子树以C为根。左子树以B为根，右子树以C为根，分别递归地构建了森林的结构。因此，将二叉树转换成对应的树（或森林）如下所示：
- A C
- / \ / \
- B D E G
- \
- F H
根据先序遍历和中序遍历的定义，先序遍历的第一个节点是二叉树的根节点，中序遍历中根节点的左侧是左子树，右侧是右子树。因此，可以确定二叉树的结构如下：
- 先序遍历：A B D F C E G H
- 中序遍历：B F D A G E H C
- 根节点：A
- 左子树：B F D
- 右子树：G E H C
步骤 2：确定后序线索树
后序线索树是将二叉树的后序遍历序列中的每个节点的左子节点和右子节点用线索指针连接起来的树。根据先序遍历和中序遍历，可以确定后序遍历序列为：F D B H G E C A。因此，后序线索树如下所示：
- F
- / \
- B H
- / \ \
- D E G
- \
- C
- \
- A
步骤 3：将二叉树转换成对应的树（或森林）
将二叉树转换成对应的树（或森林）的方法是将二叉树的根节点分为两棵子树，左子树以B为根，右子树以C为根。左子树以B为根，右子树以C为根，分别递归地构建了森林的结构。因此，将二叉树转换成对应的树（或森林）如下所示：
- A C
- / \ / \
- B D E G
- \
- F H