4.1 树与二叉树（教学课件）信息技术浙教版2019选择性必修1

第1节 树与二叉树（1课时） 第4章 树 浙教版（2019） 选修一 树 01 二叉树 02 学习目录 了解树、子树、树的度、树的深度等概念。 01 通过具体任务的实践活动，体验用树型结构描述生活中蕴含树型结构的组织关系。 03 了解二叉树、满二叉树、完全二叉树等概念。 02 学习目标 PART 01 树 新课导入 树？ 逻辑上的树 生活中的树 新课导入 常见的 树形结构 树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合。 树 一 树形结构在现实世界中广泛存在 公司内部管理的 组织关系图 赋值语句的语法树 数据库层次结构图 树 一 树（Tree）可以描述为由n（n≥0）个节点（Node）构成的一个有限集合以及在该集合上定义的一种节点关系。 A C D F B G H E J K L M I 第1层 第2层 第3层 第4层 树的示例 树 一 树 节点:树的元素【n=0为空树】 子树:树中某个节点下面的所有节点所构成的树 两个节点之间存在一条边 ❆一棵具有n个节点的树，它有n-1条边。 子树 第1层 第3层 第4层 第2层 ※树中共有13个节点、12条边。 ※节点B、G、H构成了节点A的一棵子树。 树 一 树 节点的度：某节点拥有的子树个数 树的度：最大的节点的度 第1层 第3层 第4层 第2层 ※节点A的度为5， ※节点B的度为2， ※节点I的度为3， 因此树的度为5。 线性表( 特殊的树)——度为1 节点的度和树的度共同体现了树的宽度(节点的分支数和树的发散程度)。 树的示例 树 一 第1层 第3层 第4层 第2层 树的示例 根节点（开始节点）：没有前驱的节点 叶子节点（终端节点）：度为0 分支节点（非终端节点）：度不为0 内部节点：除根节点之外的分支节点 父节点（双亲节点）：以边相连的上端节点 孩子节点：以边相连的下端节点 兄弟节点：拥有同一父节点 父节点 根节点 叶子节点 树 一 第1层 第3层 第4层 第2层 树的高度/深度=4 只需知道数据之间相互链接的顺序 树中节点层数：根节点层数为1，其余节点层数等于其父节点的层数加1 树的高度/深度=最大层数 树 一 1 线性结构： 必存在着唯一的一个“第一个元素”和唯一的一个“最后的元素”； 除第一个元素以外，其他数据元素均有唯一的“前驱”，除最后元素以外，其他数据元素均有唯一的“后继”。 2 树形结构（拥有多个节点）：非线性结构， 根节点（无前驱，有后继）， 叶子节点（存在多个，没有后继，只有前驱），其余的节点都只有一个直接前驱和多个直接后继。 树 一 拓展链接 图（Graph） 图状结构是一种比线性结构和树形结构更为复杂的非线性结构，广泛应用于计算机网络、通信工程等诸多领域。在线性表中，一个数据元素只和它的前驱和后继元素有关系。在树中，一个节点只和它的父节点和孩子节点有关系。而在图中，每个顶点都有可能和其他任意顶点有关系，这就使得图的存储和运算比前两种数据结构更加复杂。 无向图 有向图 连通图 非连通图 节点 关系图 树 一 只需知道数据之间相互链接的顺序 探讨与讨论 1.诸葛亮家族的部分家谱如图所示。和家谱图结构相似的数据结构是( ) A A.树 B.栈 C.队列 D.链表 二叉树 二 树的形态有很多，在实际的使用过程中，需要对树的形态进一步地进行约束和简化， 以便于设计和操作。二叉树是树形结构的一个重要类型，在实际应用中，许多问题抽象出 来的数据结构往往就是二叉树的形式。 树 二 叉 二叉树 二 甲方事先在纸上写出一个100以内的正整数，让乙方猜，乙方每猜一次，甲方都会告诉乙方“猜大了”或是“猜小了”，直至猜出正确结果。乙方如果采取“折半”的策略进行猜数字，就一定能够在7次以内猜对结果。 猜数字游戏 猜数字过程的抽象形态 二叉树 二 每个节点为乙方所猜的数字，每条边为实际数字与所猜数字 之间的大小关系，图中仅呈现前4次的猜数字情况。 二叉树 二 二叉树的概念 二叉树（Binary Tree）是一个具有n（n≥0）个节点的有限集合。 （1） 当n=0时，二叉树是一棵空树; （2） 当n≠0时，则是一棵由根节点和两棵互不相交的、分别称作这个根节点的左子树和右子树组成的二叉树，由于左、右子树也是二叉树，因此子树也可以是空树。 二叉树 二 二叉树的概念 二叉树的重要特征：它的所有节点的度都小于或者等于2。 五种不同形态的二叉树 二叉树的示例 从左到右分别是： ①空二叉树； ②只有根节点的单点树； ③只有根节点和左子树； ④只有根节点和右子树； ⑤左右子树均非空。 二叉树 二 满二叉树 完全二叉树 ①每个节点的度数为2(具有两个非空子树)，或者度数为0(叶子节点)。 ②所有叶子节点都在同一层。 ①至多只有最下两层中的节点度数小于2。 ②最下一层的叶子节点都依次排列在该层最左边位置。 二叉树 一 只需知道数据之间相互链接的顺序 探讨与讨论 1.满二叉树和完全二叉树有什么区别？ ①满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。 ②空二叉树和只有根节点的二叉树既是满二叉树，也是完全二叉树。 ③完全二叉树可看作是在满二叉树最下一层，从右向左去掉若干个节点后得到。 ④完全二叉树中一个节点如果没有左子节点，就一定没有右子节点。 二叉树 二 二叉树的性质 01 02 二叉树的第k层上最多有2k–1（k≥1）个节点。 ※当k=1时，只有1（20=1）个根节点； ※当k=2时，由于节点的度最大为2，因此，第2层的节点数最多有2（21=2）个节点。依次推出，第k层上最多有2k–1个节点。 深度为k的二叉树最多有2k–1（k≥1）个节点。 ※第1层至第k层上的最大节点数相加的结果是：20+21+…+2k–1=2k–1。 ※因此2k–1是深度为k的二叉树的最多节点总数。 二叉树 二 03 在任意一棵二叉树中，若度为2的节点数量为，叶子节点（度为0的节点）数为，则。 ※度为0，1和2的节点数分别是和，总的节点数 ① ※n个节点的二叉树的总边数为n-1条。 ※二叉树的总边数与度之间的关系: n-1= 2 ② 联立等式① ②，可得 甲、乙两棵二叉树 ※在甲树上，度为2的节点数是1，度为1的节点数是1，叶子节点数为2； ※在乙树上，度为2的节点数是2，度为1的节点数是1，叶子节点数为3。 二叉树 二 拓展链接 哈夫曼树 哈夫曼树又称最优二叉树，它的相关概念如下。 路径:树中两个节点之间所经过的分支,称为它们之间的路径。 路径长度:一条路径上的分支数,称为该路径的长度。 节点的权:给二叉树中的节点赋一个数,该数称为该节点的权。 节点带权路径长度:从根节点到一个节点的路径长度与该节点的权值的乘积，称为该节点的带权路径长度。 二叉树 二 拓展链接 树的带权路径长度:一棵树中所有叶子节点的带权路径长度之和，称为该树的带权路径长度WPL； WPL的公式如下: 【n=叶子节点数，=第i个叶子节点的权值;=从根节点到该路径的长度。】 最优二叉树:带权路径长度WPL最小的二叉树。在最优二叉树中，权值较大的节点离根较近。 如下所示的三棵二叉树，叶子节点的权值都分别为2，4，5，8。 三棵二叉树的WPL分别为: ①WPL=2x2+4x2+5x2+8x2=38 ②WPL=5x3+8x3+4x2+2x1=49 ③WPL=2x3+4x3+5x2+8x1=36 由此可见，第三棵二叉树是最优二叉树。 二叉树 二 只需知道数据之间相互链接的顺序 探讨与讨论 1.已知一棵完全二叉树共有200个节点，下列说法正确的 是( ) A.该完全二叉树的高度为7 B.该完全二叉树有99个叶子节点 C.该完全二叉树有100个度为2的节点 D.该完全二叉树有1个度为1的节点 D 课堂练习 三 只需知道数据之间相互链接的顺序 探讨与讨论 1.某二叉树如图所示，下列说法正确的是( ) A.该二叉树是完全二叉树 B.该二叉树共有4个叶子节点 C.节点D、F都是节点B的孩子节点 D.该二叉树后序遍历的结果为DEBFCA D D E A B C F 课堂练习 三 只需知道数据之间相互链接的顺序 探讨与讨论 2.某二叉树的前序遍历结果为ABC,若该二叉树不是满二叉树，则其后序遍历结果为( ) A.ABC B.BCA C.CBA D.CAB C 3.已知某二叉树的前序遍历为“ABCDEF"中序遍历为“BCAEFD”，则该二叉树的后序遍历为( ) A.CBFEDA B.BCFEDA C.CBEFDA D.BCEFD A 树 四 小 结 一、树 1. 树的概念 2. 树的示例 二、二叉树 1.二叉树的概念 2. 二叉树的性质 3.拓展链接：哈夫曼树 谢谢观看 第1节 树 浙教版（2019） 选修一 $$