数据结构CC版第7章 学习树和森林.pptx

《数据结构CC版第7章 学习树和森林.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构（C语言版）项目七学习树和森林树形结构是常用的一种非线性结构，结构中结点间关系是前驱唯一而后继不唯一，结点之间的数据关系是一对多的关系。树是树形结构的一个重要类型。在本项目中，通过1个工作任务，向读者展示树、森林的概念、计算方法以及实现应用。目录任务实现深度为3的树实现深度为3的树准备知识实现深度为3的树树的概述树和二叉树的三个主要差别森林的概述树的抽象数据类型和基本操作树的遍历森林的遍历树的存储结构树与二叉树的相互转换森林与二叉树的相互转换K叉树1.树的概述1.树的概述树（Tree）是一种数据结构，它是由n（n>=0）个相同类型的数据元素组成一个具有层次关系的集合

2、。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。树中的数据元素叫结点。n=0的树称为空树。2.树和二叉树的三个主要差别2.树和二叉树的三个主要差别树和二叉树的主要差别：1）树中结点的最大度数没有限制，而二叉树结点的最大度数为2。2）树的结点无左、右之分，而二叉树的结点有左、右之分。3）二叉树是最简单的树模型，具有树的递归性质，而且按左右子树可得到一个顺序（即使其成为有序的结构），可以方便使用树和二叉树是可以按一定的规则互相转换的。3.森林的概述3.森林的概述森林（forest）是m(m≥0)棵互不相交的树的集合，即2棵及2棵以上的树，称为森林。

3、将一棵非空树的根结点删去，就变成一个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。4.树的抽象数据类型和基本操作4.树的抽象数据类型和基本操作树的抽象数据类型的定义如下：ADTTree{（1）数据对象D：一个集合，该集合中的所有元素具有相同的特性。（2）数据关系R：若D为空或D中仅含有一个数据元素，则R＝{Φ}，否则R={H}，H关系如下。a.在D中存在唯一的称为根的数据元素root，它在关系H下没有前驱。b.除root以外，D中其余结点存在m(m≥0)个不相交的划分，每个划分都是一棵树，是根的子树。（3）树的基本操作。}ADTTree树的基本操作包括：（1）初

4、始化空树：建立一棵树。（2）构建树：根据树广义表字符串创建一个树（3）判断是否为空：判断树是否为空，若为空，则返回1，否则返回0。（4）求深度：返回树的深度。（5）查找树结点：从树中查找值为x的结点（6）清除树：清除树，使之变为一棵空树。（7）销毁操作：销毁以BT为根的二叉树，释放空间。4.树的抽象数据类型和基本操作5.树的遍历5.树的遍历树的遍历方法有两种：一种是先根(次序)遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树；另一种是后根(次序)遍历，即先依次后根遍历每棵子树，然后访问根结点。先根遍历5.树的遍历（1）先根遍历的顺序为：1）访问根结点；2）按照从左到

5、右的顺序先根遍历根结点的每一棵子树。按照树的先根遍历的定义，对下图所示的树进行先根遍历，得到的结果序列为：ABEFGCHDIJ树的遍历后根遍历5.树的遍历（2）后根遍历的顺序为：1）按照从左到右的顺序后根遍历根结点的每一棵子树。2）访问根结点；对下图中树进行后序遍历得到的结点序列为EFGBHCIJDA树的遍历层次遍历5.树的遍历树的遍历（3）上述的先根和后根遍历是按深度方向对树进行遍历，也可按广度方向遍历树。层次遍历的顺序为：1）首先依次访问层数为0的结点；2）然后依次访问层数为1的结点；3）以此类推，直到访问完最下一层的所有结点。对下图中树进行后序遍历得到的结点序列为AB

6、CDEFGHIJ6.森林的遍历6.森林的遍历按照森林和树相互递归的定义，可以推出森林的遍历方法，森林的遍历也有两种方式。前序遍历6.森林的遍历前序遍历的定义为：1）访问森林中第一棵树的根结点；2）前序遍历第一棵树的根结点的子树；3）前序遍历去掉第一棵树后的子森林。如下图所示的森林的先序遍历的结点序列为ABCDEFGHJI森林的遍历中序遍历6.森林的遍历中序遍历的定义为：1）中序遍历第一棵树的根结点的子树；2）访问森林中第一棵树的根结点；3）中序遍历去掉第一棵树后的子森林。此森林的中序遍历的结点序列为BCDAFEJHIG拓展提高：由森林与二叉树的转换关系以及森林与二叉树的遍历

7、定义可知，森林的前序遍历和中序遍历与所转换得到的二叉树的先序遍历和中序遍历的结果序列相同。7.树的存储结构7.树的存储结构在实际应用中，人们采用多种形式的存储结构来表示树，树成为人们表示一种客观信息的手段，但一般的树不像二叉树那样有规则的形态。既有顺序存储结构，又有链式存储结构，但无论采用哪种存储结构，都要求存储结构不但能存储结点本身的信息，还能存储树中各结点之间的逻辑关系。常用的树的存储方式包括以下几种：（1）双亲表示法（2）孩子表示法（3）孩子兄弟表示法7.树的存储结构8.树与二叉树的相互转换8.树与二叉树的相