树这种结构除了根结点外，其余每个结点，它不一定有孩子，但是一定有且仅有一个双亲。我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点在数组中的位置。也就是说，每个结点除了知道自己是谁以外，还知道它的双亲在哪里。它的结点结构为表6-4-1所示。

    data parent

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

    以下是我们的双亲表示法的结点结构定义代码。

    1. /* 树的双亲表示法结点结构定义 */
    2. #define MAX_TREE_SIZE 100
    4. /* 树结点的数据类型，目前暂定为整型 */
    5. typedef int TElemType;
    7. /* 结点结构 */
    8. typedef struct PTNode{
    10.     /* 结点数据 */
    11.     TElemType data;
    12.     /* 双亲位置 */
    13.     int parent;
    15. } PTNode;
    17. /* 树结构 */
    18. typedef struct{
    20.     /* 结点数组 */
    21.     PTNode nodes[MAX_TREE_SIZE];
    22.     /* 根的位置和结点数 */
    23.     int r, n;
    25. } PTree;

    有了这样的结构定义，我们就可以来实现双亲表示法了。由于根结点是没有双亲的，所以我们约定根结点的位置域设置为-1，这也就意味着，我们所有的结点都存有它双亲的位置。如图6-4-1中的树结构和表6-4-2中的树双亲表示所示。
    image.png

    下标 data parent
    0 A -1
    1 B 0
    2 C 0
    3 D 1
    4 E 2
    5 F 2
    6 G 3
    7 H 3
    8 I 3
    9 J 4

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

    这真是麻烦，能不能改进一下呢？

    当然可以。我们增加一个结点最左边孩子的域，不妨叫它长子域，这样就可以很容易得到结点的孩子。如果没有孩子的结点，这个长子域就设置为-1，如表6-4-3所示。

    下标 data parent firstchild
    0 A -1 1
    1 B 0 3
    2 C 0 4
    3 D 1 6
    4 E 2 9
    5 F 2 -1
    6 G 3 -1
    7 H 3 -1
    8 I 3 -1
    9 J 4 -1

    对于有0个或1个孩子结点来说，这样的结构是解决了要找结点孩子的问题了。甚至是有2个孩子，知道了长子是谁，另一个当然就是次子了。

    另外一个问题场景，我们很关注各兄弟之间的关系，双亲表示法无法体现这样的关系，那我们怎么办？嗯，可以增加一个右兄弟域来体现兄弟关系，也就是说，每一个结点如果它存在右兄弟，则记录下右兄弟的下标。同样的，如果右兄弟不存在，则赋值为-1，如表6-4-4所示。

    下标 data parent rightsib
    0 A -1 -1
    1 B 0 2
    2 C 0 -1
    3 D 1 -1
    4 E 2 5
    5 F 2 -1
    6 G 3 7
    7 H 3 8
    8 I 3 -1
    9 J 4 -1

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