资源简介

(共24张PPT)
4
树
第四章
选择性必修1《数据与数据结构》
第四章 树
4.1 树与二叉树
4.1.1 树
4 . 1
树与二叉树
公司内部管理的组织大系图
树形结构
公司内部管理的组织
编译系统中，源程序的语法结构
在数据库系统中，树形结构是数据库层次模型的基础
4.1.1 树
4 . 1
树与二叉树
树(Tree）可以描述为由n (n≥0)个节点(Node)构成的一个有限集合+节点关系。
节点：树的元素【n=0为空树】；
子树：树中某个节点下面的所有节点所构成的树；
两个节点之间存在一条边；
一棵具有n个节点的树，它有n-1条边。
树中共有13个节点、12条边
节点B、G、H构成了节点A的一棵子树。
子 树
4.1.1 树
节点的度：某节点拥有的子树个数
树的度：最大的节点的度
节点A的度为5，
节点B的度为2，
节点I的度为3，
因此树的度为5。
节点的度和树的度共同体现了树的宽度(节点的分支数和树的发散程度)。
线性表( 特殊的树)——度为1
4.1.1 树
根节点（开始节点）：没有前驱的节点
叶子节点（终端节点）：度为0
分支节点（非终端节点）：度不为0
内部节点：除根节点之外的分支节点
父节点（双亲节点）：以边相连的上端节点
孩子节点：以边相连的下端节点
兄弟节点：拥有同一父节点
根节点
叶子节点
父节点
4.1.1 树
4.1.1 树
树中节点层数：根节点层数为1，其余节点层数等于其父节点的层数加1
树的高度/深度=最大层数
树的高度/深度=4
4.1.1 树
树形结构（拥有多个节点）：非线性结构，
根节点（无前驱，有后继），
叶子节点（存在多个，没有后继，只有前驱）， 其余的节点都只有一个直接前驱和多个直接后继。
线性结构：
必存在着唯一的一个“第一个元素”和唯一的一个“最后的元素”;
除第一个元素以外，其他数据元素均有唯一的“前驱”，除最后元素以外，其他数据元素均有唯一的“后继”。
4.1.1 树
拓展链接
图状结构是一种比线性结构和树形结构更为复杂的非线性结构，广泛应用于计算机网络、通信工程等诸多领域。在线性表中，一个数据元素只和它的前驱和后继元素有关系。在树中，一个节点只和它的父节点和孩子节点有关系。而在图中，每个顶点都有可能和其他任意顶点有关系，这就使得图的存储和运算比前两种数据结构更加复杂。图中节点的关系既可以是单向的，也可以是双向的，有无向图和有向图之分，又有连通图和非连通图之别，如图所示。
1.如何管理计算机中的照片,使得浏览起来更加方便
2.若干个家庭一起组织自助游，准备阶段需要考虑旅游路线的规划、食宿安排以及旅途中各项娱乐活动的人员组队等问题。如何用学过的数据结构知识来更好地帮助制订相关计划
4.1.1 树
问题与讨论
《必修1》· 计算机一般采用树形目录结构来管理文件
4.1.2 二叉树
猜数字游戏：甲方事先在纸上写出一个100以内的正整数，让乙方猜，乙方每猜一次，甲方都会告诉乙方“猜大了”或是“猜小了”，直至猜出正确结果。
乙方如果采取“折半”的策略进行猜数字，就一定能够在7次以内猜对结果。
二叉树( Binary Tree)是一个具有n (n≥0)个节点的有限集合。
当n=0时，二叉树是一棵空树;
当n≠0时，则是一棵由根节点和两棵互不相交的、分别称作这个根节点的左子树和右子树组成的二叉树，由于左、右子树也是二叉树，因此子树也可以是空树。
二叉树的重要特征：它的所有节点的度都小于或者等于2
二叉树的概念
①空二叉树;
②只有根节点的单点树:
③只有根节点和左子树;
④只有根节点和右子树;
⑤左右子树均非空。
二叉树的5种形态
(1）满二叉树
①每个节点的度数为2(具有两个非空子树)，或者度数为0(叶子节点)。
②所有叶子节点都在同一层。
(2）完全二叉树
①至多只有最下两层中的节点度数小于2。
②最下一层的叶子节点都依次排列在该层最左边位置。
满二叉树VS完全二叉树
满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。
空二叉树和只有根节点的二叉树既是满二叉树，也是完全二叉树。
完全二叉树可看作是在满二叉树最下一层，从右向左去掉若干个节点后得到。
完全二叉树中一个节点如果没有左子节点，就一定没有右子节点。
补充！
二叉树的概念
①二叉树的第k层上最多有(k≥1 )个节点。
当k=1时，只有1个根节点;【1】
当k=2时，由于节点的度最大为2，因此，第2层的节点数最多有2个节点；【2】
依次推出，…… 第k层上最多有【2】个节点。
②深度为k的二叉树最多有-1(k≥1)个节点。
第1层至第m层上的最大节点数相加的结果是:
因此是深度为k的二叉树的最多节点总数。【满二叉树】
二叉树的性质
③在任意一棵二叉树中，若度为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最小的二叉树。在最优二叉树中，权值较大的节点离根较近。
如图4.1.12所示的三棵二叉树，叶子节点的权值都分别为2，4，5，8。
从数据的组织处理效率来看，二叉树的本质上是对数组和链表的一种折中处理，如何看待这种说法？
问题与讨论
树与二叉树
树与二叉树
？ 思考与练习
1.试着用树结构来描述自己家族成员的组成情况。
2.请画出包含4个节点的所有形态的二叉树。
3.已知某完全二叉树有200个节点，求出该二叉树的高度。
4.假设某二叉树包含的节点数据分别为:1，5，8，3，10。请完成下列任务:
(1)画出两棵高度最大的二叉树。
(2）画出两棵完全二叉树，要求每个双亲节点的值大于其孩子节点的值。
树的概念
二叉树的概念
满二叉树、完全二叉树
二叉树的性质
课堂小结
学习评价
对自己和同伴的表现进行客观的评价，并思考后续完善的方向。（5=优秀，4=超出一般水平，3=满意，2=有待改进，1=不太理想）
评分项 自我评价 同学互评
能从新课导入中的感知生活中蕴含树型结构的实例 5 4 3 2 1 5 4 3 2 1
能理树、子树、树的度、树的深度等概念。 5 4 3 2 1 5 4 3 2 1
能自主学习教材，并归纳出线性结与树型结构在连接关系上的差异。 5 4 3 2 1 5 4 3 2 1
能理解二叉树、满二叉树、完全二叉树等概念。 5 4 3 2 1 5 4 3 2 1
能理解二叉树的三种性质 5 4 3 2 1 5 4 3 2 1
课堂作业
1.思考教材“问题与讨论”中的两个问题。
谢谢观看
制作者：XXXXXX

展开更多......

收起↑