五. 应用题

（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