资源简介

课时26　树
【学业要求】
知识点 学业水平等级
1.抽象二叉树的数据结构形式,掌握二叉树的概念及性质。 3
2.通过数组和链表实现树的创建,理解数组和链表相应位置的方法。 4
3.掌握前序遍历、中序遍历和后序遍历等规则。 4
　　树是非线性结构的典型代表,需要学生掌握二叉树的概念及性质,掌握利用数组来存储二叉树,重点是确定先访问左节点,再访问右节点的前提下,根节点可以有三种不同位置进行访问,遍历树的前序、中序、后序三种遍历方法。2023年1月卷考查树的遍历方法,2023年6月卷考查了树的形态与遍历方法。
1.(2023年6月浙江选考)某二叉树的树形结构如图所示,其前序遍历结果为BDEFCA,则中序遍历结果为(　　)
A.EDCFBA B.ECFDAB
C.BFDEAC D.EDFCBA
答案　A
解析　本题考查二叉树的遍历。 前序遍历可知B为二叉树根节点,D和左子树根节点,E和F为左子树的左右孩子。C为F的左孩子,A为树的右子树。该树结构如图所示。因此中序遍历为EDCFBA。
2.(2023年1月浙江选考)下列二叉树中,中序遍历结果为 BAEDFC的是(　　)
答案　C
解析　本题考查二叉树遍历。中序遍历的方法:左子树-根-右子树,每个子树,都遵循以上规定。A选项中序遍历结果为EDFBAC。B选项中序遍历结果为BEDFAC。C 选项中序遍历结果为BAEDFC。D选项中序遍历结果为BACEDF。
1.　　　　可以描述为由n(n≥0)个节点(Node)构成的一个有限集合以及在该集合上定义的一种节点关系。
2.集合中的元素称为树的　　　　,n=0的树称为　　　　;树中某个节点下面的所有节点所构成的树称为该节点的　　　　。
3.树的两个节点之间如果有一条边连接,那么称这两个节点之间存在一条　　　　,对于一棵具有n个节点的树,它有n-1条边。
4.树的一个节点所拥有的子树个数称为该节点的　　　　,最大的节点的度称为树的度。线性表是度为1的特殊树状结构。
5.在树状结构中,没有前驱节点的称为　　　　,又称为开始节点。度为0的节点称为　　　　,也称为终端节点。
6.在树形结构中,对于两个以边直接连接的节点,上端节点称为下端节点的　　　　或双亲节点(Parent)。相应地,下端节点称为上端节点的孩子节点(Child)。
7.树中节点的　　　　从根开始计算,根的层数为1,其余节点的层数等于其父节点的层数加1。树中节点的最大层数称为树的　　　　　　。
8.　　　　是一个具有n(n≥0)个节点的有限集合,它的所有节点的度都小于或等于2。当n=0时,二叉树是一棵空树;当n不等于0时,它是一棵由根节点和两棵互不相交的,分别称作这个根节点的　　　　和　　　　组成的二叉树。
9.　　　　　　　　至多只有最下面两层的节点度数小于2,且最下面一层的叶子节点都依次排列在该层的最左边位置。
10.二叉树的性质:①二叉树的第k层最多有　　　　(k≥1)个节点;②深度为k的二叉树最多有2k-1(k≥1)个节点;③在任意一颗二叉树中,若度为2的节点数量为n2,叶子节点(度为0的节点)数为n0,则n0=n2+1。
自我校对:1.树(Tree)　2.节点　空树　子树　3.边　4.度(Degree)　5.根节点(Root)　叶节点(Leaf)
6.父节点　7.层数(Level)　高度或深度(Depth) 　8.二叉树　左子树　右子树　9.完全二叉树　10.2k-1
【典例1】 (2025年6月浙江选考)某二叉树如图所示,E节点在前序遍历序列中的位置记号为x。下列二叉树中,E节点在中序遍历序列中的位置序号也为x的是(　　)
思维点拨
明考向 本题考查二叉树的遍历
精点拨 前序遍历到节点E是第4个节点。在中序遍历序列中,A选项节点E是第4个节点。B选项节点E是第3个节点。C选项节点E是第5个节点。D选项节点E是第3个节点。
答案　A
【变式1】 (2025年1月浙江选考)某二叉树如图所示,若其中的一个叶子节点增加右子树(仅包含节点N),则新二叉树的中序遍历结果不可能是(　　)
A.CNBDAE B.CBDNAE
C.CBDAEN D.NCBDAE
答案　D
解析　本题考查二叉树的中序遍历。A选项节点C增加右子树后,中序遍历为“CNBDAE”。B选项节点D增加右子树后,中序遍历为“CBDNAE”。C选项节点E增加右子树后,中序遍历为“CBDAEN”。D选项中序遍历先遍历左子树,因此不可能出现在第1个位置。
【典例2】 某完全二叉树包含5个节点,其根节点在后序遍历序列、中序遍历序列中的位置序号分别记为x,y,则x-y的值为(　　)
A.0 B.1
C.2 D.3
思维点拨
明考向 本题考查树的性质和遍历
精点拨 构建一个5个节点完全二叉树如图所示,后序遍历为CDBEA,中序遍历为CBDAE,则x,y的值分别为5和4,差值为1
答案　B
【变式2】 某完全二叉树的中序遍历序列为abcdefgh,下列属于兄弟节点的是(　　)
A.节点a和节点b B.节点b和节点c
C.节点c和节点g D.节点d和节点f
答案　C
解析　本题考查树的性质和遍历。构建完全二叉树如图所示。A和选项两个节点不在同一层中。C选项节点c和节点g分别为节点e的左右孩子,属于兄弟节点。D选项节点d和节点f的父亲节点依次为c和g,因此不属于兄弟节点。
【典例3】 用一维数组表示二叉树,如表所示:
0 1 2 3 4 5 6 7 8 9 10
A B C D E F G
下列有关该二叉树的说法正确的是(　　)
A.该树中共有4个叶子节点
B.该树是完全二叉树,其深度为4
C.该树的中序遍历为B-F-D-G-A-C-E
D.该二叉树的结构图为(如图所示)
思维点拨
明考向 本题考查二叉树的基本知识
精点拨 第3层节点的索引号为3,4,5,可见B没有左子树,但有右子树,因此不可能是满二叉树,B也不是叶子节点。二叉树形态如图所示:
答案　C
【典例4】 某二叉树用一维数组存储结构如表所示:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G H I
下列有关该二叉树的说法正确的是(　　)
A.该树度为2的节点有4个
B.该树的前序遍历为A-B-D-E-G-H-C-F-I
C.该树是完全二叉树,其深度为4
D.该树中共有3个叶子节点,分别是G、H、I
思维点拨
明考向 本题考查二叉树的相关知识
精点拨 根据数组画出树如图所示,可以得到正确的前序遍历序列
答案　B
　　树指除根节点外,每个节点只有一个前驱,但可以有0个或多个后继。树体现的是一种层次和分支的关系,前驱表示他只能隶属于一个层次,但他可能有0个或多个分支结构。二叉树的遍历是将非线性结构转换为线性结构,是按照一定的规则和次序(先访问左节点,后访问右节点)访问二叉树中的所有节点,使得每个节点都被访问一次且仅被访问一次。一棵二叉树必定先访问左节点,再访问右节点,将根节点可能的位置分为前、中、后序三种遍历方式。在前序和后序遍历序列中,能明确树的根节点,在中序遍历中,可以根据根节点的位置来确定左子树和右子树。
完全二叉树指从根节点到倒数第二层的子树为满二叉树,最后一层的节点依次从左向右排列。二叉树的建立可以用数组或者链表数据结构来实现。用数组实现时,需把二叉树补全为一棵完全二叉树,优点是能快速地检索到某个节点的值,如果根节点编号为1,则第i个节点的左孩子编号为2*i,右孩子编号为2*i+1。缺点是当这棵二叉树不是完全二叉树时,会造成存储空间的浪费。
1.某完全二叉树共有300个节点,该二叉树的高度是(　　)
A.8 B.9
C.10 D.1l
答案　B
解析　完全二叉树倒数第2层是满二叉树,n层满二叉树总共节点数为2n-1,因此8层满二叉树节点数为255,该树的高度为9。
2.已知完全二叉树T共有 78 个节点,则其叶子节点数量为(　　)
A.15 B.32
C.39 D.40
答案　C
解析　设二叉树0度、1度和2度的节点个数分别为t0,t1,t2,有等式t0+t1+t2=78和t0=t2+1成立,代入可得t0+t1+t0-1=78,且完全二叉树1度节点个数为0或1,因此t1值为1。
3.某完全二叉树包含节点A、B、C、D、E、F,其中A为根节点,C、D、F为叶子节点,则该完全二叉树的前序遍历结果不可能为(　　)
A.ABDCEF B.AFBCDE
C.AECDBF D.ABCFED
答案　B
解析　根据完全二叉树的定义,画出如图所示形态,其中x可能是B或E,y可能是C、D、F。在前序遍历中,C、D、F不可能出现在第2个位置。
4.(2026年1月浙江选考)某二叉树有 a、b、c、d 四个节点,若中序遍历序列为 abcd,后序遍历序列为 dcba,则该二叉树的树形结构为 (　　)
答案　C
解析　本题考查二叉树的遍历。后序遍历序列确定树或子树的根节点,中序遍历序列区分左右子树。树的根节点为a,右子树的中序遍历序列为bcd;树bcd的根节点为b,右子树的中序遍历序列为cd。树cd的根节点为c,右子树为d。
5.某二叉树的树形结构如图所示,后序遍历结果为 stnaqm,则该二叉树的中序遍历结果是 (　　)
A.mntsqa 　　　　B.ntsmqa
C.nstmqa 　　　　D.nstmaq
答案　C
解析　本后序遍历规则是左右根,先在图中画出二叉树各节点的值,再根据中序遍历的规则,得到遍历的结果nstmqa。
6.某完全二叉树的中序遍历结果为“天生我才必有用”,其前序遍历结果为(　　)
A.天生我才必有用 B.天我生必用有才
C.才生天我有必用 D.才生有天我必用
答案　C
解析　本题考查二叉树及其遍历。根据中序遍历结果,该完全二叉树形态为:
则该二叉树的前序遍历为:才生天我有必用。
7.某二叉树有三个节点,其前序遍历序列是“甲乙丙”,后序遍历序列是“丙乙甲”,那么这棵二叉树的中序遍历序列不可能是(　　)
A.乙丙甲 B.丙乙甲
C.甲乙丙 D.乙甲丙
答案　D
解析　用前序遍历和4个选项的中序遍历还原出二叉树,分别为
D选项得到的二叉树的后序遍历结果为乙丙甲,与试题不符。
8.某二叉树前序遍历为ABDCE,后序遍历为DBECA,则该二叉树可能情况数量是(　　)
A.1 B.2
C.4 D.6
答案　C
解析　本题考查二叉树遍历的相关知识。左右子树的根节点都只有一个子节点,以下四种情况的前序和后序遍历都符合题目要求:
9.某深度为3的二叉树中序遍历结果为“ABCD”,则前序遍历结果不可能是(　　)
A.ABCD B.DBAC
C.CBAD D.ACBD
答案　A
解析　假设树的根节点为A,无左子树,由于深度为3,BCD是其右子树,占两层,因此C是B和D的根,前序遍历和中序遍历不可能相同。可以推断前序遍历结果D选项是可能的,A选项是不可能的。B选项假设D是根,无右子树,ABC为左子树,B是AC的根,前序为BAC。C选项假设C是树的根,AB为其左子树,前序可以是AB,也可以是BA。
10.用一维数组来表示某二叉树如表所示,则下列说法不正确的是(　　)
0 1 2 3 4 5 6 7 8 9 10 11 12
A B C D E F G H
A.该二叉树的深度为4
B.节点B有两个孩子节点,分别为E和F
C.该二叉树的中序遍历结果为DBGEAFHC
D.叶子节点的数量比度为2的节点数量多1
答案　B
解析　构建的二叉树如图所示,A选项该树有4层。B选项节点B的两个孩子分别是D和E。C选项中序遍历每棵子树的遍历方式为左根右。D选项任何二叉树中,叶子节点的数量比度为2的节点数量多1个。
1.假设完全二叉树的树根为第1层,树中第10层有5个叶子节点,则完全二叉树最多节点个数是(　　)
A.2047 B.2048
C.2037 D.2038
答案　C
解析　根据完全二又树的性质可知,叶子节点最多只出现在最下面2层,此题考查的是最多节点数,那么该二又树应有11层。前10层节点:210-1=1023第11层满节点数为:20-1=1024。因为第10层有S个叶子节点,所以第11层少10个节点,故总结点数为,1023+1024-10=2037。
2.有一棵树,节点的高度和个数如表所示。
度 0 1 2 3 4
节点个数 x 4 3 2 1
则叶子节点x的个数为(　　)
A.8 B.9
C.10 D.11
答案　D
解析　本题考查树的基本概念。树中所有节点的度之和加1为节点总数,因此1*4+2*3+3*2+4*1=21。节点数为x+4+3+2+1=x+10,因此可以得到叶子节点数为11个。
3.某二叉树的中序遍历结果是CBDAE,前序遍历结果是ABCDE。若其中的一个叶子节点增加左子树(仅包含节点N),则新二叉树的后序遍历结果不可能是(　　)
A.NCDBEA B.CNDBEA
C.CDBNEA D.CDNBEA
答案　D
解析　根据中序遍历和前序遍历,确定二叉树的形态,并在可能的位置上添加左子树,如图所示。后序遍历可能是NCDBEA、CNDBEA和DBNEA。
4.某非完全二叉树包含5个节点,中序遍历为ABCDE,添加1个节点F后变成完全二叉树。以下对于该完全二叉树的说法,正确的是(　　)
A.根节点可能为D
B.后序遍历可能为AFBEDC
C.节点B的父节点一定是C
D.深度为3,节点E在第二层
答案　C
解析　添加1个节点F后变成完全二叉树如图所示。A选项根节点为C。B选项后序遍历为AFBDEC。C选项节点B的父节点一定是C。
5.有一棵二叉树如图所示,关于该树,以下说法正确的是(　　)
A.该树是一棵完全二叉树,树的高度为4
B.该树中序遍历顺序为:15,22,23, 25,28,30,32,35
C.该树共有3个叶子节点
D.该树中度为1的节点数是0
答案　B
解析　A选项完全二叉树的第n-1层为满二叉树,因此该树不是完全二叉树。C选项该树有4个叶子节点。D选项该树有1个1度节点。
6.下列二叉树中,前序和中序遍历结果一样的选项是(　　)
答案　D
解析　前序遍历是根左右,中序遍历是左根右,当左子树不存在时,两者相同。
7.某二叉树的前序遍历结果为ABC,若该二叉树不是满二叉树,则其后序遍历结果为(　　)
A.ABC B.BCA
C.CBA D.CAB
答案　C
解析　该二叉树可能形态,满足前序遍历为ABC有4种形态,如图所示,后序遍历均为CBA。
8.如图所示,将二叉树A的根节点与二叉树B的根节点连接,使得二叉树A成为二叉树B的左子树,合并为一棵新的二叉树C。下列说法中正确的是 (　　)
A.二叉树C的高度为3
B.二叉树C的叶子节点数量为3
C.二叉树C是一棵完全二叉树
D.二叉树C中序遍历的结果是一个有序序列
答案　C
解析　本题考查二叉树的性质和遍历。新二叉树高度为4;叶子节点数量为4,是一棵完全二叉树;中序遍历的结果为84251637,不是一个有序序列。
9.某二叉树的树形结构如图所示,前序遍历为ABCDEF,则该二叉树的后序遍历结果是(　　)
A.CBFEDA
B.BCADEF
C.ABDCEF
D.FEDCBA
答案　A
解析　根据所给的树形结构,按前序遍历顺序,把 ABCDEF 填入节点中,然后再按后序遍历得到CBFEDA。
10.某二叉树的中序序列是abcdef,且节点d和f是兄弟节点,则其后序序列可能是(　　)
A.adfebc B.bdfeca
C.bdefca D.adcfeb
答案　B
解析　节点e是节点d和f的父节点,则后序遍历必定为dfe,排除C和D选项。A选项节点c为整棵树的根节点,从中序来看,def是整棵树的右子树,但在后序中并不是右子树。B选项节点a为整棵树的根节点,bcdef为右子树,c为右子树的根,b为右子树的左孩子。
11.某二叉树的部分树形结构如图所示,其前序遍历结果为 ABCDEF,下列说法正确的是(　　)
A.该二叉树的深度一定是3 B.节点C和节点D一定都是叶子节点
C.节点F在该二叉树的左子树中 D.该二叉树的后序遍历可能是CDBFEA
答案　D
解析　根据该二叉树的前序遍历如图所示,节点CD在以B为根节点的子树中,节点F在以E为根节点的子树中,左子树可能的结构有:
因此该二叉树的深度可能为3,也可能为4,A错误;节点C和D不一定是叶子节点,B错误;节点F可以是E的左孩子,也可以是F的右孩子,C错误;若节点CD分别为B的左孩子和右孩子,则该二叉树的后序遍历是CDBFEA。
12.某二叉树用一维数组来表示如表所示。该二叉树从根节点开始,按照从上到下,从左到右的顺序依次用A-H字母表示,该二叉树的中序遍历为(　　)
下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
元素 A B C D E F G H
A.DBGEACFH B.DBGEACHF
C.DBEGACHF D.ABCDEFGH
答案　A
解析　本题考查二叉树的相关概念。根据题意,可以构建出如图的二叉树。该树的中序遍历为DBGEACFH。
13.某二叉树的数组表示示意图如表所示,该二叉树的后序遍历序列为(　　)
0 1 2 3 4 5 6 7 8 9 10 11 12 13
A B C D E F G
A.BAFDCGE B.BFDGECA
C.BFGDECA D.DEBFGCA
答案　B
解析　本题考查二叉树的遍历。根据题意画出二叉树如图。
后序遍历是:BFDGECA。
14.某二叉树从根节点开始,按从上到下、自左往右的顺序用 A-G 字母表示,若补全为完全二叉树后,用一维数组表示如表所示。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G
下列关于该二叉树的说法,正确的是(　　)
A.该二叉树的深度为 3
B.节点 E 的父节点是 B
C.该二叉树的中序遍历结果为 BFDGACE
D.该二叉树的叶子节点为 D、E、F、G
答案　C
解析　本题考查二叉树性质和遍历。根据题意画出二叉树如图所示。
该二叉树的深度为 4,E 的父节点是 C,中序遍历是 B-F-D-G-A-C-E,该二叉树的叶子节点是F,G,E。(共56张PPT)
选修一　数据与数据结构
课时26　树
知识点 学业水平等级
1.抽象二叉树的数据结构形式,掌握二叉树的概念及性质。 3
2.通过数组和链表实现树的创建,理解数组和链表相应位置的方法。 4
3.掌握前序遍历、中序遍历和后序遍历等规则。 4
目 录
CONTENTS
真题剖析
01
知识梳理
02
课堂突破
03
当堂检测
04
课后作业
05
真题剖析
1
　　树是非线性结构的典型代表,需要学生掌握二叉树的概念及性质,掌握利用数组来存储二叉树,重点是确定先访问左节点,再访问右节点的前提下,根节点可以有三种不同位置进行访问,遍历树的前序、中序、后序三种遍历方法。2023年1月卷考查树的遍历方法,2023年6月卷考查了树的形态与遍历方法。
1.(2023年6月浙江选考)某二叉树的树形结构如图所示,其前序遍历结果为BDEFCA,则中序遍历结果为(　　)
A
A.EDCFBA B.ECFDAB
C.BFDEAC D.EDFCBA
解析　本题考查二叉树的遍历。 前序遍历可知B为二叉树根节点,D和左子树根节点,E和F为左子树的左右孩子。C为F的左孩子,A为树的右子树。该树结构如图所示。因此中序遍历为EDCFBA。
2.(2023年1月浙江选考)下列二叉树中,中序遍历结果为 BAEDFC的是(　　)
C
解析　本题考查二叉树遍历。中序遍历的方法:左子树-根-右子树,每个子树,都遵循以上规定。A选项中序遍历结果为EDFBAC。B选项中序遍历结果为BEDFAC。C 选项中序遍历结果为BAEDFC。D选项中序遍历结果为BACEDF。
知识梳理
2
1.　　　　可以描述为由n(n≥0)个节点(Node)构成的一个有限集合以及在该集合上定义的一种节点关系。
2.集合中的元素称为树的　　　　,n=0的树称为　　　　;树中某个节点下面的所有节点所构成的树称为该节点的　　　　。
3.树的两个节点之间如果有一条边连接,那么称这两个节点之间存在一条　　　,对于一棵具有n个节点的树,它有n-1条边。
4.树的一个节点所拥有的子树个数称为该节点的　　　　　,最大的节点的度称为树的度。线性表是度为1的特殊树状结构。
树(Tree)
节点
空树
子树
边
度(Degree)
5.在树状结构中,没有前驱节点的称为　　　　　　　,又称为开始节点。度为0的节点称为　　　　　　,也称为终端节点。
6.在树形结构中,对于两个以边直接连接的节点,上端节点称为下端节点的
　　　　或双亲节点(Parent)。相应地,下端节点称为上端节点的孩子节点(Child)。
7.树中节点的　　　　　　从根开始计算,根的层数为1,其余节点的层数等于其父节点的层数加1。树中节点的最大层数称为树的　　　　　　　　　。
根节点(Root)
叶节点(Leaf)
父节点
层数(Level)
高度或深度(Depth)
8.　　　　是一个具有n(n≥0)个节点的有限集合,它的所有节点的度都小于或等于2。当n=0时,二叉树是一棵空树;当n不等于0时,它是一棵由根节点和两棵互不相交的,分别称作这个根节点的　　　　和　　　　组成的二叉树。
9.　　　　　　　　至多只有最下面两层的节点度数小于2,且最下面一层的叶子节点都依次排列在该层的最左边位置。
10.二叉树的性质:①二叉树的第k层最多有　　　　(k≥1)个节点;②深度为k的二叉树最多有2k-1(k≥1)个节点;③在任意一颗二叉树中,若度为2的节点数量为n2,叶子节点(度为0的节点)数为n0,则n0=n2+1。
二叉树
左子树
右子树
完全二叉树
2k-1
课堂突破
3
【典例1】 (2025年6月浙江选考)某二叉树如图所示,E节点在前序遍历序列中的位置记号为x。下列二叉树中,E节点在中序遍历序列中的位置序号也为x的是(　　)
答案　A
思维点拨
明考向 本题考查二叉树的遍历
精点拨 前序遍历到节点E是第4个节点。在中序遍历序列中,A选项节点E是第4个节点。B选项节点E是第3个节点。C选项节点E是第5个节点。D选项节点E是第3个节点。
A.CNBDAE B.CBDNAE
C.CBDAEN D.NCBDAE
D
解析　本题考查二叉树的中序遍历。A选项节点C增加右子树后,中序遍历为“CNBDAE”。B选项节点D增加右子树后,中序遍历为“CBDNAE”。C选项节点E增加右子树后,中序遍历为“CBDAEN”。D选项中序遍历先遍历左子树,因此不可能出现在第1个位置。
【典例2】 某完全二叉树包含5个节点,其根节点在后序遍历序列、中序遍历序列中的位置序号分别记为x,y,则x-y的值为(　　)
A.0 B.1
C.2 D.3
答案　B
思维点拨
明考向 本题考查树的性质和遍历
精点拨 构建一个5个节点完全二叉树如图所示,后序遍历为CDBEA,中序遍历为CBDAE,则x,y的值分别为5和4,差值为1
【变式2】 某完全二叉树的中序遍历序列为abcdefgh,下列属于兄弟节点的是(　　)
A.节点a和节点b B.节点b和节点c
C.节点c和节点g D.节点d和节点f
解析　本题考查树的性质和遍历。构建完全二叉树如图所示。A和选项两个节点不在同一层中。C选项节点c和节点g分别为节点e的左右孩子,属于兄弟节点。D选项节点d和节点f的父亲节点依次为c和g,因此不属于兄弟节点。
C
【典例3】 用一维数组表示二叉树,如表所示:
0 1 2 3 4 5 6 7 8 9 10
A B C D E F G
下列有关该二叉树的说法正确的是(　　)
A.该树中共有4个叶子节点
B.该树是完全二叉树,其深度为4
C.该树的中序遍历为B-F-D-G-A-C-E
D.该二叉树的结构图为(如图所示)
答案　C
思维点拨
明考向 本题考查二叉树的基本知识
精点拨 第3层节点的索引号为3,4,5,可见B没有左子树,但有右子树,因此不可能是满二叉树,B也不是叶子节点。二叉树形态如图所示:
【典例4】 某二叉树用一维数组存储结构如表所示:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G H I
下列有关该二叉树的说法正确的是(　　)
A.该树度为2的节点有4个
B.该树的前序遍历为A-B-D-E-G-H-C-F-I
C.该树是完全二叉树,其深度为4
D.该树中共有3个叶子节点,分别是G、H、I
答案　B
思维点拨
明考向 本题考查二叉树的相关知识
精点拨 根据数组画出树如图所示,可以得到正确的前序遍历序列
　　树指除根节点外,每个节点只有一个前驱,但可以有0个或多个后继。树体现的是一种层次和分支的关系,前驱表示他只能隶属于一个层次,但他可能有0个或多个分支结构。二叉树的遍历是将非线性结构转换为线性结构,是按照一定的规则和次序(先访问左节点,后访问右节点)访问二叉树中的所有节点,使得每个节点都被访问一次且仅被访问一次。一棵二叉树必定先访问左节点,再访问右节点,将根节点可能的位置分为前、中、后序三种遍历方式。在前序和后序遍历序列中,能明确树的根节点,在中序遍历中,可以根据根节点的位置来确定左子树和右子树。
完全二叉树指从根节点到倒数第二层的子树为满二叉树,最后一层的节点依次从左向右排列。二叉树的建立可以用数组或者链表数据结构来实现。用数组实现时,需把二叉树补全为一棵完全二叉树,优点是能快速地检索到某个节点的值,如果根节点编号为1,则第i个节点的左孩子编号为2*i,右孩子编号为2*i+1。缺点是当这棵二叉树不是完全二叉树时,会造成存储空间的浪费。
当堂检测
4
1.某完全二叉树共有300个节点,该二叉树的高度是(　　)
A.8 B.9
C.10 D.1l
解析　完全二叉树倒数第2层是满二叉树,n层满二叉树总共节点数为2n-1,因此8层满二叉树节点数为255,该树的高度为9。
B
2.已知完全二叉树T共有 78 个节点,则其叶子节点数量为(　　)
A.15 B.32
C.39 D.40
解析　设二叉树0度、1度和2度的节点个数分别为t0,t1,t2,有等式t0+t1+t2=78和t0=t2+1成立,代入可得t0+t1+t0-1=78,且完全二叉树1度节点个数为0或1,因此t1值为1。
C
B
解析　根据完全二叉树的定义,画出如图所示形态,其中x可能是B或E,y可能是C、D、F。在前序遍历中,C、D、F不可能出现在第2个位置。
4.(2026年1月浙江选考)某二叉树有 a、b、c、d 四个节点,若中序遍历序列为 abcd,后序遍历序列为 dcba,则该二叉树的树形结构为(　　)
C
解析　本题考查二叉树的遍历。后序遍历序列确定树或子树的根节点,中序遍历序列区分左右子树。树的根节点为a,右子树的中序遍历序列为bcd;树bcd的根节点为b,右子树的中序遍历序列为cd。树cd的根节点为c,右子树为d。
5.某二叉树的树形结构如图所示,后序遍历结果为 stnaqm,则该二叉树的中序遍历结果是(　　)
A.mntsqa　　　　　　　　　　B.ntsmqa
C.nstmqa　　　　　　　　　　D.nstmaq
C
解析　本后序遍历规则是左右根,先在图中画出二叉树各节点的值,再根据中序遍历的规则,得到遍历的结果nstmqa。
6.某完全二叉树的中序遍历结果为“天生我才必有用”,其前序遍历结果为(　　)
A.天生我才必有用 B.天我生必用有才
C.才生天我有必用 D.才生有天我必用
C
解析　本题考查二叉树及其遍历。根据中序遍历结果,该完全二叉树形态为:
则该二叉树的前序遍历为:才生天我有必用。
D
解析　用前序遍历和4个选项的中序遍历还原出二叉树,分别为
D选项得到的二叉树的后序遍历结果为乙丙甲,与试题不符。
8.某二叉树前序遍历为ABDCE,后序遍历为DBECA,则该二叉树可能情况数量是(　　)
A.1 B.2
C.4 D.6
C
解析　本题考查二叉树遍历的相关知识。左右子树的根节点都只有一个子节点,以下四种情况的前序和后序遍历都符合题目要求:
A
解析　假设树的根节点为A,无左子树,由于深度为3,BCD是其右子树,占两层,因此C是B和D的根,前序遍历和中序遍历不可能相同。可以推断前序遍历结果D选项是可能的,A选项是不可能的。B选项假设D是根,无右子树,ABC为左子树,B是AC的根,前序为BAC。C选项假设C是树的根,AB为其左子树,前序可以是AB,也可以是BA。
A.该二叉树的深度为4
B.节点B有两个孩子节点,分别为E和F
C.该二叉树的中序遍历结果为DBGEAFHC
D.叶子节点的数量比度为2的节点数量多1
B
0 1 2 3 4 5 6 7 8 9 10 11 12
A B C D E F G H
解析　构建的二叉树如图所示,A选项该树有4层。B选项节点B的两个孩子分别是D和E。C选项中序遍历每棵子树的遍历方式为左根右。D选项任何二叉树中,叶子节点的数量比度为2的节点数量多1个。
课时作业
5
1.假设完全二叉树的树根为第1层,树中第10层有5个叶子节点,则完全二叉树最多节点个数是(　　)
A.2047 B.2048
C.2037 D.2038
C
解析　根据完全二又树的性质可知,叶子节点最多只出现在最下面2层,此题考查的是最多节点数,那么该二又树应有11层。前10层节点:210-1=1023第11层满节点数为:20-1=1024。因为第10层有S个叶子节点,所以第11层少10个节点,故总结点数为,1023+1024-10=2037。
2.有一棵树,节点的高度和个数如表所示。
D
解析　本题考查树的基本概念。树中所有节点的度之和加1为节点总数,因此1*4+2*3+3*2+4*1=21。节点数为x+4+3+2+1=x+10,因此可以得到叶子节点数为11个。
度 0 1 2 3 4
节点个数 x 4 3 2 1
则叶子节点x的个数为(　　)
A.8　　　　　　B.9　　　　　　C.10　　　　　　D.11
D
解析　根据中序遍历和前序遍历,确定二叉树的形态,并在可能的位置上添加左子树,如图所示。后序遍历可能是NCDBEA、CNDBEA和DBNEA。
4.某非完全二叉树包含5个节点,中序遍历为ABCDE,添加1个节点F后变成完全二叉树。以下对于该完全二叉树的说法,正确的是(　　)
A.根节点可能为D B.后序遍历可能为AFBEDC
C.节点B的父节点一定是C D.深度为3,节点E在第二层
C
解析　添加1个节点F后变成完全二叉树如图所示。A选项根节点为C。B选项后序遍历为AFBDEC。C选项节点B的父节点一定是C。
5.有一棵二叉树如图所示,关于该树,以下说法正确的是(　　)
B
解析　A选项完全二叉树的第n-1层为满二叉树,因此该树不是完全二叉树。C选项该树有4个叶子节点。D选项该树有1个1度节点。
A.该树是一棵完全二叉树,树的高度为4
B.该树中序遍历顺序为:15,22,23, 25,28,30,32,35
C.该树共有3个叶子节点
D.该树中度为1的节点数是0
6.下列二叉树中,前序和中序遍历结果一样的选项是(　　)
D
解析　前序遍历是根左右,中序遍历是左根右,当左子树不存在时,两者相同。
7.某二叉树的前序遍历结果为ABC,若该二叉树不是满二叉树,则其后序遍历结果为(　　)
A.ABC B.BCA
C.CBA D.CAB
C
解析　该二叉树可能形态,满足前序遍历为ABC有4种形态,如图所示,后序遍历均为CBA。
8.如图所示,将二叉树A的根节点与二叉树B的根节点连接,使得二叉树A成为二叉树B的左子树,合并为一棵新的二叉树C。下列说法中正确的是 (　　)
C
A.二叉树C的高度为3
B.二叉树C的叶子节点数量为3
C.二叉树C是一棵完全二叉树
D.二叉树C中序遍历的结果是一个有序序列
解析　本题考查二叉树的性质和遍历。新二叉树高度为4;叶子节点数量为4,是一棵完全二叉树;中序遍历的结果为84251637,不是一个有序序列。
9.某二叉树的树形结构如图所示,前序遍历为ABCDEF,则该二叉树的后序遍历结果是(　　)
A.CBFEDA　　　　　　　　B.BCADEF
C.ABDCEF　　　　　　　　D.FEDCBA
A
解析　根据所给的树形结构,按前序遍历顺序,把 ABCDEF 填入节点中,然后再按后序遍历得到CBFEDA。
10.某二叉树的中序序列是abcdef,且节点d和f是兄弟节点,则其后序序列可能是(　　)
A.adfebc B.bdfeca
C.bdefca D.adcfeb
B
解析　节点e是节点d和f的父节点,则后序遍历必定为dfe,排除C和D选项。A选项节点c为整棵树的根节点,从中序来看,def是整棵树的右子树,但在后序中并不是右子树。B选项节点a为整棵树的根节点,bcdef为右子树,c为右子树的根,b为右子树的左孩子。
11.某二叉树的部分树形结构如图所示,其前序遍历结果为 ABCDEF,下列说法正确的是(　　)
A.该二叉树的深度一定是3
B.节点C和节点D一定都是叶子节点
C.节点F在该二叉树的左子树中
D.该二叉树的后序遍历可能是CDBFEA
D
解析　根据该二叉树的前序遍历如图所示,节点CD在以B为根节点的子树中,节点F在以E为根节点的子树中,左子树可能的结构有:
因此该二叉树的深度可能为3,也可能为4,A错误;节点C和D不一定是叶子节点,B错误;节点F可以是E的左孩子,也可以是F的右孩子,C错误;若节点CD分别为B的左孩子和右孩子,则该二叉树的后序遍历是CDBFEA。
12.某二叉树用一维数组来表示如表所示。该二叉树从根节点开始,按照从上到下,从左到右的顺序依次用A-H字母表示,该二叉树的中序遍历为(　　)
A
解析　本题考查二叉树的相关概念。根据题意,可以构建出如图的二叉树。该树的中序遍历为DBGEACFH。
下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
元素 A B C D E F G H
A.DBGEACFH　　B.DBGEACHF　　C.DBEGACHF　　D.ABCDEFGH
13.某二叉树的数组表示示意图如表所示,该二叉树的后序遍历序列为(　　)
B
解析　本题考查二叉树的遍历。根据题意画出二叉树如图。
后序遍历是:BFDGECA。
0 1 2 3 4 5 6 7 8 9 10 11 12 13
A B C D E F G
A.BAFDCGE B.BFDGECA
C.BFGDECA D.DEBFGCA
14.某二叉树从根节点开始,按从上到下、自左往右的顺序用 A-G 字母表示,若补全为完全二叉树后,用一维数组表示如表所示。
C
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G
下列关于该二叉树的说法,正确的是(　　)
A.该二叉树的深度为 3
B.节点 E 的父节点是 B
C.该二叉树的中序遍历结果为 BFDGACE
D.该二叉树的叶子节点为 D、E、F、G
解析　本题考查二叉树性质和遍历。根据题意画出二叉树如图所示。
该二叉树的深度为 4,E 的父节点是 C,中序遍历是 B-F-D-G-A-C-E,该二叉树的叶子节点是F,G,E。

展开更多......

收起↑