数据结构—基础知识(13):树的存储结构

时间:2024-01-27 19:40:17

孩子表示法

由于树中每个结点可能有多棵子树,则可用多重链表,即每个结点有多个指针域,其中每个指针指向一棵子树的根结点,此时链表中的结点可以有如下图的两种结点格式。
在这里插入图片描述

若采用第一种结点格式,则多重链表中的结点是同构的,其中d为树的度。由于树中很多结点的度小于 d,所以链表中有很多空链域,空间较浪费,不难推出,在一棵有n个结点度为k的树中必有n(k-1)+1 个空链域

若采用第二种结点格式,则多重链表中的结点是不同构的,其中d为结点的度,degree 域的值同d。此时,虽能节约存储空间,但操作不方便

另一种办法是,把每个结点的孩子结点排列起来,看成是一个线性表,且以单链表做存储结构,则n个结点有n个孩子链表(叶子的孩子链表为空表)。而n个头指针又组成一个线性表,为了便于查找,可采用顺序存储结构。

下图(a)所示为下图中的树的孩子表示法。与双亲表示法相反,孩子表示法便于那些涉及孩子的操作的实现。可以把双亲表示法和孩子表示法结合起来,即将双亲表示和孩子链表合在一起。图(b)所示的就是这种存储结构的一例,它和图(a)表示的是同一棵树。
在这里插入图片描述