1、第六章树和二叉树（下载后用阅读版式视图或 web 版式可以看清）习 题一、选择题1有一“遗传”关系：设 x 是 y 的父亲，则 x 可以把它的属性遗传给 y。表示该遗传关系最适合的数据结构为( )。A.向量 B.树 C 图 D.二叉树2树最合适用来表示( )。A.有序数据元素 B 元素之间具有分支层次关系的数据C 无序数据元素 D.元素之间无联系的数据3树 B 的层号表示为 la，2b，3d，3e，2c，对应于下面选择的( )。A. la (2b (3d,3e),2c) B. a(b(D,e),c)C. a(b(d,e),c) D. a(b,d(e),c)4.高度为 h 的完全二叉树至少有(
2、)个结点，至多有( )个结点。A. 2h_l B.h C2h-1 D. 2h5.在一棵完全二叉树中，若编号为 f 的结点存在右孩子，则右子结点的编号为( )。A. 2i B. 2i-l C. 2i+l D. 2i+26.一棵二叉树的广义表表示为 a(b(c)，d(e(，g(h)，f)，则该二叉树的高度为 ( )。A.3 B.4 C.5 D.67.深度为 5 的二叉树至多有( )个结点。A. 31 B. 32 C. 16 D. 108.假定在一棵二叉树中，双分支结点数为 15，单分支结点数为 30 个，则叶子结点数为( )个。A. 15 B. 16 C. 17 D. 479.题图 6-1 中，(
3、 )是完全二叉树，( )是满二叉树。10.在题图 6-2 所示的二叉树中：(1)A 结点是A.叶结点 B 根结点但不是分支结点C 根结点也是分支结点 D.分支结点但不是根结点(2)J 结点是A.叶结点 B根结点但不是分支结点C 根结点也是分支结点 D.分支结点但不是根结点(3)F 结点的兄弟结点是A.E B.D C空 D.I(4)F 结点的双亲结点是A.A B.B C.C D.D(5)树的深度为A.1 B.2 C.3 D.4(6)B 结点的深度为A.1 B.2 C.3 D.4(7)A 结点所在的层是A.1 B.2 C.3 D.411.在一棵具有 35 个结点的完全二叉树中，该树的深度为( )。
4、A.5 B.6 C.7 D.812. 一棵有 124 个叶结点的完全二叉树，最多有( )个结点。A247 B248 C 249 D25013.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组 R1n中，结点 Ri若有左子树，则左子树是结点( )。A. R2i+l B. R2i C.Ri/2 D. R2i-114.在一非空二叉树的中序遍历序列中，根结点的右边( )。A.只有右子树上的所有结点 B.只有右子树上的部分结点C.只有左子树上的部分结点 D.只有左子树上的所有结点15一棵度为 m 的树中，有 ni 个度为 1 的结点，有 n2 个度为 2 的结点，有 nm 个度为 m 的结点，则该树
5、的叶结点数为( )。A. n1+n2+.+nm B. (m-l) nm+.+n2+1C.n1+n2+1 D. nl-n216.已知某二叉树的中序遍历序列是 debac，后序遍历序列是 dabec，它的前序遍历序列是( )。A. acbed B. decab C. deabc D. cedba17.在一棵二叉树的二叉链表中，空指针域等于所有非空指针域数加( )。A.2 B.1 C.0 D.-118.线索二叉树是一种( )结构。A.逻辑 B逻辑和存储 C物理 D.线性19.由权值分别是 8，7，2，5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。A. 23 B. 37 C46 D. 43
6、20.设 T 是哈夫曼树，具有 5 个叶结点，树 T 的高度最高可以是( )。A.2 B.3 C.4 D.5二、填空题1.对于一棵具有 n 个结点的树，该树中所有结点的度数之和为_。2.在树型结构中，树根结点没有_结点，其余每个结点有且只有_个前驱结点：叶子结点没有_结点，其余每个结点可以有_后继结点。3.有一棵树如题图 6-3 所示，回答下面的问题。这棵树的根点是_；叶子结点是_；结点 k3 的度是_；结点 k3 的子女是_；结点 k3 的父结点是_；这棵树的度为_；这棵树的深度是_。4.假定一棵树的广义表表示为 A(B(E)，C(F(H ，I ，J，G)，D) ，则该树的度为_，树的深度为
7、_，终端结点的个数为_，单分支结点的个数为_，双分支结点的个数为_，3 分支结点的个数为_，C 结点的双亲结点为_，其孩子结点为_。5.一棵深度为 h 的满 k 叉树有如下性质：第 h 层上的结点都是叶子结点，其余各层上的每个结点都有 k 棵非空子树。如果按层次顺序（同层自左至右）从 1 开始对全部结点编号，则：(1)第 i 层结点数目是_。(2)编号为 n 的结点的双亲结点（若存在）的编号是_ 。(3)编号为 n 的结点的第 i 个孩子结点（若存在）的编号是_。(4)编号为 n 的结点有右兄弟的条件是_：其右兄弟的编号是 _。6前序遍历一棵树相当于_树中对应的二叉树，后序遍历一棵树则相当于树
8、中对应的二叉树。7二叉树的遍历分为_ ，树与森林的遍历包括_。8一棵二叉树的第 i(i=1)层最多有 _个结点；一棵有 n(n0)个结点的满二叉树共有_ 个叶子和_个非终端结点。9.在一棵二叉树中，假定双分支结点数为 5 个，单分支结点数为 6 个，则叶子结点为_个。10在一棵二叉树中，第五层上的结点数最多为_。11.对于一棵具有 n 个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_个，其中_个用于链接孩子结点，_个空闲着。12.前序遍历的顺序是 ABDGEHICFJ，则二叉树的根是_。13.从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_14.结点最
9、少的树为_ ，结点最少的二叉树为_。15.一棵完全二叉树按层次遍历的序列为 ABCDEFGHI，则在前序遍历中结点 E 的直接前驱为_ ，后序遍历中结点 B 的直接后继是_。16.某二叉树的中序遍历序列为 ABCDEFG，后序序列为 BDCAFGE，则该二叉树结点的前序序列为_，该二叉树对应的森林包括_棵树。17.用一维数组存放的一棵完全二叉树如题图 6-4 所示。则后序遍历该二叉树时结点访问的顺序为_。18.由 n 个权值构成的哈夫曼树共有_个结点。19.由带权为 3，9，6，2，5 的 5 个叶子结点构成一棵哈夫曼树，则带权路径长度为_。20.设 F 是一个森林，B 是由 F 转换得到的二
10、叉树，F 中有 n 个非终端结点，则 B 中右指针域为空的结点有_个。21.二叉树的存储结构分为_ ，树的存储结构分为_。三、判断题1树中任意结点的子树不必是有序的。( )2树可以看成特殊的无向图。( )3可以使用双链表表示树型结构。( )4顺序存储方式只能用于存储线性结构。( )5完全二叉树的某结点若无左孩子，则必是叶结点。( )6在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。( )7由于二叉树中每个结点的度最大为 2，所以二叉树是一种特殊的树。( )8二叉树的前序遍历序列中，任意一个结点均处在其子树结点的前面。 ( )9二叉树的前序和后序遍历序列能惟一确定这棵二叉树。 (
11、 )10.中序线索二叉树中，右线索若不为空，则一定指向其父结点。( )四、算法和操作题1假定一棵二叉树广义表表示为 a(b(c)，d(e，D)，分别写出对它进行前序、中序、后序遍历的结果。前序：中序：后序：2已知一棵二叉树的中序和后序序列，求该二叉树的高度和双支、单支及叶子结点数。中根序列：c，b，d，e ，a，g，i,h,j，f后根序列：c，e ，d，b，i，j，h，g，fa高度： 双支： 单支： 叶子：3已知一棵树边的集合为，M，N，I，E，D ，B，J ，K， ，G，F ，L，H，C)，请画出这棵树，并回答下列问题：(1)哪个是根结点？(2)哪些是叶子结点？(3)哪个是结点 G 的双亲？
12、(4)哪些是结点 G 的祖先？(5)哪些是结点 G 的孩子？(6)哪些是结点 E 的子孙？(7)哪些是结点 E 的兄弟？哪些是结点 F 的兄弟？(8)结点 B 和 N 的层次号分别是什么？(9)树的深度是多少？(10)以结点 C 为根的子树的深度是多少？4将算术表达式(a+b)+c*(d+e)+f*(g+h)转化为二叉树。5. 一棵二叉树的结点数据采用顺序存储结构，存储于数组 BT 中，如题表 6-1 所示。画出该二叉树的链接表示形式。数组 BT 的存放形式是相对于满二叉树中编号为数组下标值的结点值。若该结点不存在，则取 0 值。6假设前序遍历某棵树的结点次序为 SACEFBDGHIJK；后序
13、遍历该树的结点次序为 CFEABHGIKJDS，请画出这棵树。7已知一棵树如题图 6-5 所示，将其转换为其孩子兄弟表示的二叉树。并画出该二叉树的后序线索二叉树。8试找出分别满足下列条件的所有二叉树：(1)前序遍历序列和中序遍历序列相同。(2)中序遍历序列和后序遍历序列相同。(3)前序遍历序列和后序遍历序列相同。9已知信息为“ABCD BCD CB DB ACB”，请按此信息构造哈夫曼树，求出每一字符的最优编码。10.己知中序线索二叉树采用二叉链表存储结构，链结点的构造为：其中若 ltag 为 0，则 lchild 指向结点的前驱，否则 lchild 指向左孩子结点；若 rtag 为 0，则
14、rchild 指向结点的后继，否则 rchild 指向右孩子结点。下面的算法返回 x 所指结点的直接后继结点的位置。若该算法有错，则请改正错误；若无错，请写“正确”二字。BiTree INSUCC (BiTree x) s=X-rchild;if（s-rtag）while （s-ltag ）s=s-rchild;return s；)五、算法设计题1编写对二叉树进行中序遍历的非递归算法，并对算法执行题图 6-6 所示的二叉树的情况进行跟踪（即给出各阶段栈的变化及输出的结点序列）。栈已经定义：InitStack(S)（初始化）、Empty(S) （判栈空）、 Push(S，p) （入栈）、Pop(
15、S，p)（出栈）等操作。2假设在表示一棵二叉树的二叉链表上增加两个域：双亲域用于指示其双亲结点，标志域 flag（可取 0.2）的值，用以区分在遍历过程中到达该结点时继续向右或向左或访问该结点。试以此存储结构编写不用栈进行后序遍历的递归形式的算法。3一棵具有 n 个结点的完全二叉树，以一维数组作为存储结构，试设计一个对该完全二叉树进行前序遍历的算法。4设中序线索树的结点由 5 个域组成。Info：给出结点的数据域。LT:标志域，为 0 或 1。LL：当 LT 为 1 时，给出该结点的左孩子的地址。当 LT 为 0 时，给出按中序遍历的前驱结点地址。RT:标志域，为 0 或 1。RL：当 RT
16、为 1 时，给出该结点的右孩子的地址。当 RT 为 O 时，给出按中序遍历的后继结点地址。请编写 程序，在具有上述结点结构的中序线索二叉树上，求某一结点 p 按后序遍历次序的后继结点的地址 q，设该中序线索二叉树的根结点地址为 r。另外，请注意必须满足：(l)额外空间的使用只能为 O(1)。(2)程序为非递归形式。5假设二叉树采用链接方法存储，编写一个函数按凹入表表示法打印出该二叉树。6给出中序线索树的结点结构，设计算法在不使用栈和递归的情况下前序遍历一棵中序线索树，并分析它的时间复杂度。7以二叉链表为存储结构，写出交换各结点左右子树的算法。8假设二叉树采用链接方法存储，编写一个函数按凹入表表
17、示法打印出该二叉树。第六章 树和二叉树第 6 章树和二叉树一、选择题（参考答案）1B 2B 3C 4A，C 5C6C 7A 8B 9A，B10. (1)C (2)A (3)C (4)A (5)C (6)A (7)C11B 12.A 13B 14A 15B16D 17A 18C 19D 20D二、填空题（参考答案）1树的总结点数-1。2前驱：1，后继，任意多个。3. kl, k2, k4, k5, k7,2,k5, k6, kl,3,4。4.3，4，6，1，1，2，A，F，G。5.(1) ki-l, (2) , (3) n-lk+n+1,(4)ink+l(n=0,l,2，),n+1.6前序遍历，
18、中序遍历。 7前序，中序，后序，前序，后序。8. 2i-1， 2/n, 2/n. 9.6 个。10. 160 11. 2n，n-l，n+l。12A13.树可采用二叉树的存储结构并可利用二叉树的已有算法解决树的有关问题。14.只有 1 个结点的树，空树。 15.I，F。16.前序遍历序列为：EACBDGF，森林包括 1 棵树。17. HIDJKEBLFGCA0 18. 2n-l。19. 560 20n+l。21.顺序存储和链式存储，双亲链表表示法，孩子链表表示法，孩子兄弟链表表示法三、判断题1. 2. 3. 4. 5. 6. 7. 8. 9. 10.四、算法和操作题1假设一棵二叉树广义表表示为
19、a(b(c)，d(e，D)，分别写出对它进行前序、中序、后序遍历的结果。【解答】前序：a，b，c，d，e，D中序：c，b，a，e，d，D后序：c，b，e，D，d，a2已知一棵二叉树的中序和后序序列，求该二叉树的高度和双支、单支及叶子结点数。【解答】中序序列：c，b，d，e，a，g，i，h，j，f后序序列：c，e，d，b，i，j，h，g，f，a由中序和后序（前序）遍历序列可惟一确定一棵二叉树，基本思想是后序（前序）定根，中序分左右。由后序序列可知该树的根结点为 a，由中序遍历序列可知该树的左子树为c，b，d，e，右子树为g，i，h，j，f）;再由后序序列可知该树的左子树的根结点为 b，右子树的根
20、结点为 f再由中序遍历序列可知 b 结点的左子树为c，右子树为d，e）;再由后序遍历序列可知右子树d，e的根结点为 d，再由中序遍历序列可知 d 的左子树为空，右子树为e。对以 f 为根结点的子树可做类似的分析。最后得到由中序和后序序列决定的二叉树为：a(b(c，d(，e)，f(g(，h(i，j)，由此可知该树：高度：5 双分支：3 单分支：3 叶结点：4。3已知一棵树边的集合为，请画出这棵树，并回答问题？【解答】根据边集画出的树如下所示：(1)根结点是：A。(2)叶子结点是：D，M，N，F，J，K，L。(3)结点 G 的双亲是：C。(4)结点 G 的祖先是：A，C。(5)结点 G 的孩子是：
21、J，K。(6)结点 E 的子孙是：I，M，N。(7)结点 E 的兄弟是：D;结点 F 的兄弟是：G，H。(8)结点 B 和 N 的层次号分别是：2，5。(9)树的深度是：5。(10)以结点 C 为根的子树的深度是：3。4将算术表达式(a+b)+c*(d+e)+f*(g+h)转化为二叉树。【解答】转化成如下二叉树：5-棵二叉树的结点数据采用顺序存储结构，存储于数组 BT 中，如题表 6-1 所示。画出该二叉树的链接表示形式。数组 BT 的存放形式是相对于满二叉树中编号为数组下标值的结点值。若该结点不存在，则取 0 值。题表 6-1【解答】二叉树的链式表示为：6若前序遍历某树的结点次序：SACEF
22、BDGHIJK;后序遍历的结点次序为：CFEABHGIKJDS，画出这棵树。【解答】画出树如下：7将原教材题图 6-5 转换为孩子兄弟所表示的二叉树及该二叉树的后序线索二叉树如下：8空树满足所有条件。非空树如下：(1)前序和中序遍历序列相同的二叉树是没有左子树的二叉树（右单支树）。(2)中序和后序遍历序列相同的二叉树是没有右子树的二叉树（左单支树）。(3)前序和后序遍历序列相同的二叉树是只有根的二叉树。9在信息“ABCD BCD CB DB ACB”中 A，B，C，D 四个字符出现的频率依次是：2，5，4，3。在哈夫曼树中每个字符的最优编码：可得编码为：A-110 B-O C-10 D-II1信息编码为：110010111 010111 100 1110 11010010.错误。修改如下：
