4.1树与二叉树课件浙教版高中信息技术选修1

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。节点的度和树的度共同体现了树的宽度(节点的分支数和树的发散程度)。线性表(特殊的树)——度为14.1.1树根节点（开始节点）：没有前驱的节点叶子节点（终端节点）：度为0分支节点（非终端节点）：度不为0内部节点：除根节点之外的分支节点父节点（双亲节点）：以边相连的上端节点孩子节点：以边相连的下端节点兄弟节点：拥有同一父节点根节点叶子节点父节点4.1.1树4.1.1树树中节点层数：根节点层数为1，其余节点层数等于其父节点的层数加1树的高度/深度=最大层数树的高度/深度=44.1.1树树形结构（拥有多个节点）：非线性结构，

根节点（无前驱，有后继），

叶子节点（存在多个，没有后继，只有前驱），

其余的节点都只有一个直接前驱和多个直接后继。线性结构：

必存在着唯一的一个“第一个元素”和唯一的一个“最后的元素”;

除第一个元素以外，其他数据元素均有唯一的“前驱”，除最后元素以外，其他数据元素均有唯一的“后继”。4.1.1树拓展链接

图状结构是一种比线性结构和树形结构更为复杂的非线性结构，广泛应用于计算机网络、通信工程等诸多领域。在线性表中，一个数据元素只和它的前驱和后继元素有关系。在树中，一个节点只和它的父节点和孩子节点有关系。而在图中，每个顶点都有可能和其他任意顶点有关系，这就使得图的存储和运算比前两种数据结构更加复杂。图中节点的关系既可以是单向的，也可以是双向的，有无向图和有向图之分，又有连通图和非连通图之别，如图所示。1.如何管理计算机中的照片,使得浏览起来更加方便?2.若干个家庭一起组织自助游，准备阶段需要考虑旅游路线的规划、食宿安排以及旅途中各项娱乐活动的人员组队等问题。如何用学过的数据结构知识来更好地帮助制订相关计划?4.1.1树问题与讨论《必修1》·计算机一般采用树形目录结构来管理文件4.1.2二叉树猜数字游戏：甲方事先在纸上写出一个100以内的正整数，让乙方猜，乙方每猜一次，甲方都会告诉乙方“猜大了”或是“猜小了”，直至猜出正确结果。乙方如果采取“折半”的策略进行猜数字，就一定能够在7次以内猜对结果。二叉树(BinaryTree)是一个具有n(n≥0)个节点的有限集合。当n=0时，二叉树是一棵空树;当n≠0时，则是一棵由根节点和两棵互不相交的、分别称作这个根节点的左子树和右子树组成的二叉树，由于左、右子树也是二叉树，因此子树也可以是空树。

二叉树的重要特征：它的所有节点的度都小于或者等于2二叉树的概念①空二叉树;②只有根节点的单点树:③只有根节点和左子树;④只有根节点和右子树;⑤左右子树均非空。二叉树的5种形态(1）满二叉树①每个节点的度数为2(具有两个非空子树)，或者度数为0(叶子节点)。②所有叶子节点都在同一层。(2）完全二叉树①至多只有最下两层中的节点度数小于2。②最下一层的叶子节点都依次排列在该层最左边位置。满二叉树VS完全二叉树满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。空二叉树和只有根节点的二叉树既是满二叉树，也是完全二叉树。完全二叉树可看作是在满二叉树最下一层，从右向左去掉若干个节点后得到。完全二叉树中一个节点如果没有左子节点，就一定没有右子节点。补充！二叉树的概念

二叉树的性质

二叉树的性质甲、乙两棵二叉树在甲树上，度为2的节点数是1，度为1的节点数是1，叶子节点数为2；在乙树上，度为2的节点数是2，度为1的节点数是1，叶子节点数为3。哈夫曼树拓展链接哈夫曼树又称最优二叉树，它的相关概念如下。路径:树中两个节点之间所经过的分支,称为它们之间的路径。路径长度:一条路径上的分支数,称为该路径的长度。节点的权:给二叉树中的节点赋一个数,该数称为该节点的权。节点带权路径长度:从根节点到一个节点的路径长度与该节点的权值的乘积，称为该节点的带权路径长度。哈夫曼树拓展链接

从数据的组织处理效率来看，二叉树的本质上是对数组和链表的一种折中处理，如何看待这种说法？问题与讨论树与二叉树树与二叉树？

思考与练习1.试着用树结构来描述自己家族成员的组成情况。2.请画出包含4个节点的所有形态的二叉树。3.已知某完全二叉树有200个节点，求出该二叉树的高度。4.假设某二叉树包含的节点数据分别为:1，5，8，3，10。请完成下列任务:(1)画出两棵高度最大的二叉树。(2）画出两棵完全二叉树，要求每个双亲节点的值大于其孩子节点的值。树的概念二叉树的概念满二叉树、完全二叉树二叉树的性质课堂小结学习评价对自己和同伴的表现进行客观的评价，并思考后续完善的方向。（5=优秀，4=超出一般水平，3=满意，2=有待改进，1=不太理想）评分项自我评价同学互评能从新课导入中的感知生活中蕴含树型结构的实例5432154321能理树、子树、树的度、树的深度等概念。5432154321能自主学习教材，并归纳出线性结与树型结构在连接关系上的差异。54321543