前言

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

6.3树的存储结构

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

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

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

6.3.1双亲表示法

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

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

其中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,这也就意味着,我们所有的结点都存有它双亲的位置。

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

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

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

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

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