合取警院 第8章树和森林及其应用 HEFEI UNIVERSITY 第8章树和森林及其应用 m8.1树和森林的基本概念 8.2树的存储 8.3树的基本算法 8.4树的应用—B-树 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(200711一20)
第8章 树和森林及其应用 1 ☞8.1 树和森林的基本概念 8.2 树的存储 8.3 树的基本算法 8.4 树的应用——B-树 第8章 树和森林及其应用
⑧合取学院 第8章树和森林及其应用 HEFEI UNIVERSITY 树的定义 树是由（≥0）个节点组成的有限集合，其中： (包)当n=0时为空树： (②当>0时，有且仅有一个特定的节点，称为树的 根，其余节点可分为m(m>0)个互不相交的子集，其中 每一个子集本身又是一棵树，并且称为根的子树。 可见，树的定义也是递归定义 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071山20)
第8章 树和森林及其应用 2 树的定义： 树是由n(n≥0)个节点组成的有限集合，其中： ⑴ 当n＝0时为空树； ⑵ 当n＞0时，有且仅有一个特定的节点，称为树的 根，其余节点可分为m(m>0)个互不相交的子集，其中 每一个子集本身又是一棵树，并且称为根的子树。 可见，树的定义也是递归定义
⑧合取些院 第8章树和森林及其应用 HEFEI UNIVERSITY 树结构中常用的基本术语 父结点：若一个节点有子树，则该结点为父结点。 孩子结点：一个结点子树的根 兄弟结点：同一个结点的孩子。 层次：根结点的层次为1，其余结点的层次是其父结点的 层次加1 E G 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(200711一20)
第8章 树和森林及其应用 3 树结构中常用的基本术语 父结点：若一个节点有子树，则该结点为父结点。 孩子结点：一个结点子树的根。 兄弟结点：同一个结点的孩子。 层次：根结点的层次为1，其余结点的层次是其父结点的 层次加1。 A B C D E F G H
合取警院 第8章树和森林及其应用 HEFEI UNIVERSITY 高度（深度）：树中结点的最大层次数。 度：一个结点的孩子数目是这个结点的度。 A 如：图中A的度为2 ® 叶子结点：度为0的结点。 分支结点：度不为0的结点。 树的度：树中结点的最大的度。上图中树的度为3 有序树/无序树：兄弟结点之间的排列是否有序。 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(200711一20)
第8章 树和森林及其应用 4 高度（深度）：树中结点的最大层次数。 度：一个结点的孩子数目是这个结点的度。 如：图中A的度为2 叶子结点：度为0的结点。 分支结点：度不为0的结点。 树的度：树中结点的最大的度。上图中树的度为3。 有序树/无序树：兄弟结点之间的排列是否有序。 A B C D E F G H
⑧合取学院 第8章树和森林及其应用 HEFEI UNIVERSITY 注意：虽然树结构的图形表示形式和二叉树的图形表示 形式有相似之处，但两者从本质上说是不同的 ··二叉树中每个结点的孩子都有左右之分：左孩 子、右孩子；而树不是。 例：三个结点所构成的树。 A 结论：二叉树和树是两种不同的数据结构。 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071山20)
第8章 树和森林及其应用 5 注意：虽然树结构的图形表示形式和二叉树的图形表示 形式有相似之处，但两者从本质上说是不同的 －－二叉树中每个结点的孩子都有左右之分：左孩 子、右孩子；而树不是。 例：三个结点所构成的树。 A B C C A B 结论：二叉树和树是两种不同的数据结构
⑧合耻学院 第8章树和森林及其应用 HEFEI UNIVERSITY 森林： 森林是m(m心0)棵互不相交的树的集合。 即：森林是多棵树。 G） 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071120)
第8章 树和森林及其应用 6 森林： 森林是m (m≥0) 棵互不相交的树的集合。 即：森林是多棵树。 E F A B C D J H I G
合取警院 第8章树和森林及其应用 HEFEI UNIVERSITY 第8章 树和森林及其应用 8.1树和森林的基本概念 m8.2树的存储 8.3树的基本运算 8.4树的应用—B-树 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(200711一20)
第8章 树和森林及其应用 7 8.1 树和森林的基本概念 ☞8.2 树的存储 8.3 树的基本运算 8.4 树的应用——B-树 第8章 树和森林及其应用
合取学院 第8章树和森林及其应用 HEFEI UNIVERSITY 8.2树的存储 r8.2.1双亲表示法 8.2.2孩子表示法 8.2.3孩子兄弟表示法 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071山20)
第8章 树和森林及其应用 8 ☞ 8.2.1 双亲表示法 8.2.2 孩子表示法 8.2.3 孩子兄弟表示法 8.2 树的存储
)合取学院 第8章树和森林及其应用 HEFEI UNIVERSITY 实现：定义结构数组存放树的结点，每个结点含两个域 数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置 特点：找双亲容易，找孩子难， 其结点的结构如下： typedef struct node 数据 双亲 datatype data; data parent int parent; Tnode; 合肥学院计算机科字与技术系“数据结构与算法”课程建设组(2007-11一20)
第8章 树和森林及其应用 9 data parent 数据 双亲 实现：定义结构数组存放树的结点，每个结点含两个域 数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置 特点：找双亲容易，找孩子难. 其结点的结构如下： typedef struct node { datatype data; int parent; }Tnode;
)合取警院 第8章树和森林及其应用 HEFEI UNIVERSITY 0号单元不用或 a 存结点个数 data parent 0 0 9 1 a 0 d f 1 3 c 1 4 d 2 5 e 2 f 3 g 5 如何找孩子结点 h 5 9 5 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(2007-11-20) 10
第8章 树和森林及其应用 10 6 0 1 2 3 4 5 7 8 9 data parent 0号单元不用或 存结点个数 如何找孩子结点 a b c d e f g h i a c d e f g h i b 0 1 2 2 3 5 5 5 1 0 9