树的存储结构

   提到存储结构，可以很自然的想到顺序存储结构和链式存储结构两种。树这种数据结构类型，它是由结点和联接结点的边构成。这些边，联接了树中的任意两个结点，从计算机内存中的存储方式来看，其实，就是通过指针保存了地址，从而实现了两个结点间的联接。

   那么关于树的表示方式，先讲一下最简单的，就是双亲表示法，我把它称之为父节点表示法。毕竟，在树中，双亲结点其实就是父节点。既然，链表也是有结点构成，那么，这个结点中，必然的必须得有能够存放数据的变量，以及存放下一个结点的地址的变量，如果没有这个变量，如何建立两个结点间的联接呢？但是，此时，这个存放的地址的变量，并不是存放下一个结点的地址，存放的是它的父节点的地址，也就是父节点在数组中的下标位置。然后还得再定义一个树结构，这个数结构中，必须得包含一个数组，因为数组就是用来表示结点的，还得有一个根节点的位置变量以及结点数的变量。那么，该结构定义如下：

#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。

如上图所示，结点A就是根结点。

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

因为B的父亲是A，所以B中存放了A的下标0，C和D的父亲都是A，所以都存放了下标0，E、F和G的父亲是B，所以它们存放了B的下标1；H的父亲是C，所以H存放了下标2；I和J的父亲是D，所以它们存放了D的下标3。这种方式可以知道哪个结点是哪个结点的父亲，哪个结点是哪个结点的儿子，但是却无法确定顺序，也就是说，一个结点可能拥有多个子节点，但是却无法确定这些子节点哪个在前哪个在后。双亲表示法求父节点方便，因为每个结点中都保存了其父节点的下标。

   第二种方式。孩子表示法。依然采用连续存储，也就是数组存储，不过，一个结点分为两部分，一部分放数据，另一部分放其子节点的指针（地址）。若是一个结点有多个孩子，假设A有三个孩子，B、C和D。那么，A中就存放B的指针域，在B中则存放C的指针域，C中则存放D的指针域，也就是A的孩子采用了链式存储的方式，串联了起来。孩子表示法，求其子节点比较方便，而求其父节点就比较麻烦。

孩子表示法结构代码如下：

#define MAXZ_TREE_SIZE  100
typedef struct CTNode{
    
    int child;
    struct CTNode *next;
}*ChildPtr;

typedef struct{

    TElemType data;
    ChildPtr firstchild;
}CTBox;

typedef struct{

    CTBox nodes[MAX_TREE_SIZE];
    int r, n;   //存放树的根和结点数
    
}CTree;

   第三种方式。父亲孩子表示法。顾名思义，就是将前两种方式结合了。也就是说，一个结点不止存放数据，还存放该该节点的父节点的下标，还存放该节点子节点的指针，那为什么父节点可以存放下标，存放子节点就只能存放子节点的指针？因为，一个结点只有一个父节点，却有多个子节点，或者是没有子节点，所以没有办法确定子节点的个数，于是，就只能通过链式存储了。

        二叉树法（孩子兄第表示法）就是将一般树转化为二叉树。具体转化方式为：左指针指向它的第一个孩子结点，右指针指向它的第一个兄弟结点。

二叉树法结构代码定义如下：

typedef struct CSNode{
    
    TElemType data;
    struct CSNode *firstchild, *rightsib;

}CSNode, *CSTree;