数据结构 教学课件 宗大华 陈吉人 06树与森林.pdfVIP

第6章 树与森林 第6章 树与森林 6.1 树 的 概 述 6.1 6.2 树 、 森 林 和 二 叉 树 间 的 转 换 6.2 6.3 树 的 存 储 结 构 6.3 6.4 树 的 遍 历 6.4 6.5 判 定 树 6.5 树具有分支和层次性，是一种树型结构。 属于非线性结构之列。由于允许树中的结点 可以有多个子结点，因此它的存储结构以及 操作实现，比起二叉树来要更为复杂一些。 本章主要介绍以下几个方面的内容：  树的定义及基本概念；  树、森林与二叉树之间的相互转换；  树的各种存储结构；  树、森林的遍历。 6.1 树 的 概 述 6.1 树 的 概 述 6.1.1 树的定义及特性 ≥ 所谓“树（Tree）”是指由n（n 0） 个结点构成的有限数据元素的集合T。当n=0 ≠ 时，称其为“空树”。当n 0时，树中诸结 点应该满足下面的两个条件： （1）有且仅有一个特定的结点，它没 有前驱，是该树的根，称为树的根结点； （2）除根结点外的其余结点，可分为m ≥ （m0）个互不相交的有限集合：T1， ≤ ≤ T2，…，Tm，每一个集合Ti（0 i m）又是 一棵树，被称为是根的子树。 树有如下的几个特性：  空树是树的一个特例；  一棵非空树，至少有一个根结点，只有根 结点的树为最小树；  在有多个结点的树里，除根结点外，其余 结点分属若干个子树，各子树间互不相交；  除根结点外，树中其他结点有且只有一个 前驱结点，但可以有零个或多个后继结点。 例6-1 图6-2所示为树的几种图形表示。 图6-2 图的几种示例 例6-2 图6-3所示为几个不是树的图形。 图6-3 非树型结构示例 6.1.2 有关树的常用术语 1 ．有关结点的术语  结点 所谓树的一个“结点”，是指一个数据 元素以及指向其子树根结点的分支。在树型 结构中，常用一个圆圈及一条条短线表示。  结点的度 所谓结点的“度”，是指树中一个结点 拥有的子树数目。因此，结点的度也就是该 结点的后继结点的个数。  结点的深度 树是一种层次结构。通常，把一棵树的 根作为第0层，其余结点的层次值，为其前 驱结点所在层值加1。所谓结点的“深度”， 即是该结点位于树的层次数。有时，也把结 点的深度称为结点的“层次”。  叶结点 树中度为0的结点被称为叶结点。叶结 点也就是终端结点。  分支结点 树中度大于0的结点称为分支结点，或 非终端结点。  结点的路径 从树中一个结点到另一个结点之间的分 支，称为这两个结点间的路径。  路径长度 一条路径上的分支数，称为该路径的长 度。 2 ．有关结点间关系的术语  根结点 所谓“根”结点，即是指树中没有直接 前驱的那个结点。一棵树，只能有一个根结 点。  孩子结点 树中一个结点的所有直接后继，都被称 作是该结点的孩子结点。实际上，一个结点 的孩子结点就是该结点子树的根结点。  双亲结点 在树中，把一个结点称作是它所有后继 结点的双亲结点。双亲结点有时也被称作父