五. 应用题
（1）已知一棵二叉树的后序遍历和中序遍历的序列分别为：ACDBGIHFE和ABCDEFGHI。
请画出该二叉树，并写出它的前序遍历的序列。 解：恢复的二叉树为： E B A C DG F H I
其前序遍历的序列为：E B A D C F H G I
（2）已知一棵二叉树的前序遍历和中序遍历的序列分别为：ABDGHCEFI和GDHBAECIF。
请画出此二叉树，并写出它的后序遍历的序列。 解：恢复的二叉树为： A B D G H E I C F
其后序遍历的序列为：G H D B E I F C A
（3）已知一棵树的层次遍历的序列为：ABCDEFGHIJ，中序遍历的序列为：DBGEHJACIF，
请画出该二叉树，并写出它的后序遍历的序列。 解：
A
B C
DF E
G H I
J
后序遍历的序列：D G J H E B I F C A （4） 把下列一般树转换为二叉树
45
A
2
B C
4 3 5 F E G H I ① ②
1 D
6 7
J
8 解： ① ②
1
2
3
4
5
6
8 7 （5）把下列森林转换为二叉树
① ②
A F B C D G
E 解： A B F
C G H E DI
K J （6）把下列二叉树还原为森林
46
A B E C F H DJ G I ③ H I J K
A B F E G C D H I 解：还原后的二叉树为：
① ② ③ G A E
（7）某二叉树的结点数据采用顺序存储，其结构如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 E A F D H C G I B B C DF H I ① 画出该二叉树（3分）
② 写出按层次遍历的结点序列（2分） 解：
E
A F
H D
C B 层次遍历的结点序列：E A F D H C G I B （8）某二叉树的存储如下： lchild data rchild 1 0 J 0 2 0 H 0 3 2 F 0 4 3 D 9 5 7 B 4 6 5 A 0 7 8 C 0 8 0 E 0 9 10 G 0 10 1 I 0 G I 其中根结点的指针为6，lchild、rchild分别为结点的左、右孩子的指针域，data为
47
数据域。
① 画出该二叉树（3分）
② 写出该树的前序遍历的结点序列（2分） 解： A
B
C D
E F G
H I
J
前序遍历的结点序列：A B C E D F H G I J
（9）给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 28 3325 54406008 55
解：
中序遍历序列：55 40 25 60 28 08 33 54 中序线索二叉树：
28
3325
54406008
55
030
（10）画出表达式：-A+B-C+D 的标识符树，并求它们的后缀表达式。 解：
48