高效作业14 第14课 二叉树的基本操作与抽象数据类型-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固PPT课件（浙教版2019）

高效作业14 [第14课　二叉树的基本操作与抽象数据类型] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 【A级　新教材落实与巩固】 1．若一棵二叉树的中序遍历序列为BIGDHAECF，后序遍历序列为IGHDBEFCA，则该二叉树的前序遍历序列为(　 　) A．ABCDEFGHI　　　　 B．ABDGHICEF C．ABDHGICEF D．ABDGIHCEF 【解析】 “A”是根节点，那么“ECF”在右子树，选项A错误；B、C、D 三个选项中，只有“GHI”的位置是不一样的。左子树的根节是“B”，那么再根据中序的“IGDH”，后序的“IGHD”，“D”是这个子树的根节点。“H”在右子树，前序遍历一定在最后。选项D正确。 22 D 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 2． 已知二叉树中序遍历序列为BEDAFHCIG，前序遍历序列为ABDECFHGI，它的后序遍历序列为(　 　) A．BDEFHCIGA B．IGHFEDCBA C．EDBFHIGCA D．EDBHFIGCA 【解析】 根据二叉树的前序与中序遍历序列，可画出二叉树如下图，再写出后序遍历序列是EDBHFIGCA。 选项D正确。 22 D 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 3． 某二叉树的后序遍历序列为F？？CAD，中序遍历序列为FBDEAC，则其前序遍历序列为(　 　) A． DBAFEC B． DBFAEC C． DEFABC D．DEAFBC 【解析】 通过后序遍历序列可知此二叉树的根节点为D，再通过中序遍历序列可知，F、B为左子树的节点，A、C、E为右子树的节点；再结合后序遍历序列可知， 左子树中，F 为左或右节点，B为根节点； 右子树中，A为根节点，E为左节点，C为右节点。由此可知，前序遍历序列为DBFAEC。选项B正确。 22 B 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 4．现有一棵二叉树的前序遍历序列为CBADE、中序遍历序列为BACED，则该二叉树的后序遍历序列为(　 　) A．ABEDC B．CBEDA C．ABDEC D．CBDEA 22 A 【解析】 通过前序遍历序列为CBADE、中序遍历序列为BACED，可以确定二叉树的根为C，左子树为BA，右子树为ED。研究其左子树BA，前序遍历序列为BA、中序遍历序列为BA；研究其右子树ED，前序遍历序列为DE、中序遍历序列为ED。确定二叉树的形态如图所示，故该二叉树的后序遍历序列为ABEDC，选项A正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 5．已知一棵二叉树的后序遍历序列为IHDBEFCA，中序遍历序列是DIHBAECF，则该二叉树的前序遍历序列为(　 　) A． ABDIHCFE B． ABDIHCEF C． ABDHICEF D．ABDHICFE 【解析】 后序遍历是先遍历左、右节点再遍历根节点，中序遍历是先遍历左节点再遍历根节点最后遍历右节点，结合后序遍历序列与中序遍历序列，可画出二叉树如图所示： 22 C 所以前序遍历序列为ABDHICEF，选项C正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 6．现有一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为BCADFE，则该二叉树的后序遍历序列为(　 　) A．CBFEDA B．BCFEDA C．CBDFEA D．BCEFDA 【解析】 根据前序遍历和中序遍历的规则画出二叉树，过程如下：前序遍历的第一个元素“A”为根节点，根据节点“A”在中序遍历的位置确定：“BC”是节点“A”的左子树，“DEF”为节点“A”的右子树。“BC”中，根据前序遍历确定节点“B”为根节点，继而根据中序遍历确定节点“C”是 22 A 节点“B”的右子树。“DEF”中，根据前序遍历确定节点“D”为根节点，继而根据中序遍历确定“EF”是节点“D”的右子树。“DEF”中，根据前序遍历确定节点“E”为根节点，继而根据中序遍历确定节点“F”是节点“D”的右子树。根据画出的二叉树可以得到后续遍历结果为CBFEDA。选项A正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 7．2023·诸暨中学检测某二叉树的结构如下， 下列说法正确的是(　 　) A． 该二叉树是一棵完全二叉树 B． 该二叉树有3个叶子节点 C． 该二叉树的后序遍历结果是DBEFCA D．该二叉树的建立可以使用数组也可以用链表数据结构 22 D 【解析】 选项A，完全二叉树指的是：从根节点开始，按自上而下、从左往右的顺序生成节点的二叉树， 而题中所给的二叉树不符合完全二叉树的生成规律， 选项错误。选项B，叶子节点指的是树中度为0的节点， 该二叉树中， 只有两个叶子节点D和F, 选项错误。选项C，后序遍历是指在遍历二叉树的过程中，按“ 左右根”的顺序对树中节点进行访问，故该二叉树的后序遍历序列为：DBFECA, 选项错误。选项D，二叉树的建立既可以使用数组也可以使用链表实现， 选项正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 8．已知一棵二叉树的前序遍历序列为：ABDCE，后序遍历序列为：DBECA，则下列关于该二叉树的中序遍历序列说法中，正确的是(　 　) A． 能唯一确定，中序遍历序列为：BDAEC B． 不能唯一确定，中序遍历序列可能为：BDAEC C． 能唯一确定，中序遍历序列为：DCBAE D．不能唯一确定，中序遍历序列可能为：DCBAE 22 B 【解析】 二叉树遍历中只有前序和后续不能唯一确定一棵二叉树， 故排除选项A、C。选项B，根据前序和中序遍历可以画出二叉树如图，其后序遍历序列为DBECA，满足条件，选项正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 9． 2023·柯桥中学检测已知一棵二叉树的前序遍历序列为FGDAETMH，中序遍历序列为DGEAFTHM，则该二叉树的后序遍历序列为(　 　) A．DAEGHMTF B．DEAGHMTF C．DEAGHMFT D．DAEGHMFT 22 B 【解析】 前序遍历的遍历次序为“根左右”，中序遍历的遍历次序为“左根右”，由此可得出二叉树如下图所示： 结合二叉树后序遍历的次序为“左右根”，故该二叉树后序遍历的结果为： DEAGHMTF。选项B正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 10．对于如图所示的二叉树，下列说法正确的是(　 　) A． 树的高度为4，是一棵完全二叉树 B． 度为2 的节点数比叶子节点数多1 C． 若采用数组存储法，需要6 个存储空间 D．该二叉树的后序遍历序列是fdebca 22 D 【解析】 选项A，树的高度是4，但不是完全二叉树。完全二叉树是除最后一层外节点都满节点，且最后一层节点都集中在左边位置上，而该二叉树倒数第二层也没有满节点(c没有子节点)，选项错误。选项B，度为2 的节点有两个，而叶子节点有3 个。实际上，任意二叉树的都满足叶子节点数比度为2 的节点数多一个，选项错误。选项C，若有数组存储二叉树时，c 节点虽然没有子节点，但是也要在数组中占据额外的两个空元素位置，因此总容量应该是8 个存储空间，选项错误。选项D，后序遍历序列为fdebca，选项正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 11．已知一棵二叉树的中序遍历序列为9－4＋2*3/1＋4 ，后序遍历序列为94－23*＋14＋/，下列说法正确的是(　 　) A．这棵树叶子结点比非叶子结点数多1 B．这是一棵满二叉树 C．其前序遍历序列为/＋－9 4*231＋4 D．这棵树有5层 22 A 【解析】 选项A，叶子结点5，非叶子结点4，选项正确；选项B，完全二叉树，没有满，选项错误；选项C，前序遍历结果为/＋94*23＋14，选项错误；选项D，这棵树有4层，选项错误。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 12．2023·瑞安中学检测用一维数组表示二叉树，如下表所示： 下列关于该二叉树的说法中，正确的是(　 　) A．该树中共有4 个叶子节点 B．该树是完全二叉树，其深度为4 C．该树的中序遍历序列为BFDGACE D．该二叉树的结构图为(如下图所示) 22 0 1 2 3 4 5 6 7 8 9 10 A B C   D   E     F G C 【解析】 二叉树形态如下图所示： 选项D错误；该二叉树不是完全二叉树，但其深度为4，选项B错误；该树中有3 个叶子节点，分别为F，G，E，选项A错误。选项C正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 13．有二叉树的前序遍历序列为ABCEFGD，中序遍历序列为AECFGBD，则下列关于该二叉树的说法中，正确的是(　 　) A． 该二叉树根节点的度为1 B． 该二叉树的高度为4 C． 该二叉树中节点G是节点C的左孩子 D．该二叉树中叶子节点的个数为4 22 A 【解析】 根据二叉树的前序遍历和中序遍历画出二叉树。该二叉树的根节点A的度为1，选项A正确；该二叉树的高度为5，选项B错误；该二叉树的节点G是节点F的右孩子，选项C错误；该二叉树的叶子节点是E、G、D，选项D错误。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 14．英国生物统计学家高尔顿为研究随机现象设计了一个装置，称为高尔顿钉板。球下落的左右走向可以用二叉树这种数据结构来表示，树的结构如图所示，节点分别由A 到H，此二叉树的后序遍历序列为(　 　) A．DEBACGHF B．DBEHCGFA C．DEBGHFCA D．ABDECFGH 【解析】 二叉树后序遍历的顺序是先左子树，再右子树，最后是根，选项C正确。 22 C 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 【B级　素养形成与评价】 15．某二叉树的前序遍历序列和后序遍历序列正好相反，则该二叉树一定是(　 　) A．空或只有一个节点 B．高度等于其节点数 C．任一节点无左孩子 D．任一节点无右孩子 【解析】 二叉树的前序遍历是：根→左→右，后序遍历是：左→右→根，当前序遍历和后序遍历恰好相反的时候，可以是没有左子树，也可以是没有右子树，因此二叉树的高度等于节点数。选项B正确。 22 B 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 16． 用二叉树构造某表达式树，其前序遍历结果为*/a＋bc*＋－defg，中序遍历结果为 a/b＋c*d－e＋f*g，则该表达式树的后序遍历结果为(　 　) A． abc＋/de－f＋g** B． ab/cd*＋e－fg＋* C． abcd*＋/e－＋fg* D．abcd*＋e－/fg＋* 22 A 【解析】 树的前序遍历是：根→左→右，中序遍历是：左→根→右，后序遍历是：左→右→根。根据一个运算符后面紧跟两个表达式(一个数也是一个表达式)的原则，根据题干中提供的前序遍历结果和中序遍历结果，可得以下过程，所以后序遍历结果为a b c ＋ / d e － f ＋ g**。前序遍历的第一个字符就是根节点，所以*是根节点，中序遍历中根节点*左边的是左子树的节点，右边是右子树的节点，故得到图1，同理，按照这个方法可以逐层获得每个节点的左右节点，顺序如图所示。选项A正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 17．有一棵二叉树如图所示： 下列关于该树的说法中，正确的是(　 　) A．该二叉树是一棵完全二叉树，树的高度为4 B．该二叉树的前序遍历结果为25，15，46，6 ，18，28，58，12，22，35，60 C．该二叉树的叶子节点有8 个 D．若用数组(第一个元素下标为0)来表示该树，则节点“46”在数组中下标为2 22 D 【解析】 完全二叉树指的是：从根节点开始，按自上而下、从左往右的顺序生成节点的二叉树。图中，最后一层叶子节点靠右排列， 与定义不符， 选项A错误；该二叉树的前序遍历结果为25 15 6 12 18 22 46 28 35 58 60, 选项B错误；该二叉树叶子节点个数为4个，选项C错误；若用数组顺序存储该二叉树，节点“46”在第3个位置，下标为2，选项D正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 18．2023·永嘉中学检测数学表达式3/(5*2)可用二叉树表示，如图所示。下列关于该二叉树的说法中，正确的是(　 　) A．该二叉树是完全二叉树 B．该二叉树的叶子节点数为2 C．该二叉树的前序遍历结果为352*/ D．该二叉树用数组表示为 22 D 【解析】 选项A，完全二叉树是指一棵深度为k 的有n 个结点的二叉树，对树中的节点按从上至下、从左到右的顺序进行编号，编号为i(1≤i≤n)的结点与满二叉树中编号为i 的结点在二叉树中的位置相同。3 所在节点缺少叶子节点，故该二叉树不是完全二叉树，选项错误。选项B，3、5、2 所在节点为叶子节点，数量为3，选项错误。选项C，前序遍历结果为/3*52，后序遍历结果为352*/，选项错误。选项D，将图中二叉树补全为完全二叉树，依次把完全二叉树中原二叉树的节点用一维数组的各元素表示，可得 ，选项正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 19．如图所示的二叉树，若要得到一个递增序列，可以用下列哪种遍历方式(　 　) A．前序遍历 B．中序遍历 C．后序遍历 D．逐层遍历 【解析】 观察图示二叉树可以发现， 该二叉树的每一棵子树均符合“左孩子<根节点<右孩子”这一存放特点。因此，要得到递增序列，按照“左→根→右”的访问顺序即可得到，因此采用中序遍历的遍历方式即可。选项B正确。 22 B 34 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 20． 有一种二叉树，它的任何一个当前节点，左子树的数据都比该节点的数据小，右子树的数据都比该节点的数据大。下列关于该二叉树遍历的说法中，正确的是(　 　) A．采用前序遍历，遍历到的节点元素升序排列 B．采用中序遍历，遍历到的节点元素升序排列 C．采用中序遍历，遍历到的节点元素降序排列 D．采用后序遍历，遍历到的节点元素降序排列 22 B 【解析】 根据题意，如下二叉树符合题目要求，根为5，故前序遍历和后序遍历都不可能实现升序或者降序。若采用中序遍历，因为中序遍历的结果是：左→根→右，以左子树为例，左跟右的结果是234，升序，选项B正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 21．已知有二叉树T，其前序遍历序列是ABDCEGF(字母为结点的编号，以下同)，后序遍历序列是DBGEFCA，则下列选项中，不可能是该二叉树中序遍历序列的是(　 　) A．DBAGECF B．BDAGECF C．DBAGEFC D．BDAEGCF 22 C 【解析】 二叉树遍历有三种：前序遍历(根左右)、中序遍历(左根右)、后序遍历(左右根)根据前序遍历序列是ABDCEGF 和后序遍历序列是DBGEFCA，可知A 为二叉树的根，前序遍历的第二个节点与后序遍历的倒数第二个节点不相等，那么前序遍历的第二节点B 是根的左子树，后序遍历的倒数第二节点C 是根的右子树，就可以得到：A(根)BD(左子树)CEGF(右子树)，DB(左子树)GEFC(右子树)A(根)。同理根据前序遍历CEGF和后序遍历GEFC，得出E 是C 的左子树，F 是C 的右子树。故选项C不可能。构建的二叉树可能如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 22． 2023·嘉兴一中检测一棵二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根节点的左子树节点的个数可能是(　 　) A．2　　 B．3　　 C．4　　 D．5 A 【解析】 可知，二叉树的根为A。 ①若左子树为BC，右子树为DEFG，则有可能； ②若左子树为BCD，右子树为EFG，则其后序遍历序列不可能为CBFEGDA，排除； ③若左子树为BCDE，右子树为FG, 则其后序遍历序列不可能为CBFEGDA，排除； ④若左子树为BCDEF，右子树为G, 则其后序遍历序列不可能为CBFEGDA，排除； 故只有第一种可能，选项A正确。 23．小明用Python的二维列表来模拟二叉树T，形态如图所示，其中['A'，1，2]表示树节点数据为“A”、该节点左子树的地址在列表的索引1、右子树的地址在列表的索引2，['K'，－1，－1]则表示为叶子节点，即该节点既没有左子树也没有右子树。现在小明要使用递归算法对二叉树T做后序遍历，但在编写代码的时候不小心出错了，并没有真正完成后序遍历，其错误的代码如下： T＝[['A'，1，2]，['B'，3，4]，['C'，5，6]，['D'，－1，7]，['E'，－1，8]，['F'，9，10]，['G'，－1，－1]，['H'，－1，－1]，['I'，－1，－1]，['J'，－1，－1]，['K'，－1，－1]] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 rsult＝[] def Lrd(node)： if T[node][1]！＝－1： Lrd(T[node][1]) elif T[node][2]！＝－1： Lrd(T[node][2]) rsult.append(T[node][0]) Lrd(0) 执行该程序后，rsult列表的值为(　 　) A．['A'，'B'，'D'] B．['H'，'D'，'B'，'A'] C．['A'，'B'，'D'，'H'] D．['D'，'B'，'A'] B 【解析】 根据程序，if语句二选一，有左子节点则在左子节点进入递归，没有左子节点则执行elif在右子节点进入递归，若左右子节点都没有的，即叶子节点，则不执行if语句中任何一个递归。执行append，加入列表，所以根据上述，先左后右再中间，则到H 的时候，H 是叶子节点，直接执行append，H 先进入列表，H 节点程序完成后，从D 的递归中返回出来，执行下一句append，D 也加入列表……以此类推，选项B正确。 24．2023·平湖中学检测哈夫曼编码是一种可变长度编码方式，其编码总体思路为对于使用频率高的字母分配较短的编码，对于使用使用频率较低的字符分配较长的编码，从而提高压缩效率。现用以下实例说明其编码思想：现有一串字符串只包含A、B、C、D、E 共5 种字母，先统计出5 个字母在字符串中的使用频率，现假定频率如表格所示。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 字符 A B C D E 频率 35% 17% 26% 13% 9% 然后，开始以频率作为权值构造哈夫曼树，方法如下： ①将每个字符排成一排，并标注权值，每个字符都是一个叶子节点。 ②找出权值最小的两个节点，将其中权值较小的节点作为左分支，较大的作为右分支，把它们合并成一个父节点，就产生了一棵二叉树。父节点的权值是合成它的两个节点的权值之和，并为其左分支节点分配编码“0”，右分支节点分配编码“1”。该父节点可以与其余未被合成过的节点继续合并。 ③重复步骤②，直至所有节点合并完成一棵二叉树，如图1所示。 ④一个字母的编码就是从根节点开始，沿着各分支到达该字母所经过路径上各编码的顺序排列，如图2所示。 小明在学习了数据结构相关知识后编写Python 程序模拟哈夫曼编码过程，程序运行结果如图3所示。 请回答以下问题。 (1)若某段仅包含a、b、c、d、e 的字符串中，各字母的出现频率依次为23，20，36，9，12，则用哈夫曼编码字母d 的代码为_______。 (2)实现上述功能的Python 程序如下，请在横线处填入合适的代码。 010 zfpl＝{”A”：0，”B”：0，”C”：0，”D”：0，”E”：0} #存储字符频率 zfbm＝{”A”：””，”B”：””，”C”：””，”D”：””，”E”：””} #存储字符编码 def getminnode(st，top)： min＝top while st[min][2]！＝－1： min＝min－1 for i in range(0，min＋1)： if st[i][2]＝＝－1 and st[i][1]<st[min][1]： 　　　min＝i return min s＝input(”输入字符串：　”) st＝[] top＝－1 for i in s： zfpl[i]＋＝1 for i in zfpl： zfpl[i]＝round(①__________________ ) zfpl[i]/len(s)*100 top＋＝1 st.append([i，zfpl[i]，－1]) print(”各字符频率：　”，zfpl) while len(st[top][0])<len(zfpl)： node1＝getminnode(st，top) st[node1][2]＝”0” node2＝getminnode(st，top) st[node2][2]＝”1” top＋＝1 st.append (②_________________________________________________________) print(”各个节点：　”，st) top＝top－1 while top>＝0： for i in③_____________： zfbm[i]＝zfbm[i]＋st[top][2] top－＝1 print(”各字符编码：　”，zfbm) [st[node1][0]＋st[node2][0]，st[node1][1]＋st[node2][1]，－1] st[top][0] 【解析】 主要考查列表的添加、遍历，字典键值统计，及哈夫曼树构造过程的理解。程序分析时，应首先依据给定的案例，进行一次推导，构造哈夫曼树，并确定二维列表中每个元素存储值的含义，然后再进行程序分析。 (1)若某段仅包含a、b、c、d、e 的字符串中各字母的出现频率依次为23，20，36，9，12，字母的编码就是从根节点开始，沿着各分支到达该字母所经过路径上各编码的顺序排列，如图所示： 可确定d 的编码为010。 (2)①统计字母频率，字典zfpl 原来存储的是每个字母出现的次数，频率等于字母出现的次数除以s 中字符个数，结合图3 中字典zfpl 的结果，应对数据进行100 取整数部分的处理，确定答案为zfpl[i]/len(s)*100。②将 新产生的节点添加到列表st 中，st[][0]存储的是字母，st[][1]存储的是频率，st[][2]存储的是节点分配编码，新产生分配编码－1，因为该父节点可以与其余未被合成过的节点继续合并。确定答案为[st[node1][0]＋st[node2][0]，st[node1][1]＋st[node2][1]，－1]。③外循环遍历st 中存储的，除top 对应节点外的所有节点，内循环遍历st[][0]中存储的字母，并将字母对应的存储在st[top][2]中的编码连接，确定答案为st[top][0]。 感谢聆听，再见！ $$