题目
2.设一棵二叉树[1]的先序序列为A,B,D,F,C,E,G,H;中序序列为B,F,D,A,G,E,H,C。(1)画出这棵二叉树；(2)画出这棵二叉树的后序线索树；(3)将这棵二叉树转换成对应的树（或森林)。
2.设一棵二叉树[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 F E
/
G
H
(2) 后序线索树是将二叉树的每个结点的右子树为空的结点，以其后继结点替代其右指针，形成的一种特殊二叉树。具体的操作方式是，在后序遍历[3]的过程中，将前一个遍历的结点与当前结点相连。对于给定的二叉树，其后序线索树如下所示：
B
/ \
D F
/ \ \
G H E
\
C
\
A
(3) 将这棵二叉树转换成对应的树（或森林）可以进行如下的操作：根据根结点A，可以构建一棵树，该树的根结点为A，左子树为B-D-F，右子树为C-E-G-H。所以，转换后的树为：
A
/ \
B C
/ \ /
D F E
/
G
H
因此，将这棵二叉树转换成树后的结果为上述结构。
解析
步骤 1：确定二叉树的结构
根据先序序列和中序序列，可以确定二叉树的结构。先序序列的第一个元素是根节点，中序序列中根节点左边的元素是左子树，右边的元素是右子树。通过递归地应用这个规则，可以构建出整棵二叉树。
步骤 2：构建后序线索树
后序线索树是将二叉树的每个结点的右子树为空的结点，以其后继结点替代其右指针，形成的一种特殊二叉树。具体的操作方式是，在后序遍历的过程中，将前一个遍历的结点与当前结点相连。
步骤 3：将二叉树转换成对应的树（或森林）
将二叉树转换成对应的树（或森林）时，需要将二叉树的根节点作为树的根节点，然后将左子树和右子树分别转换成对应的子树。如果二叉树的根节点没有左子树或右子树，则对应的树（或森林）中就没有对应的子树。
根据先序序列和中序序列，可以确定二叉树的结构。先序序列的第一个元素是根节点，中序序列中根节点左边的元素是左子树，右边的元素是右子树。通过递归地应用这个规则，可以构建出整棵二叉树。
步骤 2：构建后序线索树
后序线索树是将二叉树的每个结点的右子树为空的结点，以其后继结点替代其右指针，形成的一种特殊二叉树。具体的操作方式是，在后序遍历的过程中，将前一个遍历的结点与当前结点相连。
步骤 3：将二叉树转换成对应的树（或森林）
将二叉树转换成对应的树（或森林）时，需要将二叉树的根节点作为树的根节点，然后将左子树和右子树分别转换成对应的子树。如果二叉树的根节点没有左子树或右子树，则对应的树（或森林）中就没有对应的子树。