树结构习题及答案.doc

第5章 树【例5-1】写出如图5-1所示得树得叶子结点、非终端结点、每个结点得度及树深度。ABCDEFGHIJ图5-1解:(1)叶子结点有:B、D、F、G、H、I、J。(2)非终端结点有:A、C、E。(3)每个结点得度分别就是:A得度为4,C得度为2,E得度为3,其余结点得度为0。(4)树得深度为3。【例5-2】一棵度为2得树与一棵二叉树有什么区别？解:度为2得树有两个分支,但分支没有左右之分;一棵二叉树也有两个分支,但有左右之分,左右子树得次序不能交换。【例5-3】树与二叉树有什么区别？解:区别有两点:(1)二叉树得一个结点至多有两个子树,树则不然;(2)二叉树得一个结点得子树有左右之分,而树得子树没有次序。【例5-4】分别画出具有3个结点得树与三个结点得二叉树得所有不同形态。解:如图5-2(a)所示,具有3个结点得树有两种不同形态。图5-2(a)如图5-2(b)所示,具有3个结点得二叉树有以下五种不同形态。图5-2(b)【例5-5】如图5-3所示得二叉树,试分别写出它得顺序表示与链接表示(二叉链表)。解:(1)顺序表示。1234567891011abcdefg(2)该二叉树得二叉链表表示如图5-4所示。abcdefg图5-4【例5-6】试找出满足下列条件得所有二叉树:(1)先序序列与中序序列相同;(2)中序序列与后序序列相同;(3)先序序列与后序序列相同。解:(1)先序序列与中序序列相同得二叉树为:空树或者任一结点均无左孩子得非空二叉树;(2)中序序列与后序序列相同得二叉树为:空树或者任一结点均无右孩子得非空二叉树;(3)先序序列与后序序列相同得二叉树为:空树或仅有一个结点得二叉树。bacdef图5-5【例5-7】如图5-5所示得二叉树,要求:(1)写出按先序、中序、后序遍历得到得结点序列。(2)画出该二叉树得后序线索二叉树。解:(1)先序遍历序列:ABDEFC中序遍历序列:DEFBAC后序遍历序列:FEDBCA(2)其后序线索二叉树如图5-6所示。NULLcabdef图5-6A图5-7BCDEFGHIKLMJ【例5-8】将图5-7所示得树转换为二叉树。解:第一步,加线。第二步,抹线。第三步,旋转。过程如图5-8所示。A图5-8(a) 第一步加线BCDEFGHIKLMJA图5-8(b) 第二步抹线BCDEFGHIKLMJAB图5-8(c) 第三步旋转CFDKGELHMIJABCDEFHIJ图5-9【例5-9】将如图5-9所示得二叉树转换为树。解: 第一步,加线。第二步,抹线。第三步,调整。过程如图5-10所示。ABDHCFEJIBACDEFHIJ第一步第二步第三步BACDEFHIJ图5-10【例5-10】将如图5-11所示得森林转换成二叉树。图5-11CDEFGABHILJK解: 步骤略,结果如图5-12所示。CDEFGABHILJK图5-12【例5-11】假定用于通信得电文由8个字符A、B、C、D、E、F、G、H组成,各字母在电文中出现得概率为5、25、4、7、9、12、30、8,试为这8个字母设计哈夫曼编码。解: 根据题意,设这8个字母对应得权值分别为(5,25,4,7,9,12,30,8),并且n=8。第一步:25547912308(1)设计哈夫曼树得步骤如图5-13所示。第四步:2579123081554918第五步:257912308155491827第六步:25309549187128152743第二步:257912305498第三步:25791230549815第七步:2530954918712815274357第八步:2595491843307128152757100图5-13(2)设计哈夫曼编码利用第八步得到得哈夫曼树,规定左分支用0表示,右分支用1表示,字母A、B、C、D、E、F、G、H得哈夫曼编码如下表示:A:0011B:01 C:0010D:1010E:000F:100G:11 H:1011习题5一、单项选择题1、 在一棵度为3得树中,度为3得结点数为2个,度为2得结点数为1个,度为1得结点数为2个,则度为0得结点数为( 1、 C)个。A、 4B、 5C、 6D、 72、 假设在一棵二叉树中,双分支结点数为15,单分支结点数为30个,则叶子结点数为(2、 B )个。A、 15B、 16C、 17D、 473、 假定一棵三叉树得结点数为50,则它得最小高度为(3、 C )。A、 3 B、 4C、 5D、 64、 在一棵二叉树上第4层得结点数最多为( 4、 D)。A、 2B、 4 C、 6D、 85、 用顺序存储得方法将完全二叉树中得所有结点逐层存放在数组中R1、n,结点Ri若有左孩子,其左孩子得编号为结点(5、 B)。A、 R2i+1B、 R2iC、 Ri/2D、 R2i-16、 由权值分别为3,8,6,2,5得叶子结点生成一棵哈夫曼树,它得带权路径长度为(6、 D )。A、 24B、 48C、 72D、 537、 线索二叉树就是一种( 7、 C)结构。A、 逻辑 B、 逻辑与存储C、 物理 D、 线性8、 线索二叉树中,结点p没有左子树得充要条件就是( 8、 B)。A、 p-lc=NULL B、 p-ltag=1 C、 p-ltag=1 且p-lc=NULL D、 以上都不对9、 设n , m 为一棵二叉树上得两个结点,在中序遍历序列中n在m前得条件就是(9、 B)。 A、 n在m右方 B、 n在m 左方 C、 n就是m得祖先 D、 n就是m得子孙10、 如果F就是由有序树T转换而来得二叉树,那么T中结点得前序就就是F中结点得(10、 B )。A、 中序B、 前序C、 后序D、 层次序11、 欲实现任意二叉树得后序遍历得非递归算法而不必使用栈,最佳方案就是二叉树采用( 11、 A)存储结构。A、 三叉链表B、 广义表C、 二叉链表 D、 顺序12、 下面叙述正确得就是( 12、 D)。A、 二叉树就是特殊得树B、 二叉树等价于度为2得树C、 完全二叉树必为满二叉树D、 二叉树得左右子树有次序之分13、 任何一棵二叉树得叶子结点在先序、中序与后序遍历序列中得相对次序(13、 A )。A、 不发生改变 B、 发生改变C、 不能确定 D、 以上都不对14、 已知一棵完全二叉树得结点总数为9个,则最后一层得结点数为(14、 B )。A、 1 B、 2C、 3D、 415、 根据先序序列ABDC与中序序列DBAC确定对应得二叉树,该二叉树( 15、 A )。A、 就是完全二叉树 B、 不就是完全二叉树C、 就是满二叉树D、 不就是满二叉树二、判断题1、 二叉树中每个结点得度不能超过2,所以二叉树就是一种特殊得树。(1、)2、 二叉树得前序遍历中,任意结点均处在其子女结点之前。( 2、 )3、 线索二叉树就是一种逻辑结构。(3、)4、 哈夫曼树得总结点个数(多于1时)不能为偶数。(4、)5、 由二叉树得先序序列与后序序列可以唯一确定一颗二叉树。(5、)6、 树得后序遍历与其对应得二叉树得后序遍历序列相同。(6、)7、 根据任意一种遍历序列即可唯一确定对应得二叉树。(7、)8、 满二叉树也就是完全二叉树。(8、)9、 哈夫曼树一定就是完全二叉树。(9、)10、 树得子树就是无序得。(10、)三、填空题1、 假定一棵树得广义表表示为A(B(E),C(F(H,I,J),G),D),则该树得度为_,树得深度为_,终端结点得个数为_,单分支结点得个数为_,双分支结点得个数为_,三分支结点得个数为_,C结点得双亲结点为_,其孩子结点为_与_结点。1、 3,4,6,1,1,2,A,F,G2、 设F就是一个森林,B就是由F转换得到得二叉树,F中有n个非终端结点,则B中右指针域为空得结点有_个。2、 n+13、 对于一个有n个结点得二叉树,当它为一棵_二叉树时具有最小高度,即为_,当它为一棵单支树具有_高度,即为_。3、 完全,最大,n4、 由带权为3,9,6,2,5得5个叶子结点构成一棵哈夫曼树,则带权路径长度为_。4、 555、 在一棵二叉排序树上按_遍历得到得结点序列就是一个有序序列。5、 中序6、 对于一棵具有n个结点得二叉树,当进行链接存储时,其二叉链表中得指针域得总数为_个,其中_个用于链接孩子结点,_个空闲着。6、 2n,n-1,n+17、 在一棵二叉树中,度为0得结点个数为n0,度为2得结点个数为n2,则n0=_。7、 n2+18、 一棵深度为k得满二叉树得结点总数为_,一棵深度为k得完全二叉树得结点总数得最小值为_,最大值为_。8、 2k-1,2k-1,2k-19、 由三个结点构成得二叉树,共有_种不同得形态。9、 510、 设高度为h得二叉树中只有度为0与度为2得结点,则此类二叉树中所包含得结点数至少为_。10、 2h-111、 一棵含有n个结点得k叉树,_形态达到最大深度,_形态达到最小深度。11、 单支树,完全二叉树12、 对于一棵具有n个结点得二叉树,若一个结点得编号为i(1in),则它得左孩子结点得编号为_,右孩子结点得编号为_,双亲结点得编号为_。12、 2i,2i+1,i/2(或i/2)13、 对于一棵具有n个结点得二叉树,采用二叉链表存储时,链表中指针域得总数为_个,其中_个用于链接孩子结点,_个空闲着。13、 2n,n-1,n+114、 哈夫曼树就是指_得二叉树。14、 带权路径长度最小15、 空树就是指_,最小得树就是指_。15、 结点数为0,只有一个根结点得树16、 二叉树得链式存储结构有_与_两种。16、 二叉链表,三叉链表17、 三叉链表比二叉链表多一个指向_得指针域。17、 双亲结点18、 线索就是指_。18、 指向结点前驱与后继信息得指针19、 线索链表中得rtag域值为_时,表示该结点无右孩子,此时_域为指向该结点后继线索得指针。19、 1,RChild20、 本节中我们学习得树得存储结构有_、_与_。20、 孩子表示法,双亲表示法,长子兄弟表示法四、应用题1、 已知一棵树边得集合为,请画出这棵树,并回答下列问题:(1)哪个就是根结点？(2)哪些就是叶子结点？(3)哪个就是结点g得双亲？(4)哪些就是结点g得祖先？(5)哪些就是结点g得孩子？(6)哪些就是结点e得孩子？(7)哪些就是结点e得兄弟？哪些就是结点f得兄弟？(8)结点b与n得层次号分别就是什么？(9)树得深度就是多少？(10)以结点c为根得子树深度就是多少？1、 解答:abcdegfhimnjki图5-15根据给定得边确定得树如图5-15所示。其中根结点为a;叶子结点有:d、m、n、j、k、f、l;c就是结点g得双亲;a、c就是结点g得祖先;j、k就是结点g得孩子;m、n就是结点e得子孙;e就是结点d得兄弟;g、h就是结点f得兄弟;结点b与n得层次号分别就是2与5;树得深度为5。4、 已知用一维数组存放得一棵完全二叉树:ABCDEFGHIJKL,写出该二叉树得先序、中序与后序遍历序列。4、 解答:先序序列:ABDHIEJKCFLG中序序列:HDIBJEKALFCG后序序列:HIDJKEBLFGCA6、 找出所有满足下列条件得二叉树:(1)它们在先序遍历与中序遍历时,得到得遍历序列相同;(2)它们在后序遍历与中序遍历时,得到得遍历序列相同;(3)它们在先序遍历与后序遍历时,得到得遍历序列相同;6、 解答:(1)先序序列与中序序列相同得二叉树为:空树或者任一结点均无左孩子得非空二叉树;(2)中序序列与后序序列相同得二叉树为:空树或者任一结点均无右孩子得非空二叉树;(3)先序序列与后序序列相同得二叉树为:空树或仅有一个结点得二叉树。7、 假设一棵二叉树得先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请写出该二叉树得后序遍历序列。7、 解答:后序序列:ACDBGJKIHFE8、 假设一棵二叉树得后序序列为DCEGBFHKJIA,中序序列为DCBGEAHFIJK,请写出该二叉树得后序遍历序列。8、 解答:先序序列:ABCDGEIHFJK9、 给出如图5-14所示得森林得先根、后根遍历结点序列,然后画出该森林对应得二叉树。9、 解答:先根遍历:ABCDEFGHIJKLMNO后根遍历:BDEFCAHJIGKNOML森林转换成二叉树如图5-16所示。10.给定一组权值(5,9,11,2,7,16),试设计相应得哈夫曼树。10、 解答:构造而成得哈夫曼树如图5-17所示。ABDEFCGHJIKNOML图5-14