4.1 树与二叉树（教学课件）-高中《信息技术》选修1数据与数据结构同步高效课堂（浙教版）

第1节

树与二叉树（1课时）第4章树浙教版（2019）

选修一树01二叉树02

了解树、子树、树的度、树的深度等概念。01

通过具体任务的实践活动，体验用树型结构描述生活中蕴含树型结构的组织关系。03

了解二叉树、满二叉树、完全二叉树等概念。02PART01树新课导入树？逻辑上的树生活中的树新课导入常见的树形结构

树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合。

树一

树形结构在现实世界中广泛存在公司内部管理的组织关系图赋值语句的语法树数据库层次结构图

树一

树（Tree）可以描述为由n（n≥0）个节点（Node）构成的一个有限集合以及在该集合上定义的一种节点关系。ACDFBGHEJKLMI第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.诸葛亮家族的部分家谱如图所示。和家谱图结构相似的数据结构是(

)AA.树

B.栈

C.队列

D.链表

二叉树二

树的形态有很多，在实际的使用过程中，需要对树的形态进一步地进行约束和简化，以便于设计和操作。二叉树是树形结构的一个重要类型，在实际应用中，许多问题抽象出来的数据结构往往就是二叉树的形式。树二叉

二叉树二

甲方事先在纸上写出一个100以内的正整数，让乙方猜，乙方每猜一次，甲方都会告诉乙方“猜大了”或是“猜小了”，直至猜出正确结果。乙方如果采取“折半”的策略进行猜数字，就一定能够在7次以内猜对结果。猜数字游戏猜数字过程的抽象形态

二叉树二

每个节点为乙方所猜的数字，每条边为实际数字与所猜数字之间的大小关系，图中仅呈现前4次的猜数字情况。

二叉树二

二叉树的概念二叉树（BinaryTree）是一个具有n（n≥0）个节点的有限集合。（1）

当n=0时，二叉树是一棵空树;（2）

当n≠0时，则是一棵由根节点和两棵互不相交的、分别称作这个根节点的左子树和右子树组成的二叉树，由于左、右子树也是二叉树，因此子树也可以是空树。

二叉树二

二叉树的概念二叉树的重要特征：它的所有节点的度都小于或者等于2。五种不同形态的二叉树二叉树的示例从左到右分别是：①空二叉树；②只有根节点的单点树；③只有根节点和左子树；④只有根节点和右子树；⑤左右子树均非空。

二叉树二

满二叉树完全二叉树①每个节点的度数为2(具有两个非空子树)，或者度数为0(叶子节点)。②所有叶子节点都在同一层。①至多只有最下两层中的节点度数小于2。②最下一层的叶子节点都依次排列在该层最左边位置。

二叉树一

只需知道数据之间相互链接的顺序探讨与讨论1.满二叉树和完全二叉树有什么区别？①满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。②空二叉树和只有根节点的二叉树既是满二叉树，也是完全二叉树。③完全二叉树可看作是在满二叉树最下一层，从右向左去掉若干个节点后得到。④完全二叉树中一个节点如果没有左子节点，就一定没有右子节点。

二叉树二

二叉树的性质0102二叉树的第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的节点数是1，度为1的节点数是1，叶子节点数为2；

※在乙树上，度为2的节点数是2，度为1的节点数是1，叶子节点数为3。

二叉树二拓展链接哈夫曼树

哈夫曼树又称最优二叉树，它的相关概念如下。路径:树中两个节点之间所经过的分支,称为它们之间的路径。路径长度:一条路径上的分支数,称为该路径的长度。节点的权:给二叉树中的节点赋一个数,该数称为该节点的权。节点带权路径长度:从根节点到一个节点的路径长度与该节点的权值的乘积，称为该节点的带权路径长度。

二叉树二拓展链接

三棵二叉树的WPL分别为:①WPL=2x2+4x2+5x2+8x2=38②WPL=5x3+8x3+4x2+2x1=49③WPL=2x3+4x3+5x2+8x1=36由此可见，第三棵二叉树是最优二叉树。

二叉树二

只需知道数据之间相互链接的顺序探讨与讨论1.已知一棵完全二叉树共有200个节点，下列说法正确的是(

)A.该完全二叉树的高度为7B.该完全二叉树有99个叶子节点C.该完全二叉树有100个度为2的节点D.该完全二叉树有1个度为1的节点D课堂练习三只需知道数据之间相互链接的顺序探讨与讨论1.某二叉树如图所示，下列说法正确的是(

)A.该二叉树是完全二叉树B.该二叉树共有4个叶子节点C.节点D、F都是节点B的孩子节点D.该二叉树后序遍历的结果为DEBFCADDEABCF课堂练习三只需知道数据之间相互链接的顺序探讨与讨论2.某二叉树的前序遍历结果为ABC,若该二叉树不是满二叉树，则其后序遍历结果为()A.ABC B.BCA C.CBA D.CABC3.已知某二叉树的前序遍