2.孩子表示法 (1)多重链表法 由于树中每个结点都有零个或多个孩子结点,因此,可 以令每个结点包括一个结点信息域和多个指针域,每个指 针域指向该结点的一个孩子结点,通过各个指针域值反映 出树中各结点之间的逻辑关系。在这种表示法中,树中每 个结点有多个指针域,形成了多条链表,所以这种方法又 常称为多重链表法。 在一棵树中,各结点的度数各异,因此结点的指针域个数 的设置有两种方法 ①每个结点指针域的个数等于该结点的度数 ②每个结点指针域的个数等于树的度数。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 16 2．孩子表示法 ⑴多重链表法 由于树中每个结点都有零个或多个孩子结点，因此，可 以令每个结点包括一个结点信息域和多个指针域，每个指 针域指向该结点的一个孩子结点，通过各个指针域值反映 出树中各结点之间的逻辑关系。在这种表示法中，树中每 个结点有多个指针域，形成了多条链表，所以这种方法又 常称为多重链表法。 • 在一棵树中，各结点的度数各异，因此结点的指针域个数 的设置有两种方法： ①每个结点指针域的个数等于该结点的度数； ②每个结点指针域的个数等于树的度数
(2)孩子链表表示法 孩子链表法是将树按如下图所示的形式存储。其主体 4是一个与结点个数一样大小的一维数组,数组的每一个 元素有两个域组成,一个域用来存放结点信息,另一个 用来存放指针,该指针指向由该结点孩子组成的单链表 的首位置。单链表的结构也由两个域组成,一个存放孩 子结点在一维数组中的序号,另一个是指针域,指向下 个孩子。 序号 data firstchild 2 BCDEFGH 8∧ 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 17 ⑵孩子链表表示法 孩子链表法是将树按如下图所示的形式存储。其主体 是一个与结点个数一样大小的一维数组，数组的每一个 元素有两个域组成，一个域用来存放结点信息，另一个 用来存放指针，该指针指向由该结点孩子组成的单链表 的首位置。单链表的结构也由两个域组成，一个存放孩 子结点在一维数组中的序号，另一个是指针域，指向下 一个孩子