二叉树的基本操作一轮复习课件-2025-2026学年浙江省高三信息技术选修一

二叉树的基本操作 1 知识过关 2 1. 二叉树的建立 (1)数组实现完全二叉树。从它的根节点开始,按从上而下、自左往右的顺序编号,根节点的编号为0,最后一个节点的编号为n－1。然后依次把二叉树的节点用一组连续的数组元素来表示,节点编号与数组的下标一一对应。如左下图所示的完全二叉树所对应的一维数组表示如右下图所示。 完全二叉树　　 编号 0 1 2 3 4 5 6 7 结点 A B C D E       数组表示示意图 3 (2)数组实现非完全二叉树。对于非完全二叉树,先将它补全为一棵完全二叉树,补上的节点及分支用虚线表示,将如左下图所示的一棵非完全二叉树补全为完全二叉树。然后将补全后的完全二叉树,从它的根节点开始,按从上而下、自左往右的顺序编号,根节点的编号为0,最后一个节点的编号为n－1。如右下图所示,依次把完全二叉树中原二叉树的节点用一维数组的各个元素来表示,节点编号与数组的下标一一对应。 原二叉树　　 补全后的二叉树　　 0 1 2 3 4 5 6 7 A   B       C   数组实现示意图 4 (3)链表实现二叉树。用任意的一组存储单元来存储二叉树的节点,用指向节点的指针来表示节点之间的关系。由于二叉树的节点可能有两个孩子,即左孩子和右孩子,因此二叉树的节点至少需要3个域:一个数据域和两个指针域。两个指针域分别指向节点的左孩子和右孩子,这两个指针分别称为左指针和右指针,这样得到的链表也称为二叉链表。如图所示为二叉树及其对应的二叉链表实现示意图。 5 2. 二叉树的遍历(前序、中序和后序) 二叉树遍历是指按照一定的规则和次序访问二叉树中的所有节点,使得每个节点都被访问一次且仅被访问一次。二叉树的遍历方式有很多,主要有前序遍历、中序遍历和后序遍历等。 (1)前序遍历(先根遍历)。 若二叉树为空,则空操作返回;否则,先访问根节点,再访问左子树,最后访问右子树。 (2)中序遍历(中根遍历)。 若二叉树为空,则空操作返回;否则,先访问左子树,再访问根节点,最后访问右子树。 6 (3)后序遍历(后根遍历)。 若二叉树为空,则空操作返回;否则,先访问左子树,再访问右子树,最后访问根节点。 二叉树 前序遍历(先根遍历):ABDECF 中序遍历(中根遍历):DBEAFC 后序遍历(后根遍历):DEBFCA 方法:找出根节点、划分子树,子树递归遍历。 7 典例精选 8 【例1】 (2024·浙江1月选考)某完全二叉树包含5个节点,其根节点在后序遍历序列、中序遍历序列中的位置序号分别记为x,y,则x－y的值是(　　) A. 0 B. 1 C. 2 D. 3 【解析】 本题考查完全二叉树及二叉树的遍历知识。二叉树的后序遍历:左子树—右子树—根节点,根节点一定是在最后的位置。中序遍历:左子树—根节点—右子树,5个节点的完全二叉树,左子树有3个节点,右子树只有1个节点,根节点在倒数第二的位置,那就有x－y=1,B正确。 B 【例2】 (2023·浙江6月选考)某二叉树的树形结构如下图所示,其前序遍历的结果为 BDEFCA,则中序遍历结果是(　　) A. EDCFBA B. ECFDAB C. BFDEAC D. EDFCBA A 【解析】 本题考查二叉树的遍历知识。前序遍历规则为“根左右”,已知前序遍历结果为BDEFCA,结合题图可知: ①二叉树第一次划分状态应为 ,如图1所示。 ② 根据前序遍历规则结合结构图,对左子树进行划分 , 如图2所示。 ③ 重复上述划分过程,对FC进行划分 ,最后,根据完整的二叉树结构图, 如图3所示,可知中序遍历为EDCFBA。 A正确。 【例3】 (2023·浙江1月选考)下列二叉树中,中序遍历的结果为BAEDFC的是(　　) C A. B. C. D. 【解析】 本题考查二叉树遍历的基本操作。中序遍历的特点:左子树—根—右子树,每个子树都遵循以上规定。4个二叉树的中序遍历结果如下:A:EDFBAC;B:BEDFAC; C:BAEDFC;D:BACEDF。C正确。 自我检测 15 1. 某完全二叉树共有300个节点,该二叉树的高度是(　　) A. 8 B. 9 C. 10 D. 11 【解析】 本题考查二叉树的基础知识。根据二叉树知识可知,若满二叉树的深度为3,则该二叉树的节点数为20+21+22=7。现在已知完全二叉树共有300个节点,由于256+44=300,且21+22+……27=256,因此该二叉树的前面8层是满二叉树,第9层的左边有连续的44个节点,B正确。 B 16 2. 某二叉树如右图所示。下列关于该二叉树的说法,错. 误. 的是(　　) A. 该二叉树的深度为3 B. 该二叉树的度均为2 C. 该二叉树的根节点为A D. 该二叉树的节点D和E是兄弟节点 【解析】 本题考查二叉树的知识。叶子节点D、E、C的度均为0,B符合题意。 B 17 3. 某二叉树的前序遍历的结果为ABC,若该二叉树不是满二叉树,则其后序遍历的结果是 (　　) A. ABC B. BCA C. CBA D. CAB 【解析】 本题考查二叉树的遍历。若二叉树不是满二叉树,则其可能有如下图所示的形式: 可以看出,其后序遍历的结果均为CBA,C正确。 C 18 4. 有一棵完全二叉树,已知其中序遍历结果是CADGBEIHJ,则其前序遍历结果应该为 (　　) A.ABCDEFGHI B.EGACDBHIJ C.EACGBDIHJ D.EACDBHIJ 【解析】 该完全二叉树有9个节点,因此共有4层,其中前3层是满二叉树(7个节点),第4层有2个节点,画出二叉树的形态和中序遍历路径,可得前序遍历序列。 B 19 5. 某二叉树中序遍历为ABCDEF,则下列不可能是此二叉树的为(　　) A.　　　　 B.　　 　C.　　　　 D. 【解析】 C选项中序遍历为ACBDEF。 C 20 必备知识练 21 1. 某二叉树的中序遍历序列为ABCDEFG,后序遍历序列为ACBFEGD。下列说法中,正确的是(　　) A. 前序遍历序列为DBACGFE B. 节点G为节点E的父节点 C. 该二叉树有两个叶子节点 D. 节点A与节点F为同一层 【解析】 本题考查二叉树的应用。根据中序遍历及后序遍历可得树的结构如图所示。分析可得,B正确。 B 22 2. 某二叉树的树形结构如图所示,其中序遍历的结果为EDBCFA,则后序遍历的结果为 (　　) A. EDFACB B. BEDCAF C. DEFACB D. CAFBED C 23 【解析】 本题考查二叉树的遍历。中序遍历规则为“左—根—右”,已知中序遍历结果为EDBCFA,可知完整二叉树如图所示。可得出后序遍历结果为DEFACB,C正确。 24 3. 如图所示的二叉树的中序遍历的结果是(　　) A. ABDEGCFH B. DBEGACHF C. DGEBHFCA D. ABCDEFGH 【解析】 中序遍历先访问左子树,再访问根节点,最后访问右子树。故该二叉树的中序遍历结果是DBEGACHF,B正确。 B 25 4. 如图所示的二叉树的后序遍历的结果是(　　) A. ABDEGCFH B. DBEGACHF C. DGEBHFCA D. ABCDEFGH 【解析】 后序遍历是先访问左子树,再访问右子树,最后访问根节点。因此该二叉树的后序遍历结果是DGEBHFCA,C正确。 C 26 5. 已知7个节点的二叉树的前序遍历是ABDEFCG(字母为节点编号),中序遍历是 DBFEAGC,则该二叉树的后序遍历是(　　) A. DFEBGCA B. DFEBACG C. FBCGEDA D. DFECAGB 【解析】 已知7个节点的二叉树的前序遍历是ABDEFCG(字母为节点的编号),判断出节点A是树根,B、D错误;又根据中序遍历是DBFEAGC,可判断出GC是树根的右子树,A正确,C错误。 A 27 6. 某二叉树的前序遍历序列和中序遍历序列相同,下列选项中,符合该二叉树结构的是 (　　) C A. B. C. D. 【解析】 本题考查二叉树的遍历。前序遍历为根—左—右,中序遍历为左—根—右,若没有左子树,则两种遍历结果相同,C正确。 28 7. 如表所示为用数组表示二叉树。则该二叉树的中序遍历序列为(　　) 0 1 2 3 4 5 6 7 A B C 　 D 　 　 　 8 9 10 11 12 13 14   　 E F 　 　 　 　   A. BEDFAC B. ABDEFC C. DBEAFC D. BDAECF 【解析】 本题考查二叉树的创建与遍历。根据题意,创建如图所示的二叉树,然后进行中序遍历,分析可得A正确。 A 29 8. 某二叉树的树形结构如图所示,前序遍历为ABCDEF,则该二叉树的后序遍历的结果是 (　　) A. CBFEDA B. BCADEF C. ABDCEF D. FEDCBA A 30 【解析】 本题考查二叉树的遍历。根据前序遍历根—左—右的规则和题图的二叉树结构,不难得出该二叉树如图所示。由此可知,后序遍历结果是CBFEDA,A正确。 31 9. 已知一棵二叉树的前序遍历序列为ABCDEFG,则该二叉树的中序遍历序列可能为 (　　) A. CABDEFG B. ABCDEFG C. DACEFBG D. ADBCFEG 【解析】 本题考查二叉树的相关知识。已知前序遍历和中序遍历,可以确定对应的二叉树。若某个中序遍历序列有错,则无法还原二叉树。利用这个特点,我们可以逐个选项尝试画出二叉树。当二叉树所有分支节点都没有左子树时,该二叉树的中序遍历序列是ABCDEFG,B正确。 B 32 关键能力练 33 10. 某二叉树的后序遍历序列为ABCDE,其中节点A和节点B分别是节点C的左右孩子,则该树的前序遍历可能是(　　) A. CABED B. DCABE C. EACBD D. EDCAB 【解析】 本题考查二叉树的遍历。根据后序遍历序列为ABCDE可知,节点E是根节点,前序遍历根节点在最前面,A、B错误。另外,由于节点A和节点B分别是节点C的左右孩子,因此前序遍历(根—左—右)A和B节点不可能分居在节点C的两边,C错误。 D 34 11. 某二叉树的前序遍历序列和后序遍历序列正好相反,则该二叉树一定是(　　) A. 空或只有一个节点 B. 高度等于其节点数 C. 任一节点无左孩子 D. 任一节点无右孩子 【解析】 前序遍历顺序是“M－L－R”,后序遍历的顺序是“L－R－M”,其中L－R的相对位置不发生变化,变化的是M的位置。题目指出二叉树的先序和后序结果正好相反,分析以下几种情况:①当二叉树只有一个节点时,只有M、L和R为空,满足条件;②当二叉树为空时,M、L和R均为空,满足条件;③当二叉树任一节点无左孩子时,L为空,前序遍历为M－R,后序遍历为R－M,结果正好相反,满足条件;④当二叉树任一节点无右孩子时,R为空,前序遍历的结果为M－L,后序遍历的结果为L－M,满足条件;综上,上述分析的四种条件都满足二叉树的高度等于其节点数。B正确。 B 35 12. 已知某二叉树的前序遍历是cdaefh,中序遍历是adechf。下列说法中,正确的是(　　) A. 该二叉树是完全二叉树 B. 该二叉树的数组实现示意图如下 0 1 2 3 4 5 a c d e f h C. 该二叉树的高度为4 D. 该二叉树的后序遍历是aedfhc A 36 【解析】 由前序遍历和中序遍历可以绘制出如图所示的对应的二叉树及数组实现示意图,B错误。 0 1 2 3 4 5 c d f a e h 综上可知,其高度为3,C错误。后序遍历为aedhfc,D错误。 13. 某二叉树的中序遍历为BACEDF,前序遍历为ABCDEF。下列关于该二叉树的说法, 正确的是(　　) 该二叉树是完全二叉树 B. 该二叉树的高度为3 C. 该二叉树有4个叶子节点 D. 该二叉树的总边数为5 【解析】 根据题干描述,该二叉树如图所示。 由图可知,该二叉树不是完全二叉树,A错误。该二叉树的高度为4, B错误。该二叉树有3个叶子节点,C错误。该二叉树的总边数为5, D正确。 D 38 14. 某完全二叉树的总节点数为 10,用数字[1~10]逐层依次标示各个节点。下列关于该二叉树的说法,错. 误. 的是(　　) A. 叶子节点数比度为 2 的节点数多1 B. 中序遍历的顺序为8－9－4－10－5－2－1－6－3－7 C. 若某节点无左孩子节点,则此节点亦无右孩子节点 D. 用一维数组存储该树,所有节点对应的数组元素一定是连续的 【解析】 本题考查二叉树的遍历。具体二叉树的形态如图所示。 因此其中序遍历数序为8－4－9－2－10－5－1－6－3－7, B符合题意。 B 39 15. 某二叉树的中序遍历的结果是DGBAECF,后序遍历的结果是GDBEFCA。下列关于该二叉树的说法,错. 误. 的是(　　) A. 该二叉树前序遍历结果是ABDGCEF B. 该二叉树是满二叉树 C. 该二叉树有3个叶子节点 D. 节点D是节点G的父节点 【解析】 本题考查二叉树的遍历。根据中序遍历结果是 DGBAECF,后序遍历结果是GDBEFCA,可得具体二叉树 的形态如图所示。 因此该二叉树不是满二叉树,B符合题意。 B 40 $