6.3树的存储结构( 二 ) _结点

6.3树的存储结构
? 说到存储结构，就会想到顺序存储和链式存储两种结构。
? 先来看看顺序存储结构，用一段地址连续的存储单元依次存储线性表的数据元素。这对于线性表来说是很自然的，对于树这样一多对的结构呢?
? 简单的顺序存储结构是不能满足树的实现要求的。
?
6.3.1双亲表示法
? 每个结点，它不一定有孩子，但是一定有且仅有一个双亲。
? 我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。也就是说，每个结点除了知道自己是谁以外，还知道它的双亲在哪里。
其中data是数据域，存储结点的数据信息。而是指针域，存储该结点的双亲在数组中的下标。
代码表示
/*树的双亲表示法结点结构定义*/#define MAX TREE SIZE 100typedef int TElemType;/* 树结点的数据类型，目前暂定为整型*/typedef struct PTNode /*结点结构*/{TElemType data; /*结点数据*/int parent; /*双亲位置*/} PTNode ;typedef struct /*树结构*/{PTNode nodes[MAX_TREE SIZE]; /*结点数组*/int r,n; /*根的位置和结点数*/} PTree;
有了这样的结构定义，我们就可以来实现双亲表示法了。由于根结点是没有双亲的，所以我们约定根结点的位置域设置为-1,这也就意味着,我们所有的结点都存有它双亲的位置。
? 这样的存储结构，我们可以根据结点的指针很容易找到它的双亲结点，所用的时间复杂度为O(1),直到为-1时，表示找到了树结点的根。可如果我们要知道结点的孩子是什么，对不起，请遍历整个结构才行。
? 我们只需要进行一点改进，增加一个结点最左边孩子的域,不妨叫它长子域，这样就可以很容易得到结点的孩子。如果没有孩子的结点，这个长子域就设置为-1
? 对于有0个或1个孩子结点来说，这样的结构是解决了要找结点孩子的问题了。甚至是有2个孩子，知道了长子是谁，另一个当然就是次子了。另外一个问题场景，我们很关注各兄弟之间的关系，双亲表示法无法体现这样的关系，那我们怎么办?嗯，可以增加一个右兄弟域来体现兄弟关系，也就是说，每一个结点如果它存在右兄弟，则记录下右兄弟的下标。同样的，如果右兄弟不存在，则赋值为-1
但如果结点的孩子很多，超过了2个。我们又关注结点的双亲、又关注结点的孩子、还关注结点的兄弟，而且对时间遍历要求还比较高，那么我们还可以把此结构扩展为有双亲域、长子域、再有右兄弟域。存储结构的设计是一个非常灵活的过程。一个存储结构设计得是否合理，取决于基于该存储结构的运算是否适合、是否方便，时间复杂度好不好等。注意也不是越多越好，有需要时再设计相应的结构。就像再好听的音乐，不停反复听上千遍也会腻味，再好看的电影，一段时间反复看上百遍，也会无趣，你们说是吧?
牛！！！多读几遍就能看懂了！
6.3.2孩子表示法
换一种完全不同的考虑方法。由于树中每个结点可能有多棵子树，可以考虑用多重链表，即每个结点有多个指针域，其中每**个指针指向一棵子树的根结点,我们把这种方法叫做多重链表表示法。**不过，树的每个结点的度，也就是它的孩子个数是不同的。所以可以设计两种方案来解决。
方案一：
? 一种是指针域的个数就等于树的度，复习一下，树的度是树各个结点度的最大值
[data|child||…|]
其中data是数据域，到是指针域，用来指向该结点的孩子结点
用图来说明一下吧
这种方法显然是很浪费空间的，因为有很多结点，它的指针域都是空的