高效作业14 第14课 二叉树的基本操作与抽象数据类型-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参(浙教版2019)
高效作业14[第14课 二叉树的基本操作与抽象数据类型](见学生用书P223)
学科网(北京)股份有限公司
【A级 新教材落实与巩固】
1.若一棵二叉树的中序遍历序列为BIGDHAECF,后序遍历序列为IGHDBEFCA,则该二叉树的前序遍历序列为( D )
A.ABCDEFGHI B.ABDGHICEF
C.ABDHGICEF D.ABDGIHCEF
【解析】 “A”是根节点,那么“ECF”在右子树,选项A错误;B、C、D 三个选项中,只有“GHI”的位置是不一样的。左子树的根节是“B”,那么再根据中序的“IGDH”,后序的“IGHD”,“D”是这个子树的根节点。“H”在右子树,前序遍历一定在最后。选项D正确。
2. 已知二叉树中序遍历序列为BEDAFHCIG,前序遍历序列为ABDECFHGI,它的后序遍历序列为( D )
A.BDEFHCIGA B.IGHFEDCBA
C.EDBFHIGCA D.EDBHFIGCA
【解析】 根据二叉树的前序与中序遍历序列,可画出二叉树如下图,再写出后序遍历序列是EDBHFIGCA。选项D正确。
3. 某二叉树的后序遍历序列为F??CAD,中序遍历序列为FBDEAC,则其前序遍历序列为( B )
A. DBAFEC
B. DBFAEC
C. DEFABC
D.DEAFBC
【解析】 通过后序遍历序列可知此二叉树的根节点为D,再通过中序遍历序列可知,F、B为左子树的节点,A、C、E为右子树的节点;再结合后序遍历序列可知, 左子树中,F 为左或右节点,B为根节点; 右子树中,A为根节点,E为左节点,C为右节点。由此可知,前序遍历序列为DBFAEC。选项B正确。
4.现有一棵二叉树的前序遍历序列为CBADE、中序遍历序列为BACED,则该二叉树的后序遍历序列为( A )
A.ABEDC B.CBEDA
C.ABDEC D.CBDEA
【解析】 通过前序遍历序列为CBADE、中序遍历序列为BACED,可以确定二叉树的根为C,左子树为BA,右子树为ED。研究其左子树BA,前序遍历序列为BA、中序遍历序
学科网(北京)股份有限公司
列为BA;研究其右子树ED,前序遍历序列为DE、中序遍历序列为ED。确定二叉树的形态如图所示,故该二叉树的后序遍历序列为ABEDC,选项A正确。
5.已知一棵二叉树的后序遍历序列为IHDBEFCA,中序遍历序列是DIHBAECF,则该二叉树的前序遍历序列为( C )
A. ABDIHCFE B. ABDIHCEF
C. ABDHICEF D.ABDHICFE
【解析】 后序遍历是先遍历左、右节点再遍历根节点,中序遍历是先遍历左节点再遍历根节点最后遍历右节点,结合后序遍历序列与中序遍历序列,可画出二叉树如图所示:
所以前序遍历序列为ABDHICEF,选项C正确。
6.现有一棵二叉树的前序遍历序列为ABCDEF,中序遍历序列为BCADFE,则该二叉树的后序遍历序列为( A )
A.CBFEDA B.BCFEDA
C.CBDFEA D.BCEFDA
【解析】 根据前序遍历和中序遍历的规则画出二叉树,过程如下:前序遍历的第一个元素“A”为根节点,根据节点“A”在中序遍历的位置确定:“BC”是节点“A”的左子树,“DEF”为节点“A”的右子树。“BC”中,根据前序遍历确定节点“B”为根节点,继而根据中序遍历确定节点“C”是节点“B”的右子树。“DEF”中,根据前序遍历确定节点“D”为根节点,继而根据中序遍历确定“EF”是节点“D”的右子树。“DEF”中,根据前序遍历确定节点“E”为根节点,继而根据中序遍历确定节点“F”是节点“D”的右子树。根据画出的二叉树可以得到后续遍历结果为CBFEDA。选项A正确。
7.2023·诸暨中学检测某二叉树的结构如下, 下列说法正确的是( D )
学科网(北京)股份有限公司
A. 该二叉树是一棵完全二叉树
B. 该二叉树有3个叶子节点
C. 该二叉树的后序遍历结果是DBEFCA
D.该二叉树的建立可以使用数组也可以用链表数据结构
【解析】 选项A,完全二叉树指的是:从根节点开始,按自上而下、从左往右的顺序生成节点的二叉树, 而题中所给的二叉树不符合完全二叉树的生成规律, 选项错误。选项B,叶子节点指的是树中度为0的节点, 该二叉树中, 只有两个叶子节点D和F, 选项错误。选项C,后序遍历是指在遍历二叉树的过程中,按“ 左右根”的顺序对树中节点进行访问,故该二叉树的后序遍历序列为:DBFECA, 选项错误。选项D,二叉树的建立既可以使用数组也可以使用链表实现, 选项正确。
8.已知一棵二叉树的前序遍历序列为:ABDCE,后序遍历序列为:DBECA,则下列关于该二叉树的中序遍历序列说法中,正确的是( B )
A. 能唯一确定,中序遍历序列为:BDAEC
B. 不能唯一确定,中序遍历序列可能为:BDAEC
C. 能唯一确定,中序遍历序列为:DCBAE
D.不能唯一确定,中序遍历序列可能为:DCBAE
【解析】 二叉树遍历中只有前序和后续不能唯一确定一棵二叉树, 故排除选项A、C。选项B,根据前序和中序遍历可以画出二叉树如图,其后序遍历序列为DBECA,满足条件,选项正确。
9. 2023·柯桥中学检测已知一棵二叉树的前序遍历序列为FGDAETMH,中序遍历序列为DGEAFTHM,则该二叉树的后序遍历序列为( B )
A.DAEGHMTF B.DEAGHMTF
C.DEAGHMFT D.DAEGHMFT
【解析】 前序遍历的遍历次序为“根左右”,中序遍历的遍历次序为“左根右”,由此可得出二叉树如下图所示:
结合二叉树后序遍历的次序为“左右根”,故该二叉树后序遍历的结果为: DEAGHMTF。选项B正确。
10.对于如图所示的二叉树,下列说法正确的是( D )
学科网(北京)股份有限公司