大话数据结构–双亲表示法前言6.3树的存储结构

「这是我参与11月更文挑战的第17天,活动详情查看:2021最后一次更文挑战」。

前言

废话不多,数据结构必须学!
每天更新一章,一篇写不完的话会分成两篇来写~

6.3树的存储结构

​ 说到存储结构,就会想到顺序存储和链式存储两种结构。

​ 先来看看顺序存储结构,用一段地址连续的存储单元依次存储线性表的数据元素。这对于线性表来说是很自然的,对于树这样一多对的结构呢?

​ 简单的顺序存储结构是不能满足树的实现要求的。

6.3.1双亲表示法

​ 每个结点,它不一定有孩子,但是一定有且仅有一个双亲。

​ 我们假设以一组连续空间存储树的结点,同时在每个结点中,附设一个指示器指示其双亲结点到链表中的位置。也就是说,每个结点除了知道自己是谁以外,还知道它的双亲在哪里。

image-20211114175446299

其中data是数据域,存储结点的数据信息。而parent是指针域,存储该结点的双亲在数组中的下标。

代码表示

/*树的双亲表示法结点结构定义*/
#define MAX TREE SIZE 100
typedef int TElemType; 	/* 树结点的数据类型,目前暂定为整型*/
typedef struct PTNode	/*结点结构*/
{
    TElemType data;	/*结点数据*/
	int parent;	/*双亲位置*/
} PTNode ;

typedef	struct	/*树结构*/
{
	PTNode nodes[MAX_TREE SIZE]; /*结点数组*/
	int r,n;	/*根的位置和结点数*/
} PTree;
复制代码

有了这样的结构定义,我们就可以来实现双亲表示法了。由于根结点是没有双亲的,所以我们约定根结点的位置域设置为-1,这也就意味着,我们所有的结点都存有它双亲的位置。

image-20211114174452875

image-20211114174458609

​ 这样的存储结构,我们可以根据结点的parent指针很容易找到它的双亲结点,所用的时间复杂度为O(1),直到parent为-1时,表示找到了树结点的根。可如果我们要知道结点的孩子是什么,对不起,请遍历整个结构才行。

​ 我们只需要进行一点改进,增加一个结点最左边孩子的域,不妨叫它长子域,这样就可以很容易得到结点的孩子。如果没有孩子的结点,这个长子域就设置为-1

image-20211114175105273

​ 对于有0个或1个孩子结点来说,这样的结构是解决了要找结点孩子的问题了。甚至是有2个孩子,知道了长子是谁,另一个当然就是次子了。另外一个问题场景,我们很关注各兄弟之间的关系,双亲表示法无法体现这样的关系,那我们怎么办?嗯,可以增加一个右兄弟域来体现兄弟关系,也就是说,每一个结点如果它存在右兄弟,则记录下右兄弟的下标。同样的,如果右兄弟不存在,则赋值为-1

image-20211114175306753

但如果结点的孩子很多,超过了2个。我们又关注结点的双亲、又关注结点的孩子、还关注结点的兄弟,而且对时间遍历要求还比较高,那么我们还可以把此结构扩展为有双亲域、长子域、再有右兄弟域。存储结构的设计是一个非常灵活的过程。一个存储结构设计得是否合理,取决于基于该存储结构的运算是否适合、是否方便,时间复杂度好不好等。注意也不是越多越好,有需要时再设计相应的结构。就像再好听的音乐,不停反复听上千遍也会腻味,再好看的电影,一段时间反复看上百遍,也会无趣,你们说是吧?

牛!!!多读几遍就能看懂了!