第13课 树与二叉树-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参（浙教版2019）

第四章│树 第13课　 树与二叉树(见学生用书P102) ——4.1　树与二叉树，教材P98～105 1.理解树和二叉树的概念和特性。　2.理解二叉数的性质，并能利用二叉树的性质解决实际问题。 1． 树 树(Tree)是一种　非线性　的数据结构，用它能很好地描述有　分支和层次　特性的数据集合。 (1)树可以描述为由n(n≥0)个节点(Node)构成的一个　有限集合　以及在该集合上定义的一种　节点　关系。 (2)节点(Node)：集合中的元素称为树的　节点　。 ①n＝0的树称为　空树　。 ②根节点(Root)：在树形结构中，　没有　前驱的节点称为根节点，又称为开始节点。 ③叶子节点(Leaf)：度为　0　的节点称为叶子节点，也称为终端节点。 ④父节点(Parent)、孩子节点(Child)：在树形结构中，对于两个以边直接连接的节点，上端节点称为下端节点的父节点或双亲节点。相应地，下端节点称为上端节点的孩子节点。 (3)子树：树中某个节点下面的所有节点所构成的树称为该节点的　子树　。 (4)边：树的两个节点之间如果有一条边连接，那么称这两个节点之间存在一条边；对于一棵具 有n个节点的树，它有　n－1　条边。 (5)度(Degree)：树的一个节点所拥有的子树个数称为该节点的度；　最大的　节点的度称为树的度；线性表是度为1的特殊的树状结构。 (6)树的高度或深度(Depth)：树中节点的层数(Level)从根开始计算，根的层数为　1　，其余节点的层数等于其父节点的层数加1；树中节点的　最大层数　称为树的高度或深度。 2． 二叉树 二叉树是树形结构的一个重要类型，在实际应用中，许多问题抽象出来的数据结构就是二叉树的形式。 (1)二叉树的概念 ①二叉树是一个具有n(n≥0)个节点的有限集合，它的所有节点的度都　小于　或　等于　2。当n＝0时，二叉树是一棵　空树　；当n≠0时，它是一棵由根节点和两棵互不相交的、分别称作这个根节点的　左子树　和　右子树　组成的二叉树。二叉树的左右子树的次序不能颠倒。 ②二叉树的高度(深度)：二叉树中节点的最大层数。 ③二叉树的五种形态： ④满二叉树：每个节点的度数均为　2　或为　0　(没有度数为1的节点)；所有叶子节点都在同一层。 ⑤完全二叉树：至多只有最　下面两层　中的节点度数　小于　2，且最下面一层的叶子节点都依次排列在该层的　最左边　位置。例如： (2)二叉树的性质： ①二叉树的第i层上最多有2i－1(i≥1)个节点。 ②深度为h的二叉树最多有2h－1(h≥1)个节点。 ③在任意一棵二叉树中，若度为2的节点数为n2，叶子节点(度为0的节点)数为n0，则n0＝n2＋1。 ④具有n个节点的完全二叉树的深度为int(log2n)＋1。 ⑤若对一棵有n个节点的完全二叉树进行顺序编号(1<＝i<＝n)，那么，对于编号为i(i>＝1)的节点： 当i＝1时，该节点为根，它无双亲节点。 当i>1时，该节点的双亲节点的编号为i//2。 若2*i<＝n，则编号为2*i的节点是编号为i的左孩子。 若2*i＋1<＝n，则编号为2*i＋1的节点是编号为i的右孩子。 (3)哈夫曼树，又称最优二叉树。 ①路径：树中两个节点之间所经过的分支。 ②路径长度：一条路径上的分支数。 ③节点的权：给二叉数的节点赋一个数，该数称为节点的权。 ④节点带权路径长度：从根节点到一个节点的路径长度与该节点的权值的乘积。 ⑤树的带权路径长度(WPL)：一棵树中所有叶子节点的带权路径长度之和，WPL的公式如下： ⑥最优二叉树：在具有n个带权叶子节点的所有二叉树中，称带权路径长度(WPL)最小的二叉树为最优二叉树。 1． 二叉树性质举例 ①二叉树的第i层上最多有2i－1(i≥1)个节点。 例如，图中二叉树的第3层共有23－1个节点，即有4个节点。 ②深度为h的二叉树最多有2h－1(h≥1)个节点。 例如，图为满二叉树，深度为4，则其共有24－1个节点，即有15个节点。 ③在任意一棵二叉树中，若度为2的节点数为n2，叶子节点(度为0的节点)数为n0，则n0＝n2＋1。 例如，图中二叉树的叶子节点数为8，度为2的节点数则为7。 ④具有n个节点的完全二叉树的深度为int(log2n)＋1。 例如，图中二叉树共有15个节点，则如图所示的完全二叉树的深度为int(log215)＋1＝4。 　　树最适合用来表示的数据类型为(　D　) A．有序数据元素　　　　　　　　B．无序数据元素 C．元素之间无联系的数据 D．元素之间具有分支层次关系的数据 【解析】 树能很好地描述有分支和层次特性的数据集合，选项D正确。 　　如下图所示的一棵树，树的度和深度分别为(　B　) A．4 5　　　　　B．5 4　　　　　C．3 4　　　　　D．5 3 【解析】 树的一个节点所拥有的子树个数称为该节点的度，最大的节点的度称为树的度，当前节点A的度为5，度数最大即为树的度；树的层数从根开始计算，树的高度为最大层数，即为4。 变式1如下图所示的树是根据某组织关系图抽象得到的。下列关于该树的说法中，不正确的是(　C　) A．树中的节点B、G、H 构成了节点A 的一棵子树 B．该树的度为5，体现了节点的分支树和树的发散程度 C．树中的节点A、B、E 是该树形结构中的根节点 D．树中的节点G、H、C、D、K、L、M、J、F是该树形结构中的叶子节点 【解析】 在树形结构中，没有前驱的节点为根节点(Root)，该树形结构中节点A 是根节点，节点B和节点E 有前驱节点A，不是根节点，选项C错误。 　　一棵有n(n>0)个节点的二叉树， 其节点的度为0或2， 则此树的最大高度是(　A　) A．(n＋1)//2 B．n//2 C．(n－1)//2 D．log2n＋1 【解析】 二叉树由根节点和其子节点组成， 每个节点的度有如下可能：0， 1， 2， 根据题干， 该二叉树的节点的度都为0或2，即除根节点外，其每个节点都有一个兄弟节点。由于题目求的为该树的最大高度，即考虑极端情况下，每一层都只有一对兄弟节点， 此时除根节点外， 每一层都有两个节点， 则除第一层外， 节点数除2为除第一层外的层数。则假设根节点有一个兄弟节点后， 则用2整除， 则为层数。即(n＋1)//2。 变式1假设完全二叉树的树根为第1层，树中第10层有5个叶子节点， 则完全二叉树的节点个数最多为(　C　) A．2047 B．2048 C．2037 D．2038 【解析】 根据完全二叉树的性质可知，叶子节点最多只出现在最下面2层，此题考查的是最多节点数，那么该二叉树应有11层。前10层节点：210－1＝1023；第11层满节点数为：211－1＝1024。因为第10层有5个叶子节点， 所以第11层少10个节点， 故总结点数为：1023＋1024－10＝2037。故选项C正确。 　　有如图所示的二叉树，圈中数字表示叶子节点的权，则该二叉树的带权路径长度WPL为(　C　) A．26 B．41 C．62 D．88 【解析】 本题主要考查的是二叉树的带权路径长度WPL的计算。WPL＝5×1＋6×2＋(8＋7)×3＝62，故选项C正确。 |随|堂|检|测| 1．下列数据结构中属于非线性结构的是(　D　) A．链表 B．队列 C．栈 D．树 【解析】 树是一种非线性的数据结构，用于描述有分支和层次的数据集合，选项D正确。 2． 观察如图所示的树的示意图，该树的深度为(　C　) A．3 B．4 C．5 D．6 【解析】 树中节点的最大层数称为树的高度或深度，根的层数为1，因此树的深度为5，选项C正确。 3．由3个节点可以构造出的不同的二叉树的种数为(　D　) A．2 B．3 C．4 D．5 【解析】 3个节点可以构造5种不同的二叉树，如下图所示： 4．2023·浦江中学检测已知一棵完全二叉树的节点总数为12，则下列关于该二叉树的说法中，正确的是(　D　) A．该二叉树的度为12 B．该二叉树的层数为3 C．该二叉树的叶子节点数为5 D．该二叉树的最后一层的节点数为5 【解析】 选项A，二叉树的度最大为2，选项错误；选项B，该树的层数为int(log212)＋1＝4，选项错误；选项C，叶子节点数是6，选项错误；选项D，层数为4，但未满，前3 层有7 个节点，则第4 层有12－7＝5 个节点，选项正确。 学科网（北京）股份有限公司 $$