习题解答
N、O、P、Q、R ，这棵树的度是 3 ，这棵树的深度是 4 ，结点F的孩子结点是 J、K ，结点G的父结点是 C ，结点 M、H、D、A 是结点R的祖先。
二、选择
1．已知一棵单右支的二叉树，如下左图所示。把它还原成森林，应该是 D 。
A．
B．
C．
D．
2．将一棵树Tr转换成相应的二叉树Bt，那么对Tr的先序遍历是对Bt的 A 。 A．先序遍历 B．中序遍历 C．后序遍历 D．无法确定 3．将一棵树Tr转换成相应的二叉树Bt，那么对Tr的后序遍历是对Bt的 B 。 A．先序遍历 B．中序遍历 C．后序遍历 D．无法确定
4．设森林F中有3棵树，依次有结点n1、n2、n3个。把该森林转换成对应的二叉树后，该二叉树的右子树上的结点个数是 D 。
A．n1 B．n1+n2 C．n3 D．n2+n3
5．设有由三棵树T1、T2、T3组成的森林，其结点个数分别为n1、n2、n3。与该森林相应的二叉树为Bt。则该二叉树根结点的左子树中应该有结点 A 个。 A．n1-1 B．n1 C．n1+1 D．n1+n2 6．现有一棵度为3的树，它有两个度为3的结点，一个度为2的结点，两个度为1的结点。那么其度为0的结点的个数应该是 C 。 A．5 B．8 C．6 D．9 注意：有n个结点的树，树中所有结点的度之和为n-1。现在这棵树应该满足条件： n-1 = 2*3 + 1*2 + 2*1 = 10 这表示该树共有11个结点（加上一个根结点）。在11个结点里，减去度为3、2、1的结点数5，剩下的就是度为0的结点。所以，该树有叶结点6个。 7．一棵有n个结点的树，在把它转换成对应的二叉树之后，该二叉树根结点的左子树上共有 B 个结点。 A．n-2 B．n-1 C．n+1 D．n+2 8．一棵有n个结点的树，在把它转换成对应的二叉树之后，该二叉树根结点的右子树上共有 A 个结点。 A．0 B．n C．n+1 D．n+2 9．下列说法中，正确的是 A 。 A．树的先序遍历序列与其对应的二叉树的先序遍历序列相同 B．树的先序遍历序列与其对应的二叉树的后序遍历序列相同 C．树的后序遍历序列与其对应的二叉树的先序遍历序列相同 D．树的后序遍历序列与其对应的二叉树的后序遍历序列相同
三、问答
1． 如图6-23所示的两棵树是一样的吗？为什么？
答：从图6-23(a)知，该树的根结点为A，下面有两棵子树，其中的一棵子树是最小树，只有根结点为B；另一棵子树的根结点为C，下面又有一棵最小子树，它的根结点为D。
从图6-23(b)知，该树的根结点也是A，它的下面也有两棵子树，这两棵子树的构成也与图6-23(a)里的相同。因此如果把树的子树视为是无序的，那么该图所展示的两棵树是一
- 25 -
习题解答
样的，否则是不一样的。
图6-23 树示例
2．二叉树与树有什么不同？
答：二叉树是一种树，但是一种特殊的树。第一，二叉树的每个结点至多可以有两棵子树，但树的每个结点可以有多棵子树；第二，二叉树的子树有左、右之分（即是有序的），但树的子树通常是不分顺序的。 3．为什么对于二叉树有中序遍历，而对一般树却没有中序遍历？
答：二叉树有中序遍历，是因为二叉树的每个结点最多只有两个子树，且子树有左、右之分，因此可以规定在访问左子树和右子树的中间去访问子树的根结点。但对于一般的树，其结点可以有任意数目的子树，因此，无法规定怎样的访问顺序才算是“中序”。所以，对一般的树没有中序遍历。 4．对于树的各种遍历，哪一种遍历是（1）首先访问树的根结点？（2）位于最左边的结点最先访问？（3）根结点最后访问？（4）最右边的结点最后访问？
答：（1）层次遍历和先序遍历总是首先访问树的根结点；（2）后序遍历总是最先访问位于树最左边的结点；（3）后序遍历总是最后访问树的根结点；（4）前序遍历总是最后访问树的最右边的结点。 5．一棵度为2的树与一棵二叉树有什么区别？ 答：从形状上看，一棵度为2的树与一棵二叉树没有什么区别。但度为2的树结点的子树一般是无序的，没有左、右之分；而二叉树结点的子树是有序的，它们之间有左、右之分，不能随意换位。
四、应用
1．已知一棵树的孩子链表表示法如图6-24所示，试画出该树。
图6-24 一棵树的孩子链表表示法 图6-25 树示例
答：该树形状如下图所示。
2．已知一棵树如图6-25所示。请画出该树的以下存储结构：（1）双亲表示法；（2）带
- 26 -
习题解答
双亲的孩子链表表示法（我们介绍过双亲表示法和孩子链表表示法，没有介绍过带双亲的孩子链表表示法。望能够把两者结合起来）；（3）孩子/兄弟链表表示法。 答：（1）双亲表示法如下图(a)所示；（2）带双亲的孩子链表表示法如图下(b)所示；（3）孩子/兄弟链表表示法如下图(c)所示。
3．将图6-26所示的二叉树转换成相应的森林。
图6-26 二叉树示例 图6-27 树示例
答：转换成的森林如下图所示。
4．给出如图6-27所示树的先序遍历序列和后序遍历序列。 答：该树的先序遍历序列为：A-B-E-F-K-L-M-C-G-D-H-I-J；该树的后序遍历序列是：E-K-M-L-F-B-G-C-H-I-J-D-A。
- 27 -
习题解答
5．将图6-28所示的森林转换成对应的二叉树。
图6-28 森林示例 图6-29 树示例
答：对应的二叉树如下图所示。
6．将图6-29所示的树转换成相对应的二叉树。 答：对应的二叉树如下图所示
第7章习题解答
一、填空
1．由4个顶点组成的一个连通图，应该有边 6 条。 2．在一个具有4个顶点的无向图中，要连通全部顶点，，至少需要 3 条边。 3．在无向图中，若顶点vi和vj之间有一条边（vi，vj）存在，那么则称顶点vi和vj互为 邻接 点。 4．图中顶点vi的“度”，是指与它 相邻接 的顶点的个数，并记为D(vi)。
- 28 -