6.1.2 若开术语 根 即根结点（没有前驱） 即终端结点设有后继) 森林 指m棵不相交的树的集 合（例如删除A后的子树个数） 有序树 结点各子树从左至右有序，不能互换（左为第一） 无序树 结点各子树可互换位置。 双亲 即上层的那个结点（直接前驱 孩子 即下层结点的子树的根直接后继) 兄弟 同一双亲下的同层结点（孩子之间互称兄弟） 堂兄弟 即双亲位于同一层的结点（但并非同一双亲） 祖先 即从根到该结点所经分支的所有结点 子孙 即该结点下层子树中的任一结点 6
6 6.1.2 若干术语 ——即上层的那个结点(直接前驱) ——即下层结点的子树的根(直接后继) ——同一双亲下的同层结点（孩子之间互称兄弟） ——即双亲位于同一层的结点（但并非同一双亲） ——即从根到该结点所经分支的所有结点 ——即该结点下层子树中的任一结点 A B C E G I D F H J K L F 根 叶子 森林 有序树 无序树 ——即根结点(没有前驱) ——即终端结点(没有后继) ——指m棵不相交的树的集 合(例如删除A后的子树个数) 双亲 孩子 兄弟 堂兄弟 祖先 子孙 ——结点各子树从左至右有序，不能互换（左为第一） ——结点各子树可互换位置
结点 即树的数据元素 结点的度 结点挂接的子树数 (有几个直接后继就是几度，亦称次数” 结点的层次一从根到该结点的层数（根结点算第一层） 终端结点 即度为0的结点，即叶子 分支结点 即度不为0的结点（也称为内部结点） 树的度 所有结点度中的最大值(Max{各结点的度}) 树的深度 指所有结点中最大的层数(Max{各结点的层次) 或高度) 问：右上图中的结点数=13树的度=3树的深度=
7 ——即树的数据元素 ——结点挂接的子树数 结点 结点的度 结点的层次 终端结点 分支结点 树的度 树的深度 (或高度) A B C E G I D F H J K L F ——从根到该结点的层数（根结点算第一层） ——即度为0的结点，即叶子 ——即度不为0的结点（也称为内部结点） ——所有结点度中的最大值（Max{各结点的度}） ——指所有结点中最大的层数（Max{各结点的层次}） 问：右上图中的结点数＝13；树的度＝ 3；树的深度＝ 4 （有几个直接后继就是几度，亦称“次数”）
自学：树的抽象数据类型定义 (见教材P118- 119) ADT Treef 数据对象D:D是具有相同特性的数据元素的集合。 数据关系R:若D为空集，则称为空树；/允许=0 若D中仅含一个数据元素，则R为空集； 其他情况下的R存在二元关系： ①root唯一 /关于根的说明 ②D∩Dk=Φ /关于子树不相交的说明 ③ 。 /关于数据元素的说明 基本操作P:/至少有15个，如求树深，求某结点的双亲 ADT Tree
8 自学：树的抽象数据类型定义 （见教材P118- 119） ADT Tree{ 数据对象D: 数据关系R: 基本操作 P： }ADT Tree D是具有相同特性的数据元素的集合。 若D为空集，则称为空树；//允许n=0 若D中仅含一个数据元素，则R为空集； 其他情况下的R存在二元关系： ① root 唯一 //关于根的说明 ② Dj∩Dk= Φ //关于子树不相交的说明 ③ . //关于数据元素的说明 //至少有15个，如求树深，求某结点的双亲
6.1.3 树的逻辑结构 特点： 一对多(1：n),有多个直接后继（如家谱 树、目录树等等)，但只有一个根结点，且 子树之间互不相交。 6.1.4 树的存储结构 讨论1：树是非线性结构，该怎样存储？ 仍然有顺序存储、链式存储等方式。 9
9 6.1.3 树的逻辑结构 一对多（1:n），有多个直接后继（如家谱 树、目录树等等），但只有一个根结点，且 子树之间互不相交。 6.1.4 树的存储结构 讨论1：树是非线性结构，该怎样存储？ 特点： ——仍然有顺序存储、链式存储等方式