资源简介

(共48张PPT)
课时26 树与二叉树
一、树的概念
树可以描述为由 n（n≥0）个节点（Node）构成的一个有限　　　　以及在该集合上定义的一种　　　　关系。
集合
节点
n-1
二、树的属性
子树
最大
前驱
0
0
根节点
下端
孩子
1
1.线性结构中必存在着唯一的一个“第一个元素”和唯一的一个“最后的元素”；除第一个元素以外，其他数据元素均有唯一的前驱，除最后一个元素以外，其他数据元素均有唯一的后继。
2. 树形结构是比较复杂的　　　　结构，在有一个以上节点的树形结构中，它只有
　　　　没有前驱、只有后继的根节点，可以有多个没有后继、只有前驱的叶子节点，其余的节点只有一个直接前驱和多个直接后继。
非线性
一个
三、树形结构和线性结构
1. 树结构：一个节点只和它的父节点和孩子节点有关系。
2. 图结构：每个顶点都可能和其他任意顶点有关系，是一种更为复杂的非线性结构。
（1）图结构图示。
四、树结构和图结构
（2）图结构与树结构的不同点。
①树结构有分明的层次关系，同一层的节点之间不会有边相连；图结构中没有明显的层次关系，每个顶点之间都可能存在一条边。
②树中节点数量和边的数量之间有关联；图结构中顶点数量和边的数量之间无关联，互不影响。
③图结构是比树结构更为复杂的非线性结构，适合用于人际关系图的表示。
1. 二叉树是一个具有 n（n≥0）个节点的有限集合。二叉树的所有节点的度都小于或者等于　　　　。当 n=0 时，二叉树是一棵空树；当 n≠0 时，则是一棵由
　　　　和两棵互不相交的、分别称作这个根节点的左子树和右子树组成的二叉树。
2. 如图所示，二叉树中的子树也为二叉树，节点 A 的左子树和右子树都不为空；节点 B 的左子树和右子树都不为空；节点 C 的左子树为空，右子树不为空；节点 D、E、F 的左子树和右子树都为空。
2
根节点
五、二叉树的概念
3.二叉树的五种形态。
4.完全二叉树最多只有最下面两层中的节点度数小于 2，且最下面一层的叶子节点都依次排列在该层的　　　　位置，如图所示。
最左边
1. 二叉树的第 k 层上最多有　　　　（k≥1）个节点。
2. 深度为 k 的二叉树最多有　　　　（k≥1）个节点。
3. 在任意一棵二叉树中，若度为 2 的节点数量为 n2，叶子节点（度为 0 的节点）数为 n0，则有 n0=　　　　。
（1）二叉树中总的节点数 n=n0+n1+n2。二叉树的总边数 n-1=0×n0+1×n1+2×n2= n1+2×n2。
（2）例如，有如图所示的甲、乙两棵二叉树：在甲树上，度为 2 的节点数是 1，度为 1 的节点数是 1，叶子节点数为 2；在乙树上，度为 2的节点数是 2，度为 1 的节点数是 1，叶子节点数为 3。
2k-1
2k-1
六、二叉树的性质
n2+1
4.二叉树的应用。
（1）二叉树在实际应用中非常广泛，如基于二叉树的查找方法（二叉排序树查找），具有较高的查找效率，还能够在查找表中进行数据插入和删除等动态查找操作。
（2）最优二叉树（哈夫曼树）被广泛应用于编码和决策等方面。
（3）哈夫曼树是指在具有 n 个带权叶子节点的所有二叉树中，带权路径长度 WPL 最小的二叉树。在最优二叉树中，权值较大的节点离根较近。
典例 1 如图所示的树结构中，节点数量最多的子树中的节点个数是 （　　）
A.8
B.7
C.4
D.5
B
√
题型导向一　树的基础知识
胜券点拨1
明考向 本题主要考查树的基础知识和概念
审关键 子树的分辨
考场思 维快闪 如图所示的画框部分为该树结构中节点最多的子树，包含的节点共7个
典例 2 如图所示的树结构中，树的内部节点有 （　　）
A.B、E、C、F、H
B.D、E、I、J、F、G、H
C.A、B、C
D.B、E、C
D
√
胜券点拨2
明考向 本题主要考查树的基础知识
审关键 根节点、分支节点、内部节点、叶子节点等概念的辨析
考场思 维快闪 树中度不为0的节点称为分支节点，除根节点外的分支节点为内部节点，即除了叶子节点和根节点之外的节点都是内部节点
典例 3 有如图所示的树，请回答下列问题：
（1）该树中的节点数量是　　　　　　，边的数
量是　　　　　　；该树中度为 2 的节点个数
是　　　　　　；该树的度为　　　　　　。
（2）该树中的叶子节点分别是　　　　　　。
（3）与节点 E 在同一层的节点有　　　　　　 ；
该树的高度是　　　　　　。
13
12
3
3
C、E、K、G、H、M
C、D、J
5
胜券点拨3
明考向 本题主要考查树的基础知识
审关键 树的各种节点分类、树的度和边判断、树的高度判断
考场思维快闪 （1） 该树中节点共有13个，边为节点数减1，共12条；度为2的节点也就是有2个后继的节点，分别是A、F、J；树的度为树中最大的节点的度，该树中度最大的节点是B，其度为3，所以该树的度为3
（2） 叶子节点即树中没有后继的节点，逐层查找分别是C、E、K、G、H、M
（3） 节点E在树中的第三层，与它在同一层的节点分别是C、D、J，该树中节点的最大层数是5，故该树的高度为5
典例 4 有一棵树的度为 3，其中度为 3 的节点有 1 个，度为 2 的节点有 3 个，度为 1 的节点有 2 个，则度为 0 的节点有 （　　）
A.5 个
B.6 个
C.10 个
D.11 个
B
√
题型导向二　树的特点应用
胜券点拨4
明考向 本题主要考查树的特点
审关键 树的节点数与边的数量的对比
考场思 维快闪 一个节点连接其后继节点的边的数量即该节点的度。根据已知条件可得该树的边共有3×1+2×3+1×2=11条，再根据定理“对于一棵具有n个节点的树，它有n-1条边”，可知该树的节点总数为12。故度为0的节点共有12-1-3-2=6个
典例 5 有一棵树的度为 4，高度为 3，则下列关于该树的说法，正确的是 （　　）
A.该树中最多有 21 条边
B.该树最少有 5 条边
C.该树的根节点的度一定为 4
D.该树中至少有 3 个叶子节点
B
√
胜券点拨5
明考向 本题主要考查树的性质
审关键 有n个节点的树，其边的数量为n-1；树的基本性质和特点
考场思维快闪 A 树中节点数量越多则边的数量越多，该树中节点数量最多的情况是除了最下层节点外，所有节点的度都是4，即1+4+16=21，故边的数量最多是20
B 树中节点数量越少则边的数量越少，该树中节点数量最少的情况是只有一个节点的度为4，高度为3的树结构最少有3个节点，故最少节点数为3+3=6，则边的数量最少是5
C 树的度取决于树中最大的节点的度，不一定是根节点，比如前两层都只有1个节点，第三层有4个节点，则此时根节点的度不为4
D 该树的度为4，则度为4的节点在第1层或第2层，故至少会有4个叶子节点
典例 6 ［2025 浙南名校联盟］某二叉树一共有 4 个节点，其中度为 2 的节点有 1 个，则该二叉树的形态有 （　　）
A.5 种
B.6 种
C.7 种
D.8 种
B
√
题型导向三　二叉树的概念与性质
胜券点拨6
明考向 本题主要考查二叉树的概念和性质
审关键 度为2的节点有1个
考场思 维快闪 若度为2的节点是根节点，则有4种形态。若度为2的节点位于第二层，则有2种形态。一共有6种形态
典例 7 ［2025稽阳联考］有一棵深度为 4 的二叉树，已知其根节点左侧的节点总数比右侧的节点总数多 1，则下列说法正确的是 （　　）
A.该树一定是一棵完全二叉树
B.根节点右侧可能只有 1 个节点
C.该二叉树可能共有 16 个节点
D.该二叉树可能共有 7 个叶子节点
D
√
胜券点拨7
明考向 本题主要考查二叉树的概念和性质
审关键 深度为4的二叉树、根节点左侧的节点总数比右侧的节点总数多1
考场思维快闪 A 该树不一定是一棵完全二叉树
B 该二叉树的深度为4，则根节点左侧至少有3个节点，则根节点右侧至少有2个节点
C 当二叉树是满二叉树时，节点数最多，共24-1=15个，又因为根节点左侧的节点总数比右侧的节点总数多1，所以该二叉树最多只有14个节点
D 若该二叉树为完全二叉树，则共有7个叶子节点
1.根节点：没有前驱的节点。
2.叶子节点：没有后继的节点。
3.节点的度：一个节点拥有的子树个数。
4.树的度：一棵树中，最大的节点的度即为树的度。
5.节点的层数：从根节点开始算，根节点的层数为 1，其余节点的层数为其父节点的层数加 1。
6.树的高度（深度）：树中节点的最大层数。
通法一　树的概念重点掌握
1.树中所有节点的度数相加即为树中边的数量。
2.对于一棵具有 n 个节点的树，它有 n-1 条边。
通法二　树的特点
1.下列关于树结构的说法，不正确的是 （　　）
A.树的元素之间具有分支层次关系
B.若某数据结构的节点有一个及以上后继，则该数据结构一定是树结构
C.只有一个节点的结构也可以是树
D.树中节点的层次从1开始计算
树结构的节点可以有0个或多个后继，最多只有一个前驱。图结构的节点有多个后继也可以有多个前驱。
一、树的基础知识
B
√
2.下列实例中，适合用树结构来描述的是 （　　）
A.根据门牌号方便找到指定的地址
B.画图过程中的撤消和复原
C.一个家族的家谱
D.一个人的人际关系
门牌号一般按照顺序排列，适合用数组结构描述。画图过程中的撤消和复原一般是对最后一步操作的撤消和复原，所以合适使用栈结构来描述。一个家族的族谱中，一个人对应一对父母，一对父母对应若干个孩子，适合使用树结构来表示。一个人的人际关系不符合树结构的特征，因为一个人的人际关系通常类似一张网，适合使用图结构来表示。
C
√
3.一棵树的度指的是 （　　）
A.该树中所有节点的度的和
B.该树中度最大的节点的个数
C.该树中度最大的节点的度
D.该树中根节点的度
C
√
树结构中最大的节点的度为树的度。
二、树的特点应用
4.在1个树结构中，节点B有3个兄弟节点，节点P为节点B的双亲节点，则节点P的度是 （　　）
A.3
B.4
C.5
D.1
B
√
节点B有三个兄弟节点，说明它们拥有相同的双亲节点，也就是说节点P有4个孩子节点，故节点P的度为4。
5.一棵二叉树上第4层的节点数最多是 （　　）
A.2
B.4
C.6
D.8
二叉树第k层上的节点数量最多是2k-1（k≥1）个。
D
√
三、二叉树的概念与性质
6.一棵二叉树的深度为k(k≥1)，则该二叉树中的节点数最多有 （　　）
A.2k-1
B.2k
C.2k-1
D.2k
深度为k的二叉树最多有2k-1（k≥1）个节点。
C
√
7.假设某完全二叉树的树根为第1层，树中第10层有5个叶子节点，则该完全二叉树的节点个数最多为 （　　）
A.2047
B.2048
C.2037
D.2038
C
√
二叉树的第10层上最多有29=512个节点，前10层最多有210-1=1023个节点。已知该完全二叉树中第10层有5个叶子节点，则该完全二叉树中第10层左侧的512-5=507个节点都有孩子节点，则第11层最多有507×2=1014个节点，再加上前10层的节点，一共最多有2037个节点。
8.下列图示不属于树状结构的是 （　　）
B
树结构中数据元素之间的关系都呈现出一个共同的特点，即一个元素前面（或上面）只有一个元素，而后面（或下面）却有多个（0个或多个）元素相邻，所有数据元素之间的关系特征就像一棵倒放的树。
√
9.在一棵树中，既有双亲节点也有孩子节点的节点称为 （　　）
A.根节点
B.叶子节点
C.分支节点
D.内部节点
D
√
双亲节点又称为父节点。根节点没有父节点，叶子节点没有孩子节点，树中度不为0的节点称为分支节点，除根节点以外的分支节点称为内部节点。故除了根节点和叶子节点以外的所有节点称为内部节点，除了根节点和叶子节点之外的节点都有一个父节点和一个及以上的孩子节点。
10.有树结构如图所示。
下列关于该树结构的说法，正确的是 （　　）
A.该树结构的高度为2
B.该树结构的度为5
C.该树结构中叶子节点的数量是4
D.该树结构中度为1的节点数是2
D
√
该树的高度为4。该树的度为3。该树中叶子节点的数量是3。
11.有树结构如图所示。
下列关于该树的说法，不正确的是 （　　）
A.节点C、D有同一个双亲节点
B.该树中有2个度为2的节点
C.节点K、L、M互为兄弟节点
D.该树的叶子节点有H、I、J、K、L、M
D
√
该树的叶子节点除选项描述的之外，还有一个节点C。
12.有树结构如图所示。
下列关于该树结构的说法，正确的是 （　　）
A.该树的度为4
B.该树有4层
C.该树中共有13条边
D.该树的叶子节点数量是5
B
√
该树中最大的节点的度为3，故该树的度为3。两个节点之间的连接线为一条边，故该树中边的数量是12。叶子节点即树中没有后继节点的节点，该树的叶子节点数量为6。
13.某树由4个节点组成，则该树的度最大是 （　　）
A.4
B.3
C.2
D.1
B
√
有n个节点的树有n-1条边，一棵节点数为4的树，它的边数为3，一个节点连接的边为该节点的度，若这3条边都与同一个节点连接，则度最大为3。
14.某树的度为3，高度为3，且该树第三层的节点数为8，则该树第二层的节点数是 （　　）
A.1
B.2
C.3
D.4
C
√
树的度为3表示最大的节点的度为3。第三层的节点数为8，已知第二层每个节点的度小于等于3，故第二层的节点数大于等于3；已知第一层只有1个节点，其度小于等于3，故第二层的节点数小于等于3。综上，第二层的节点数为3。
15.某树有12条边，5个叶子节点，则该树结构的内部节点个数是 （　　）
A.7
B.9
C.13
D.11
A
√
该树有12条边，故它的节点数量为13，减去5个叶子节点，再减去1个根节点，内部节点的数量为13-5-1=7。
16.已知一棵树的度为3，高度为4，则该树中的节点数最多是 （　　）
A.27
B.40
C.81
D.121
B
√
求最多的节点数，则设所有节点的度都是3，第一层为根节点，节点数为1，第二层为根节点的孩子节点，共3个，第三层为3个节点的所有孩子节点，即3*3=9，第四层为9个节点的所有孩子节点，即3*9=27，所有节点相加的和为1+3+9+27=40。
17.在一棵度为4的树中，度为4的节点数为1，度为3的节点数为1，度为2的节点数为1，度为1的节点数为0，则度为0的节点数为 （　　）
A.4
B.2
C.7
D.5
C
√
一个节点的度表示其拥有的孩子节点的个数，即该节点连接的边，故该树中的边共有4*1+3*1+2*1+1*0=9条；已知树中边的数量为节点数减1，故该树中的节点总数为10。故减去已知的节点（1+1+1+0）得到的数即为度为0的节点的数量。
18.已知在一棵树中共有11个节点，其中度为1的节点有3个，度为2的节点有0个，根节点的度为3，则该树的度最大是 （　　）
A.3
B.4
C.5
D.6
B
√
已知该树中共有11个节点，故该树共有10条边。树中边的数量即是树中所有节点的度数的和，故将10减去根节点的度，再减去3个度为1的节点的度，得到的结果为4。故该树中可以有一个节点的度为4，该树结构的度最大可以是4。
19.一棵二叉树中某一层的节点数是314，则该层至少是二叉树的第几层 （　　）
A.7
B.8
C.9
D.10
D
√
314在28~29之间，已知二叉树的第k层中，节点数最多有2k-1（k≥1）个，故314大于第9层的最大节点数，至少在第10层。
20.将一棵有50个节点的完全二叉树从第一层的根节点开始，每一层中从左到右依次对节点进行编号，根节点的编号为1，则编号为15的节点的左孩子编号为 （　　）
A.空
B.14
C.16
D.30
D
√
根据深度为k的二叉树最多有2k-1（k≥1）个节点这个性质，可以推测，节点数为50的完全二叉树，因为25-1<50<26-1，所以该二叉树共六层，第五层上的节点编号范围是16~31，编号15的节点为第四层的最后一个节点，其孩子节点为第五层的最后两个节点，即30和31，故编号15的左孩子编号为30。
21.某二叉树有n个节点，若n为奇数，则该二叉树的叶子节点的个数最多是 （　　）
A.n-1
B.n//2
C.n//2+1
D.n/2
C
√
当二叉树是一个满二叉树时，叶子节点数量最多。满二叉树的叶子节点全部在最后一层，设该二叉树共有k层，则n=2k-1，第k层的节点数为2k-1，即(n+1)/2，因为n为奇数，故(n+1)/2等价于n//2+1。
22.某二叉树如图所示，下列说法正确的是 （　　）
A.节点D、F都是节点B的孩子节点
B.该二叉树的度和深度分别为2和3
C.该二叉树的叶子节点数为1
D.若补全成高度为5的满二叉树，则需增加24个节点
D
√
节点D、E是节点B的孩子节点。该二叉树的深度为4。该二叉树的叶子节点数为3。
23.请画出由3个节点组成的二叉树的不同形态。
由3个节点组成的树共有以下5种形态。
24.根据如图所示的树结构，请回答下列问题：
（1）该树结构的叶子节点是　　　　　　　。
（2）该树结构的内部节点是　　　　　　　。
（3）节点A、D、G、R的度分别是　　　　 　。
C、E、F、Z、P、H
（1）叶子节点即树中没有后继的节点。　（2）内部节点即树中除了根节点和叶子节点之外的所有节点。　（3）节点的孩子节点个数即是该节点的度。
B、G、R、Q、D
3、1、1、2

展开更多......

收起↑