
合取警院 第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