数据结构单元练习7(2)

（9）树的深度是多少？

（10）以结点C为根的子树的深度是多少？ （11）树的度数是多少？ 答：

（1）A是根结点。

（2）叶结点：M，N，D，J，K，F，I。 （3）G的双亲：C。 （4）G的祖先：A，C。 （5）G的孩子：J，K。 （6）E的子孙：L，M，N。

（7）E的兄弟：D；F的兄弟：G，H。 （8）结点B的层次为2；结点N的层次是5。 （9）树的深度是5。

（10）以结点C为根的子树的深度是3。 （11）树的度数是3。

2． 设下列二叉树是与某森林对应的二叉树，试回答下列问题。 （1）森林中有几棵树？

A （2）每一棵树的根结点分别是什么？ B C （3）第一棵树有几个结点？ （4）第二棵树有几个结点？ D E F G （5）森林中有几个叶结点？ J I H K

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

（4） 2 （5） 7

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

C B A A B C A B C AB C B A C

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

（1） 三个结点的树

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

五. 应用题

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

A，C，D，B，G，I，H，F，E和A，B，C，D，E，F，G，H，I。 请画出该二叉树，并写出它的前序遍历的序列。 答：恢复的二叉树为： E B F A DH 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， 请画出此二叉树，并写出它的后序遍历的序列。。 答：恢复的二叉树为： A B C D E F G H I

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

I，F。

3． 已知一棵树的层次遍历的序列为：ABCDEFGHIJ，中序遍历的序列为：DBGEHJACIF，请画出该二叉树，并写出它的后序遍历的序列。 解：

后序遍历的序列：D G J H E B I F C A

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

1 (1) (2) DG B E H I J A C F

3 2 4 6 5 7 E B F J G H A C I D 解：

1 A 8 （1） 2 B （2）

3 4 E F C H D

5. 把下列森林转换为二叉树

E K B A C D F G I H J

解：

A B C F G DK C F H I E J G

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

E A

B D H 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 B A C DE F H G I