资源简介

(共41张PPT)
课时1　树与二叉树
第四章　树
1.了解二叉树的基本概念和特点，并能结合实例进行分析。2.了解满二叉树和完全二叉树的特点，并能正确区分满二叉树和完全二叉树。3.理解二叉树的性质，并能利用二叉树的性质解决实际问题。
目 录
CONTENTS
知识梳理
01
例题精析
02
随堂检测
03
巩固与提升
04
知识梳理
1
1.树(Tree)的几个基本概念
树是一种_________的数据结构，用它能很好地描述有分支和层次特性的数据集合。
(1)树可以描述为由n(n≥0)个节点构成的一个____________以及在该集合上定义的一种______关系。
(2)节点(Node)：集合中的元素称为树的节点，_________的树称为空树。
根节点：在树形结构中，____________的节点称为根节点(Root)，又称为开始节点。
父节点、孩子节点：在树形结构中，对于两个以边直接连接的节点，上端节点称为下端节点的父节点(Parent)，下端节点为孩子节点(Child)，简称为子节点。
(3)子树：树中某个节点下面所有节点所构成的树称为该节点的子树。
非线性
有限集合
节点
n＝0
没有前驱
(4)边：树的两个节点之间如果有一条边连接，那么称为这两个节点之间存在一条边。
对于一棵有n个节点的树，它有_________条边。
(5)度(Degree)
节点的度：树的一个节点所拥有的____________称为该节点的度。
树的度：________________________称为树的度。
节点的度和树的度是指宽度。
(6)叶子：度为___的节点称为叶子节点(Leaf)，又称为终端节点。
(7)树的深度(高度)：树中节点的层数(Level)从根开始计算，根的层数为___，其余节点的层数等于父节点的层数加1。树中节点的____________称为树的高度或深度(Depth)。
n－1
子树个数
节点的度的最大值
0
1
最大层数
2.二叉树
(1)二叉树的定义
二叉树是指除根节点外的所有节点可分为两个互不相交的有限集合，分别称为左子树和右子树，左子树和右子树也是二叉树。
二叉树的子树有左右之分，且左右子树的次序不能颠倒。
(2)二叉树的高度(深度)
二叉树中节点的____________称为二叉树的深度或高度。
最大层数
(3)二叉树的五种形态
单点树
只有根和右子树
左右子树均非空
3.特殊的二叉树
(1)满二叉树
符合满二叉树的两个条件为：
①每个节点的度数均_______________；
②所有叶子节点都在_________。
(2)完全二叉树
符合完全二叉树的两个条件为：
①只有____________中的节点度数小于2；
②最下一层的叶子节点都依次排列在该层_________位置。
为2或为0
同一层
最下二层
最左边
正确区分满二叉树和完全二叉树的方法：
(1)满二叉树的判断方法：指叶子节点都在最下面一层上，除叶节点外其他每个节点的度数为2。
(2)完全二叉树的判断方法：可将一棵二叉树先变为满二叉树，然后从上到下，同层从左到右的次序从1开始连续编号，如果能按从大到小的顺序连续删除该满二叉树的若干节点后得到该二叉树，则该二叉树为完全二叉树。
4.二叉树的性质
(1)二叉树的第k层上最多有__________ (k≥1)个节点。
(2)深度为k的二叉树最多有__________(k≥1)个节点。
(3)在任意一棵二叉树中，叶子节点数比度为2的节点数_________。
2k－1
2k－1
多1个
例题精析
2
例1 有一棵树，如图所示。
C
解析　本题主要考查的是节点的度和树的度。节点a有三个子节点b、c、d，因此节点a的度为3；树的度是指宽度，即树中节点的度的最大值，树中节点g的度最大，节点g的度为4，因此树的度为4，答案为C。
则该树中节点a的度和树的度分别为(　　)
A.3，3 B.4，3
C.3，4 D.3，10
变式训练　有一棵树，如图所示。
解析　本题主要考查的是树的深度。树中节点的最大层数称为树的高度或深度，根的层数为1，因此树的深度为5，答案为C。
C
则该树深度为(　　)
A.3 B.4 C.5 D.6
例2 若树的根的高度为1，则二叉树的第p层上的节点数最多为(　　)
解析　本题主要考查的是二叉树的性质。当二叉树为满二叉树时，每一层上的节点数最多，第p层上的节点数为2p－1个，因此答案为B。
B
A.2p－1个 B.2p－1 个 C.2p 个 D.2p－1个
变式训练　若树的根的高度为1，则高度为h的二叉树中节点数最多为(　　)
解析　高度为h的满二叉树的节点数为2h－1个，因此答案为C。
C
A.2h－1个 B.2h－1 个 C.2h－1个 D.2h＋1个
例3 有一棵深度为h的满二叉树，共有n个节点，其中叶子节点为m个，则下列等式成立的是(　　)
A.n＝m＋h B.m＝2h－1＋1 C.2m＝n＋1 D.n＝2h＋1
解析　本题主要考查的是满二叉树的性质。深度为h的满二叉树的节点总数为2h－1，因此n＝2h－1；在满二叉树中，叶子节点数为2h－1，因此，m＝2h－1；在满二叉树中，只有度为2的节点和度为0的叶节点，且叶子节点比度为2的节点数多1个，度为2的节点数为n－m，可得到n－m＋1＝m，即2m＝n＋1，因此，答案为C。
C
变式训练　将一棵有1000个节点的完全二叉树从上到下，从左到右依次进行编号，根节点的编号为1，则编号为35的节点的右孩子的编号为(　　)
A.36 B.70 C.71 D.72
解析　本题主要考查的是完全二叉树的特点。在一棵的完全二叉树中，若父节点的编号为n，则它的左孩子的编号为2*n，右孩子的编号为2*n＋1，则编号为35的节点的右孩子的编号为71，因此答案为C。
C
随堂检测
3
1.下列数据结构中属于非线性结构的是(　　)
D
解析　树是一种非线性的数据结构，用于描述有分支和层次的数据集合。
A.链表 B.队列 C.栈 D.树
A.父节点 B.叶节点 C.根节点 D.空节点
C
解析　在树中，没有前驱节点的节点称为根节点，也称开始节点，因此答案为C。
3.如果节点A有3个兄弟节点，而且B是A的父节点，那么B的度是(　　)
B
解析　节点B是节点A和三个兄弟节点的父节点，也就是节点B有4个孩子节点，即节点B的度数为4，因此选B。
A.3 B.4 C.5 D.6
4.按照二叉数的定义，具有3个节点的二叉树形态有(　　)
C
解析　具有3个节点的二叉树有以下五种：
A.3种 B.4种 C.5种 D.6种
因此，答案为C。
5.若树的根的高度为1，则具有120个节点的完全二叉树的高度为(　　)
A.5 B.6 C.7 D.8
C
解析　高度为h的满二叉树的节点数为2h－1个，完全二叉树是将满二叉树最后一层的叶子节点进行删除得到的，高度为7的满二叉树的节点数为27－1个(127个节点)，可知该完全二叉树的高度为7，因此答案为C。
6.有如图所示的二叉树，圈中数字表示叶子节点的权。则该二叉树的带权路径长度WPL为(　　)
C
解析　本题主要考查的是二叉树的带权路径长度WPL的计算。WPL＝5*1＋6*2＋(8＋7)*3＝62，因此答案为C。
A.26 B.41
C.62 D.88
4
巩固与提升
基础巩固
能力提升
1.树最适合用来表示下面哪种类型的数据(　　)
D
解析　树能很好地描述有分支和层次特性的数据集合。
A.有序数据元素
B.无序数据元素
C.元素之间无联系的数据
D.元素之间具有分支层次关系的数据
A.父节点 B.叶节点 C.根节点 D.空节点
B
解析　在树中，没有子节点的节点称为叶节点，也称终端节点，因此答案为B。
3.具有3个节点的二叉树形态有5种，可推测出具有4个节点的二叉树形态共有(　　)
B
解析　可先画出3个节点的二叉树形态，然后求得二叉树的形态总数，具有4个节点的二叉树形态共有14种，因此，答案为B。
A.13种 B.14种 C.15种 D.16种
4.下列有关二叉树的说法，正确的是(　　)
B
解析　本题主要考查的是二叉树的度。二叉树的度为最大节点的度，二叉树中的节点的度最大为2，最小为0(叶节点)，因此正确答案为B。
A.二叉树的度为2
B.一棵二叉树的度可以小于2
C.至少有一个节点的度为2
D.任一节点的度均为2
5.一棵度为3，深度为4的树的节点个数至多为(　　)
C
解析　度为3的树，即每个分支节点最多有3个孩子节点，按照每个分支节点均有3个孩子节点，即每一层都是上一层节点数的3倍，则前4层的节点数应分别为1，3，9，27，共40个节点，答案为C。
A.31 B.32 C.40 D.42
6.在一棵度为2的树中，度为2的节点数为15，度为1的节点数为30，则叶子节点(度为0的节点)的个数为(　　)
A.15 B.16 C.17 D.47
B
解析　设度为0的节点数为n0，总节点数为n，则由树中总结点数、不同度数的节点个数及总边数之间的关系可以列出以下两个等式：(1)n＝n0＋n1＋n2＝n0＋30＋15；(2)n－1＝1*n1＋2*n2＝30＋30，可得n＝61，n0＝16，答案为B。
7.一棵高度为h的满二叉树，从上到下，同层从左到右的次序从1开始连续编号，若某子节点的右孩子的编号为x(x>1)，则该子节点的编号为(　　)
A.2*x＋1 B.2*x－1 C.x/2 D.x∥2
D
解析　在一棵满二叉树中，若父节点的编号为x，则它的左孩子的节点编号为2*x，右孩子的节点编号为2*x＋1，同理，若某子节点的右孩子的编号为x，则该子节点的编号为x∥2，因此答案为D。
8.已知一棵二叉树有13个节点，树中度为1的节点数为2，则该树度为2的节点数为(　　)
A.4 B.5 C.6 D.11
B
解析　本题考查二叉树性质。根据二叉树的性质，n0＝n2＋1，n＝n0＋n1＋n2，可以推出n2＝5。
9.下列关于二叉树的说法中，正确的是(　　)
D
解析　满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树，因此A选项错误；二叉树的度是指二叉树中最大节点的度，而二叉树的深度是指二叉树中节点的最大层数，因此B选项错误；二叉树的子树有左右之分，且左右子树的次序不能颠倒，因此C选项错误；二叉树中所有节点的度都小于或等于2，因此答案为D。
A.完全二叉树一定是满二叉树
B.二叉树的深度是指二叉树中最大节点的度
C.二叉树的子树没有左右之分，左右子树的次序可以交换
D.二叉树中所有节点的度都小于或等于2
10.有一棵树如图所示，回答下面的问题：
答案　①A　②9　③2　④IJ　⑤A　⑥5　⑦4
解析　参照树的概念和特性解答。
这棵树的根节点是①________，叶子节点个数是②________；节点E的度是③________，节点E的孩子节点是④________；节点E的父节点是⑤________；这颗树的度为⑥________；这棵树的深度是⑦______。
11.根节点的深度为1，则深度为5的完全二叉树中节点数最少为(　　)
C
解析　本题主要考查的是完全二叉树的深度。它是由一个深度为4的满二叉树的基础上得到的，要节点数最少，则第5层上只有一个节点，因此最少为16个节点，答案为C。
A.9 B.15 C.16 D.31
12.在一棵满二叉树中，若有N个叶节点，则该满二叉树的节点总数为(　　)
C
解析　满二叉树除了叶节点外，其他节点均有2个节点，在二叉树中，叶子节点比度为2的节点多1个，因此，当叶节点个数为N时，它的节点总数为N＋N－1＝2N－1个，因此答案为C。
A.N个 B.2N个 C.2N－1个 D.2N＋1个
B
13.完全二叉树共有2*n－1个节点，则它的叶节点数为(　　)
解析　完全二叉树共有2*n－1个节点，该完全二叉树可能就是一棵满二叉树，或者是将满二叉树的最下面一层中的偶数个叶节点删除得到的，因此它的叶节点数为n，答案为B。
A.n－1 B.n C.2*n D.2*n－1
14.假设完全二叉树的树根为第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。课时1　树与二叉树
课时目标
1.了解二叉树的基本概念和特点，并能结合实例进行分析。2.了解满二叉树和完全二叉树的特点，并能正确区分满二叉树和完全二叉树。3.理解二叉树的性质，并能利用二叉树的性质解决实际问题。
1.树(Tree)的几个基本概念
树是一种________的数据结构，用它能很好地描述有分支和层次特性的数据集合。
(1)树可以描述为由n(n≥0)个节点构成的一个________________以及在该集合上定义的一种________关系。
(2)节点(Node)：集合中的元素称为树的节点，________的树称为空树。
根节点：在树形结构中，____________的节点称为根节点(Root)，又称为开始节点。
父节点、孩子节点：在树形结构中，对于两个以边直接连接的节点，上端节点称为下端节点的父节点(Parent)，下端节点为孩子节点(Child)，简称为子节点。
(3)子树：树中某个节点下面所有节点所构成的树称为该节点的子树。
(4)边：树的两个节点之间如果有一条边连接，那么称为这两个节点之间存在一条边。
对于一棵有n个节点的树，它有________条边。
(5)度(Degree)
节点的度：树的一个节点所拥有的____________称为该节点的度。
树的度：____________________称为树的度。
节点的度和树的度是指宽度。
(6)叶子：度为________的节点称为叶子节点(Leaf)，又称为终端节点。
(7)树的深度(高度)：树中节点的层数(Level)从根开始计算，根的层数为__________________，其余节点的层数等于父节点的层数加1。树中节点的__________________称为树的高度或深度(Depth)。
2.二叉树
(1)二叉树的定义
二叉树是指除根节点外的所有节点可分为两个互不相交的有限集合，分别称为左子树和右子树，左子树和右子树也是二叉树。
二叉树的子树有左右之分，且左右子树的次序不能颠倒。
(2)二叉树的高度(深度)
二叉树中节点的____________称为二叉树的深度或高度。
(3)二叉树的五种形态
3.特殊的二叉树
(1)满二叉树
符合满二叉树的两个条件为：
①每个节点的度数均____________；
②所有叶子节点都在________。
(2)完全二叉树
符合完全二叉树的两个条件为：
①只有____________中的节点度数小于2；
②最下一层的叶子节点都依次排列在该层________位置。
(3)哈夫曼树
①哈夫曼树又称为最优二叉树。
②树的带权路径长度(WPL)的计算公式为：WPL＝Wi×Pi，其中，n为树中叶子节点的个数，Wi和Pi分别是第i个叶子节点的权值和从根节点到该节点的路径长度。
③最优二叉树是指在具有n个带权叶子结点的所有二叉树中，带权路径长度(WPL)最小的二叉树。
正确区分满二叉树和完全二叉树的方法：
(1)满二叉树的判断方法：指叶子节点都在最下面一层上，除叶节点外其他每个节点的度数为2。
(2)完全二叉树的判断方法：可将一棵二叉树先变为满二叉树，然后从上到下，同层从左到右的次序从1开始连续编号，如果能按从大到小的顺序连续删除该满二叉树的若干节点后得到该二叉树，则该二叉树为完全二叉树。
4.二叉树的性质
(1)二叉树的第k层上最多有______________(k≥1)个节点。
(2)深度为k的二叉树最多有________(k≥1)个节点。
(3)在任意一棵二叉树中，叶子节点数比度为2的节点数________。
例1 有一棵树，如图所示。则该树中节点a的度和树的度分别为(　　)
A.3，3 B.4，3 C.3，4 D.3，10
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　有一棵树，如图所示。则该树深度为(　　)
A.3 B.4 C.5 D.6
例2 若树的根的高度为1，则二叉树的第p层上的节点数最多为(　　)
A.2p－1个 B.2p－1 个
C.2p 个 D.2p－1个
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　若树的根的高度为1，则高度为h的二叉树中节点数最多为(　　)
A.2h－1个 B.2h－1 个 C.2h－1个 D.2h＋1个
例3 有一棵深度为h的满二叉树，共有n个节点，其中叶子节点为m个，则下列等式成立的是(　　)
A.n＝m＋h B.m＝2h－1＋1 C.2m＝n＋1 D.n＝2h＋1
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　将一棵有1000个节点的完全二叉树从上到下，从左到右依次进行编号，根节点的编号为1，则编号为35的节点的右孩子的编号为(　　)
A.36 B.70 C.71 D.72
1.下列数据结构中属于非线性结构的是(　　)
A.链表 B.队列 C.栈 D.树
2.在一棵树中，没有前驱节点的节点是(　　)
A.父节点 B.叶节点 C.根节点 D.空节点
3.如果节点A有3个兄弟节点，而且B是A的父节点，那么B的度是(　　)
A.3 B.4 C.5 D.6
4.按照二叉数的定义，具有3个节点的二叉树形态有(　　)
A.3种 B.4种 C.5种 D.6种
5.若树的根的高度为1，则具有120个节点的完全二叉树的高度为(　　)
A.5 B.6 C.7 D.8
6.有如图所示的二叉树，圈中数字表示叶子节点的权。则该二叉树的带权路径长度WPL为(　　)
A.26 B.41 C.62 D.88
课时1　树与二叉树
知识梳理
1.非线性　(1)有限集合　节点　(2)n＝0　没有前驱　(4)n－1　(5)子树个数　节点的度的最大值　(6)0　(7)1　最大层数
2.(2)最大层数　(3)②单点树　④只有根和右子树　⑤左右子树均非空
3.(1)①为2或为0　②同一层　(2)①最下二层　②最左边
4.(1)2k－1　(2)2k－1　(3)多1个
例题精析
例1　C　[本题主要考查的是节点的度和树的度。节点a有三个子节点b、c、d，因此节点a的度为3；树的度是指宽度，即树中节点的度的最大值，树中节点g的度最大，节点g的度为4，因此树的度为4，答案为C。]
变式训练　C　[本题主要考查的是树的深度。树中节点的最大层数称为树的高度或深度，根的层数为1，因此树的深度为5，答案为C。]
例2　B　[本题主要考查的是二叉树的性质。当二叉树为满二叉树时，每一层上的节点数最多，第p层上的节点数为2p－1个，因此答案为B。]
变式训练　C　[高度为h的满二叉树的节点数为2h－1个，因此答案为C。]
例3　C　[本题主要考查的是满二叉树的性质。深度为h的满二叉树的节点总数为2h－1，因此n＝2h－1；在满二叉树中，叶子节点数为2h－1，因此，m＝2h－1；在满二叉树中，只有度为2的节点和度为0的叶节点，且叶子节点比度为2的节点数多1个，度为2的节点数为n－m，可得到n－m＋1＝m，即2m＝n＋1，因此，答案为C。]
变式训练　C　[本题主要考查的是完全二叉树的特点。在一棵的完全二叉树中，若父节点的编号为n，则它的左孩子的编号为2*n，右孩子的编号为2*n＋1，则编号为35的节点的右孩子的编号为71，因此答案为C。]
随堂检测
1.D　[树是一种非线性的数据结构，用于描述有分支和层次的数据集合。]
2.C　[在树中，没有前驱节点的节点称为根节点，也称开始节点，因此答案为C。]
3.B　[节点B是节点A和三个兄弟节点的父节点，也就是节点B有4个孩子节点，即节点B的度数为4，因此选B。]
4.C　[具有3个节点的二叉树有以下五种：
因此，答案为C。]
5.C　[高度为h的满二叉树的节点数为2h－1个，完全二叉树是将满二叉树最后一层的叶子节点进行删除得到的，高度为7的满二叉树的节点数为27－1个(127个节点)，可知该完全二叉树的高度为7，因此答案为C。]
6.C　[本题主要考查的是二叉树的带权路径长度WPL的计算。WPL＝5*1＋6*2＋(8＋7)*3＝62，因此答案为C。]

展开更多......

收起↑