4.1树与二叉树 课件-2021-2022学年浙教版（2019）高中信息技术选修1

4.1 树与二叉树 总经理 技术部 财务部 人事部 零售部 采购部 项目部 运营部 管理部 售后部 门店一 门店二 门店三 树形结构在现实世界中广泛存在，如上图所示的公司内部 管理的组织关系图就可以用树形结构来表示。树在计算机 领域中也有广泛应用，在编译系统中，用树表示源程序的 语法结构。在数据库系统中，树形结构是数据库层次模型 的基础，也是各种索引和目录的主要组织形式。 树（Tree）可以描述为由n(n>=0)个节点（node）构成的 一个有限集合以及在该集合上定义的一种节点关系。集合中 的元素称为树的节点，n=0的树称为空树；树中某个节点下面 的所有节点所构成的树称为该节点的子树。 A B G H C D E F I J K L M 子树 节点的度：树的一个节点所拥有的子树个数称为该节点的度。 树的度：最大节点的度称为树的度。 节点的度和树的度共同体现了树的宽度，也就是体现了节点 的分支数和树的发散程度。 线性表其实是一种特殊的树状结构，它的度为1。 树的两个节点之间如果有一条边连接，那么称这两个节点 之间存在一条边；对于一棵具有n个节点的树，它有n-1条边。 A B G H C D E F I J K L M A节点的度为___________,B节点的度为__________， I节点的度为__________。 该树的度为____________。 5 2 3 5 该树共有____________个节点、________条边。 13 12 在树形结构中，没有前驱的节点称为根节点（Root）， 又称为开始节点。度为0的节点称为叶子节点（Leaf），它 又称为终端节点。树中度不为0的节点称为分支节点或者称 为非终端节点，除根节点外的分支节点统称为内部节点。 在上图中，节点A是根节点，节点G、H、C、D、K、L、M、 J、F都是叶子节点。 在树形结构中，对于两个以边直接连接的节点，上端节点 称为下端节点的父节点或双亲节点（Parent）。相应地， 下端节点称为上端节点的孩子节点（Child）。 A B G H C D E F I J K L M 节点K、L、M都是节点I的孩子节点 节点B是节点G、H的父节点 节点G、H是兄弟节点 树中节点的层数（Level）从根开始计算，根的层数为1， 其余节点的层数等于其父节点的层数加1。树中节点的最大 层数称为树的高度或深度