西安交通大学：《计算机软件基础》第4单元 非线性数据结构树、二叉树

第4单元 非线性数据结构 树、二叉树 计算机软件基础 The software bas ic of computer 讲:刘志 西安交通大学 计算机教学实验中心

下一页 计算机软件基础 The software basic of computer 主讲：刘志强 西安交通大学 计算机教学实验中心 第4单元 非线性数据结构 树、二叉树

教学目标 ●了解树、二叉树: 基本概念 逻辑结构 存储结构及实现 遍历算法 特殊二叉树的表示及性质 □上一页 「停止放映 第2页

下一页 上一页 停止放映 第 2 页 教学目标 ⚫ 了解树、二叉树: –基本概念 –逻辑结构 –存储结构及实现 –遍历算法 –特殊二叉树的表示及性质

教学要求 通过本单元的学习,了解、掌握: ●树、二又树的基本概念 ●树、二叉树的存储结构及实现 ●二叉树的遍历操作及有关算法 ●特殊二叉树的表示及性质 ●树、森林、二叉树的转换 □上一页 「停止放映 第3页

下一页 上一页 停止放映 第 3 页 教学要求 通过本单元的学习，了解、掌握： ⚫ 树、二叉树的基本概念 ⚫ 树、二叉树的存储结构及实现 ⚫ 二叉树的遍历操作及有关算法 ⚫ 特殊二叉树的表示及性质 ⚫ 树、森林、二叉树的转换

本单元涉及的内容 第3章 3.1、树形结构及基本概念 3.2、二叉树 3.3、二叉树的遍历 3.4树、森林与二叉树的转换 □上一页 (P81P90 「停止放映 第4页

下一页 上一页 停止放映 第 4 页 本单元涉及的内容 第3章 3.1、树形结构及基本概念 3.2、二叉树 3.3、二叉树的遍历 3.4树、森林与二叉树的转换 (P81~P90)

、树型结构及其基本概念 树形结构基本概念包括的内容: 树的定义 树的基本概念 结点、根、叶、路径、结点度、 树的度 结点的层次、子结点、父结点 有序、无序 □上一页 「停止放映 第5页

下一页 上一页 停止放映 第 5 页 一、树型结构及其基本概念 ⚫ 树形结构基本概念包括的内容： –树的定义 –树的基本概念 •结点、根、叶、路径、结点度、 树的度 •结点的层次、子结点、父结点 •有序、无序

树形结构 ●树形结构是以分支关系来定义的层次结 构。在客观世界中树形结构广泛存在, 并应用于: 人类社会的族谱、家谱、行政区域划 分管理; 各种社会组织机构; 在计算机领域中,用树表示源程序的 语法结构; □上一页 在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（m0）个互不相交的集合 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) 广义表形式