(
课件网) 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。 ②最下一层的叶子节点都依次 ... ...
