(3)凹入式表示法 B E K D H 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 （3) 凹入式表示法 A B E F J K G C D H I
三、树中常用术语 <心 1.双亲与孩子设X与Y为树中的两个结点,若X 是Y的前驱,则称X是Y的双亲,Y是X的孩子。 二2.兄弟与堂兄弟树中的两个结点X与Y存在有 共同的双亲,称X与Y为兄弟,若其双亲为兄弟, 则称为堂兄弟 ≥3.分支结点和终端结点有后继结点的结点称为 分支结点;没有后继结点的结点称为终端结点 或树叶。 4.结点的度结点的后继结点的个数称为该结点 的度显然度为零的结点一定是树叶。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 1. 双亲与孩子设X与Y为树中的两个结点，若X 是Y的前驱，则称X是Y的双亲，Y是X的孩子。 2. 兄弟与堂兄弟树中的两个结点X 与Y存在有 共同的双亲，称X与Y为兄弟，若其双亲为兄弟， 则称为堂兄弟 3. 分支结点和终端结点 有后继结点的结点称为 分支结点；没有后继结点的结点称为终端结点 或树叶。 4. 结点的度结点的后继结点的个数,称为该结点 的度,显然,度为零的结点一定是树叶。 三、树中常用术语
5.树的度树中结点度的最大值称为树的度。 例如:图5-1树的度为3,因为该树中,有度为一的结点、 也有度为二、度为零与度为三的结点,其度的最大值为 三。若一棵树的度为n时,则称该树为n度树。 6.结点的层又称为结点的层次高度,它是从树根开始定 义的:即根结点属于第一层,其余结点的层次高度等于 其双亲的层次+1。 7.树的层次高度树的层次高度等于树中结点的层次的 最大值。(也称为树的深度) 8.森林n(n>=0)棵互不相交的树的集合。注意 当n=0时说明森林中无结点,即森林可以为空。(树不 能为空) 9有序树和无序树:若树中结点从左到右是有序的,则 称该树为有序树,反之为无序树工程
武汉理工大学华夏学院-信息工程 系 5.树的度 树中结点度的最大值,称为树的度。 例如：图5-1树的度为3, 因为该树中，有度为一的结点、 也有度为二、度为零与 度为三的结点，其度的最大值为 三。若一棵树的度为n时，则称该树为n度树。 6. 结点的层 又称为结点的层次高度，它是从树根开始定 义的：即根结点属于第一层，其余结点的层次高度等于 其双亲的层次＋1。 7. 树的层次高度 树的层次高度等于树中结点的层次的 最大值。（也称为树的深度） 8. 森林 n（ n>=0 ）棵互不相交的树的集合。注意： 当n＝0时说明森林中无结点，即森林可以为空。（树不 能为空） 9.有序树和无序树：若树中结点从左到右是有序的，则 称该树为有序树，反之为无序树
四、树的存储结构 当一棵树的逻辑结构确定以后,就应该考虑如何存放 在计算机中,存储一棵树时,不仅要存储树中每个结点 ●的值,而且要存储各结点之间的关系,一般可以用三种 方法实现 1,双亲数组表示方法:用一个一维数组存储树中的结点 数组元素是一个结构体,该结构体中包含两个字段:其 为data字段,用来存放结点的值;其二为 parent字段 用来存储该结点的双亲结点(即该结点的前驱结点)在 数组中的下标地址 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 1.双亲数组表示 方法：用一个一维数组存储树中的结点， 数组元素是一个结构体，该结构体中包含两个字段：其 一为data字段，用来存放结点的值；其二为parent字段, 用来存储该结点的双亲结点（即该结点的前驱结点）在 数组中的下标地址。 四、 树的存储结构 当一棵树的逻辑结构确定以后, 就应该考虑如何存放 在计算机中，存储一棵树时，不仅要存储树中每个结点 的值，而且要存储各结点之间的关系，一般可以用三种 方法实现：
例如:以图5-1所示的三度树为例,存储该树 的双亲数组表示,如图5-2所示。 「23451678910m moa abcd efghiilk rram022“2到3 图5-2图41树的双亲数组存储表示 存储特点:可以根据每一个结点本身的内容直 接读取其双亲结点的地址,但查找孩子结点较 困难。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 例如： 以图5-1所示的三度树为例，存储该树 的双亲数组表示， 如图5-2所示。 1 图5-2 图4-1树的双亲数组存储表示 data 2 parent root 1 3 4 5 6 7 8 9 a b c d e f g h i 0 1 1 2 2 2 3 3 7 10 11 j k 5 5 存储特点：可以根据每一个结点本身的内容直 接读取其双亲结点的地址，但查找孩子结点较 困难