发布时间 : 星期四 文章数据结构典型例题更新完毕开始阅读22e8e67b168884868762d6f1
树和二叉树
一、单项选择题
[例10-1] 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则 T中的叶子数为( )。
A．5 B．6 C．7 D．8
解析：假设度为0的结点数为n。，度为1的结点数为n1，……，度为4的结点数为n4，
则结点数n＝n0+n1+n2+n3+n4。又因为树的结点数为分支数加1，而分支数为n0×0+n1×1+n2×2+n3×3+n4×4，所以可得n0+n1+n2+n3+n4＝n1×1+n2×2+n3×3+n4×4+1，将已知条件代人得n0＝8。本题答案为：D。
[例10-2] 树最适合用来表示( )。
A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据 解析：由树的特点可知，本题答案为：C。
[例10-3] 如图10.13所示的二叉树中，( )不是完全二叉树。
解析：在一棵二叉树中，除最后一层外其余各层都是满的，最后一层或者是满的，或者是结点都集中在左边，这样的二叉树称为完全二叉树。由此可见，A不是完全二叉树，B、C是完全二叉树，D为空树，也是完全二叉树。本题答案为：A。
(例10-4] 如图10．14所示的二叉树的中序遍历序列是( )。
A．abdefgc B．dbgfeac C．dbfgeac D．dgfebac 解析：由二叉树中序遍历(LDR)可知，本题答案为：C。
(例10-5) 某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是 ( )。
A．空树或只有一个结点的二叉树 B．高度等于其结点数的二叉树 C．完全二叉树 D．二叉排序树
解析：对于高度等于其结点数的二叉树，每层只有一个结点，假设从上向下分别为a1，a2，…，an，则
21
先序遍历序列为a1，a2，…an，后序遍历序列为an，an-1,…，a1。本题答案为：D。 [例10-6] 按照二叉树的定义，具有3个结点的二叉树有( )种不同的树形。 A．3 B．4 C．5 D．6
n3C2C6n?5。本题答案为：C。 解析：n个结点的二叉树总数为＝
n?14(例10-7) 在一非空二叉树的中序遍历中，根结点的右边( )。 A．只有右子树上的结点 B．只有右子树上的部分结点 C．只有左子树上的结点 D．只有左子树上的部分结点
解析：在中序遍历序列中，根结点将左、右子树上的结点分开，左边为左子树上的结点，右边为右子树上的结点。本题答案为：A。 [例10-8] 用于编码的是( )。 A．完全二叉树 B．二叉排序树 C．最优二叉树 D．空树
解析：用于编码的二叉树是哈夫曼树，又称最优二叉树。本题答案为：C。 (例10-9) 根据使用频率，为5个字符设计的哈夫曼树编码不可能是( )。 A．000，001，010，011，1 B．0000，0001，001，01，1 C．000，001，01，10，11 D．00，100，101，110，111
解析：哈夫曼树中只有度为0或2的结点，D不满足这种条件。本题答案为：D。 [例10-10] 一个具有1024个结点的二叉树的高h为( )。 A．11 B．10
C．11~1024之间 D．10至1024之间
解析：根据二叉树的性质2，可知高度为k的二叉树至多有2k-1个结点，即高度为10的二叉树至多有1023个结点；而当二叉树每层只有一个结点时，树高和结点数是一样 的。本题答案为：C。 二、判断题
[例10-11] 二叉树是一种特殊的树，度为2的树就是二叉树。
解析：错误。二叉树是一种特殊的树，但是度为2的树不一定是二叉树。原因是二叉树为有序树，并且二叉树中不一定存在度为2的结点。
[例10-12] 二叉树的先序遍历序列中，任意一个结点均处于其孩子结点前面。 解析：正确。先序遍历时，应先访问根结点，再访问其孩子。 [例10-13] 将一棵树转换成二叉树后，根结点没有左子树。
解析：错误。从树和二叉树的相互转换可知，由一棵树转换成的二叉树，根结点必无 右子树，没有左子树的情况只有两种：空树和只有一个结点的树。
(例10-14) 用树的先序遍历序列和中序遍历序列可以导出树的后序遍历序列。
解析：正确。用树的先序遍历序列或后序遍历序列加上中序遍历序列可以恢复二叉树，从而可以得出另一个遍历序列。
(例10-15) 中序遍历一棵二叉排序树的结点就可得到值递增的结点序列。
解析：正确。二叉排序树的特点是左子树上所有结点的值小于根结点的值，根结点的值小于右子树上所有结点的值。中序遍历的顺序是先遍历左子树，再访问根结点，最后遍历右子树。因此，中序遍历一棵二叉排序树的结点所得到的序列是递增的，命题正确。
(例10-16) 在由同样的叶子结点构成的树中，哈夫曼树是带权路径长度最小的树，路径上权值较大的结点离根较近。
解析：正确。由哈夫曼树的定义可知本命题正确。 三、填空题
22
(例10—17) 有一棵树如图10.15所示，试回答下列问题： (1)这棵树的根结点是 。 (2)这棵树的叶子结点有 。 (3)结点b的双亲是 。 (4)结点b的子孙有 。 (5)结点b的兄弟是 。 (6)树的度为 。
(7)树的深度为 。
解析：由树的相关定义可知，本题答案为：(1)a；(2)c，d，e，h5(3)a；(4)d，e，f，g，h； (5) c；(6) 3；(7) 5。
[例10-18] 结点数最少的二叉树为 。 解析：本题答案为：空树。
[例l0-19] 在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是 。
解析：由二叉树的性质4可知，具有n个结点的完全二叉树的深度为[1bn]+1或[1b(n+1)]。又因为用顺序存储的二叉树的结点编号和完全二叉树中相同位置上结点的编号是一致的，所以如果编号为i和j的两个结点处在同一层，则有[1bi]＝[1bj]。本题答案为：[1bi]＝[1bi]。
[例10-20] 深度为h的完全二叉树至少有 个结点；至多有 个结点；h和结点总数n之间的关系是 。
解析：由二叉树的性质2可知，高度为k的二叉树至多有2k一1个结点。由性质4可知，具有n个结点的完全二叉树的深度为[1bn]+1或[1b(n+1)]。所以本题答案为：2h 1;2 h-1;h=[1bn]+1或h＝[1b(n+1)]。
—
[例10-21] 在二叉树中，指针p所指结点为叶子结点的条件是 。
解析：叶子结点的特点是没有子树。本题答案为：p一>lchild = =NULL && p一>rchild= =NULL。 [例10-22] 高度为8的完全二叉树至少有 个叶子结点。
解析：在完全二叉树中，度为1的结点要么没有，要么只有一个；又由二叉树的性质3
可知，任何一棵二叉树的叶子结点数no为度为2的结点数n2加1。由此可知，完全二叉树的叶子结点数基本是随着总结点数的增多而增多的，即在同样高度的完全二叉树中，结点最少的完全二叉树的叶子结点也最少。高度为8的完全二叉树的结点最少有27个，叶子结点为26个。本题答案为：64。
[例10-23] 一棵二叉树的先序遍历、中序遍历和后序遍历序列分别如下，其中有一部分未显示出来。试填补空格处的内容。
先序遍历序列： B F ICEH G 中序遍历序列： D KFIA EJC 后序遍历序列： K FBHJ G A
解析：由三种遍历序列的特点可知，先序遍历为每棵子树的根结点总在该子树中其他结点前被遍历；
23
中序遍历为左子树结点在前，根结点次之，右子树结点最后；后序遍历为每棵子树的根结点总在该子树中其他结点后被遍历。由此可推断出：先序遍历序列空格中依次填入A、D、K、J，中序遍历序列中依次填入B、H、G，后序遍历序列中依次填人D、I、E、C。
[例10-24] 若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度为 。 解析：本题答案为：69。 四、应用题
(例10-25) 从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转换成二叉树的基本目的是什么?并指出树和二叉树的主要区别。
解析：树和森林转换成二叉树是为了采用二叉树的存储结构并利用二叉树的已有算法解决树和森林的有关问题。
树和二叉树的主要区别是：树中结点的最大度数没有限制，而二叉树结点的最大度数为2；树中结点的子树无左、右之分，而二叉树中结点的子树有严格的左、右之分。
（例l0-26) 请说明一棵二叉树进行先序、中序和后序遍历后，其叶子结点的相对次序是否会发生改变?为什么?
解析：在二叉树中，叶子结点必在某结点的左或右子树中。因为三种遍历方法对左、右子树的遍历都是按左子树在前、右子树在后的顺序进行的，所以在三种遍历序列中，叶子结点的相对次序是不会发生改变的。
[例10-27] 一棵完全二叉树用一维数组存放为：abcdefghijk。请写出中序遍历该二叉树的访问结点序列。
解析：由顺序存储完全二叉树的存储方式，我们很容易画出这棵完全二叉树的树形结构。对其进行中序遍历得到的序列为：hdibjekafcg。
[例10-28] 假设二叉树采用顺序存储结构，如图10.16所示。 (1)画出此二叉树树形。
(2)写出此二叉树的先序、中序和后序遍历序列。 (3)将此二叉树转换为森林。
解析：(1)此二叉树树形如图10．17所示。 (2)该二叉树的遍历序列如下： 先序遍历序列：bcdfeagh 中序遍历序列：cfdebahg 后序遍历序列：fedchgab
(3)转换成的森林如图10.18所示。
(例10-29) 已知哈夫曼树的叶子结点数为no，试推导出该哈夫曼树共有多少个结点。
解析：设度为1的结点数为n1，度为2的结点数为n2，结点总
24