（11）树的度数是3。

2． 设下列二叉树是与某森林对应的二叉树，试回答下列问题。

（1）森林中有几棵树？

D A B （2）每一棵树的根结点分别是什么？ （3）第一棵树有几个结点？ （4）第二棵树有几个结点？

C E F G （5）森林中有几个叶结点？

H I J L K 解： （1） 4 （2） A，C，G，K （3） 6

（4） 2 （5） 7

3．二叉树按中序遍历的结果为：ABC，试问有几种不同形态的二叉树可以得到这一遍历结果？并画出这些二叉树。

答：

（1） 5种。 （2） A AC B A

C B B A A C

B C C B

4. 分别画出具有3个结点的树和三个结点的二叉树的所有不同形态。 答：

（1） 三个结点的树

（2） 三个结点的二叉树树

5

五. 应用题

1．已知一棵二叉树的后序遍历和中序遍历的序列分别为：

A，C，D，B，G，I，H，F，E和A，B，C，D，E，F，G，H，I。 请画出该二叉树，并写出它的前序遍历的序列。 答：恢复的二叉树为： E

B F H A D C G I

其前序遍历的序列为：E B A D C F H G I

2．已知一棵二叉树的前序遍历和中序遍历的序列分别为：

A，B，D，G，H，C，E，F，I和G，D，H，B，A，E，C，I，F。 请画出此二叉树，并写出它的后序遍历的序列。。

答：恢复的二叉树为： A

B C

F D E

G H I

其后序遍历的序列为：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

6

4. 把下列一般树转换为二叉树

(1) (2)

1

2

3 4 5 E

6 7

8 解：

（1） 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

A B C D F G H I J 2） A B E C F H DJ G I H I J K 7

（

6．把下列二叉树还原为森林

A

B

F C

D

解：还原后的二叉树为：

A

B C D

E G H I E F H G I 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 （1）画出该二叉树（3分）

（2）写出按层次遍历的结点序列（2分） 解： （1）

E

A F

H D

C I G B

（2）层次遍历的结点序列：E A F D H C G I B

8． 某二叉树的存储如下： lchild data

1 0 J 2 0 H 3 2 F 4 3 D 5 7 B 8

6 5 A 7 8 C 8 0 E 9 10 G 10 1 I