[理学]第七章 树.ppt

数据结构（Java语言版） 邮箱：wenh@ 第一节 7.1.实例引入 【学习任务】通过实例分析，了解树形结构的特点。 【例7.1】连锁店结构示意图。 假设北京某食品连锁店，为扩大其经销范围，增强其销售能力和竞争实力，在东北地区的哈尔滨、长春、沈阳等城市建立分店，由于经销得当，销售情况良好，在每个城市分店处又可建立了若干分店，其结构图如图7.1所示。 第一阶段 第二节 7.2 树 【学习任务】掌握树的定义和相关概念，了解树的表示方法，理解树的存储结构。 7.2.1 树的定义 树（Tree）是由n（n≥0）个结点构成的有限集合。结点数为0的树称为空树，结点数大于0的树称为非空树。 结点：结点由数据元素和构造数据元素之间关系的指针组成。指针指向结点的子树的分支。图7.2(a)是一棵只有1个结点的树，图7.2(b)是一棵具有12个结点的树. 第二阶段 叶子结点和分支结点：将度为0的结点称为叶子结点，又称为终端结点。将度不为0的结点称为分支结点，又称为非终端结点。图7.2(b)中的E、F、G、H、J、K、L都是叶子结点。A、B、C、D、I结点都是分支结点。 孩子结点和双亲结点：某结点子树的根结点称为该结点的孩子结点。该结点称为孩子结点的双亲结点。如图7.2(b)中的B、C、D结点是A结点的孩子结点，K结点是I结点的孩子结点，相对应的A结点是B、C、D结点的双亲结点。 兄弟结点：具有同一双亲的结点互为兄弟结点。如图7.2(b)中的H、I、J结点具有相同的双亲结点D，所以称H、I、J结点为兄弟结点。 后裔和祖先：一个结点的所有子树上的任何结点都是该结点的后裔。该结点称为这些后裔结点的祖先。如图7.2(b)中的H、I、J、K、L结点都是结点D后裔，A、D、I结点称为K结点的祖先。 结点的层次：从根结点到树中某结点所经路径上的边数加1称为该结点的层次。根结点的层次规定为1，其他结点的层次就是其双亲结点的层次数加1。如图7.2(b)中的H结点层次为3。 树的深度：树中所有结点的层次的最大值称为该树的深度。如图7.2(b)中的树深度为4。 无序树：如果树中任意结点的各孩子结点的排列没有严格次序，可交换位置，则称该树为无序树。 有序树：如果树中任意结点的各孩子结点的排列有严格的次序，不可交换位置，则称该树为有序树。在有序树中，最左边的子树的根结点称为第一个孩子，最右边的称为最后一个孩子。 森林：n（n≥0）棵树的集合称为森林。森林和树的概念相近，删除一棵树的根，则所有的子树形成森林；而为森林加上一个根，则森林就变成一棵树。 7.2.2 树的表示方法 树的常用表示方法有以下四种：图形表示法、文氏图表示法、广义表表示法和凹入表示法。 1．图形表示法 图7.2给出了图形表示树的直观表示法，其中用圆圈表示结点，连线表示结点间的关系，并把树根画在上面。图形表示法主要用于直观描述树的逻辑结构。 2．文氏图表示法 文氏图表示法采用集合的包含关系表示树，如图7.3所示。 3．广义表表示法 以广义表的形式表示树，利用广义表的嵌套区间表示树的结构。如图7.4所示。 4．凹入表示法（章节目录表示法） 采用逐层缩进的方法表示树，有横向凹入表示和竖向凹入表示。图7.5所示为横向凹入表示。 7.2.4 树的存储结构 对于树，关心的是树在计算机中如何表示和存储。存储树时，既要存储结点的数据元素，又要存储结点之间的逻辑关系。采用树的存储结构主要有双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法。 表示结点之间的逻辑关系主要采用指针或仿真指针。 1．双亲表示法 使用指针表示每个结点的双亲结点，即双亲表示法。每个结点包含两个域：数据域和指针域。 图7.6(a)是对图7.2(b)采用常规指针表示的存储结构，图7.6(b)是对图7.2(b)采用仿真指针表示的存储结构。 2．孩子表示法 使用指针表示出每个结点的孩子结点，即孩子表示法。由于每个结点的孩子结点个数不同，为了简便起见，孩子表示法中的每个结点的指针域个数是树的度。 图7.7是对图7.2(b)采用常规指针表示的存储结构。 孩子表示法与双亲表示法的特点相反。孩子表示法可方便的找到一个结点的孩子及其后裔，并能方便的实现树的遍历。 3．双亲孩子表示法 采用双亲表示法和孩子表示法的优势，使用指针既表示出每个结点的双亲结点，又表示出每个结点的孩子结点，就是双亲孩子表示法。指针域既包括指向孩子的指针，也包括指向双亲结点的指针。图7.8是对图7.2(b)采用常规指针表示的存储结构，其中实线表示孩子指针，虚线表示双亲指针。 4．孩子兄弟表示法 采用指针既指向每个结点的孩子结点，又指向每个结点的兄弟结点，就是孩子兄弟表示法