树形结构 ●树形结构是以分支关系来定义的层次结 构。在客观世界中树形结构广泛存在, 并应用于: 人类社会的族谱、家谱、行政区域划 分管理; 各种社会组织机构; 在计算机领域中,用树表示源程序的 语法结构; □上一页 在0S中,文件系统、目录等组织结构 也是用树来表示的。 「停止放映 第6页
下一页 上一页 停止放映 第 6 页 树形结构 ⚫ 树形结构是以分支关系来定义的层次结 构。在客观世界中树形结构广泛存在， 并应用于： –人类社会的族谱、家谱、行政区域划 分管理； –各种社会组织机构； –在计算机领域中，用树表示源程序的 语法结构； –在OS中，文件系统、目录等组织结构 也是用树来表示的
树的定义(逻辑结构) ●树是一种数据结构: Tree=(D, R) 其中: D是具有相同特性的数据元素的集合; R是D上逻辑关系的集合,且满足: 在D中存在唯一的称为根的数据元素,没 有前趋; D中其余数据元素都有且只有一个前趋; □上一页 D中所有元素,或有若干个互不相同的后 「停止放映 继(子树),或无后继(叶结点); 则称Tree为树。 第7页
下一页 上一页 停止放映 第 7 页 树的定义（逻辑结构） ⚫ 树是一种数据结构： Tree=（D，R） 其中： D 是具有相同特性的数据元素的集合； R 是D上逻辑关系的集合，且满足： –在D中存在唯一的称为根的数据元素，没 有前趋； –D中其余数据元素都有且只有一个前趋； –D中所有元素，或有若干个互不相同的后 继（子树），或无后继（叶结点）； 则称Tree为树
树的定义(递归结构) 树是一个或多个结点组成的有限集合 T,有一个特定结点称为根,其余结 点分为m(m0)个互不相交的集合 1,T2,…,Tm。每个集合又是一棵 树,被称为这个根的子树。 树是一种递归结构,可以包含一个结 □上一页 点,该结点包含不相交的树的指针 「停止放映 (即子树)。 第8页
下一页 上一页 停止放映 第 8 页 树的定义（递归结构） ⚫ 树是一个或多个结点组成的有限集合 T，有一个特定结点称为根，其余结 点分为m（m0）个互不相交的集合 T1，T2，…,Tm。每个集合又是一棵 树，被称为这个根的子树。 ⚫ 树是一种递归结构，可以包含一个结 点，该结点包含不相交的树的指针 （即子树）
树结构举例 书目录 目录树 树结构 C1(章) BOOK Q S1.1(节) S1.2 C3 a O C2 S2.1 S1.1S1 S2.1S2.2S2.3 S2.11 S2.12 S2.2 S2.1.1s2.1.2 □上一页 S2.3 「停止放映 C3 第9页
下一页 上一页 停止放映 第 9 页 树结构举例 书目录 目录树 树结构 C1（章） BOOK S1.1(节) S1.2 C1 C2 C3 C2 S2.1 S1.1 S1.2 S2.1 S2.2 S2.3 S2.11 S2.12 S2.2 S2.1.1 S2.1.2 S2.3 C3
树的表示形式 (1)一般形式 (2)嵌套形式 (3)凹入形式 (4)广义表式 □上一页 「停止放映 第10页
下一页 上一页 停止放映 第 10 页 树的表示形式 (1) 一般形式 (2) 嵌套形式 (3) 凹入形式 (4) 广义表形式