树存储结构

一、双亲表示法：

　　以一组连续空间存储树的结点，同时在每个结点中，附设一个指示其双亲结点位置的指针域。也就是说每个结点除知道自己外还知道它的双钱在哪儿。它的结点结构如图所示：

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

双亲表示法结点结构定义代码：

//树的双亲表示法结点结构定义
#define MAX_TREE_SIZE 100
typedef struct  //结点结构
{
    char data;   //结点数据
    int parent; //双亲位置
}TNode;
typedef struct       //树结构
{
    TNode nodes[MAX_TREE_SIZE];   //结点数组
    int r, n;      //r是根位置，n是结点数
}Tree;

优点：parent指针域指向数组下标，所以找双亲结点的时间复杂度为O(1),向上一直找到根节点也快。

缺点：由上向下找就十分慢，若要找结点的孩子或者兄弟，要遍历整个树。

改进方法一：增加一个结点最左边孩子的域，不妨叫它长子域，这样就可以很容易得到结点的孩子。如果没有孩子的结点，这个长子域就设置为-1。如图所示：

int firstchild; //长子域

改进二：方便获取各兄弟之间的关系

　　增加一个右兄弟域来体现兄弟关系，也就是说，每一个结点如果它存在右兄弟，则记录下右兄弟的下标。同样的，如果右兄弟不存在，则赋值为-1。如图所示：

　int rightsib; //右兄弟域

如果结点孩子超过2。我们又关注结点的双亲、又关注结点的孩子还关注结点的兄弟，而且对时间遍历要求高，那么我们可以扩展上面结构含有双亲域，长子域，右兄弟域等。

存储结构的设计是一个十分灵活的过程。一个存储结构设计是否合理，取决于基于该存储结构的运算是否合适，方便，时间复杂度好不好等。

二、孩子表示法

　　由于树中每个结点可能有多颗子树，即每个结点有多个指针域，其中每个指针指向一颗子树的根结点，我们呢把这种方法叫做多重链表表示法。

方案一：根据树的度来设置孩子域的个数，例如本例中度为3，设置3个孩子域

缺点：占用了大量不必要的孩子域空指针。以其为标准：需要3n个指针域，实际上有用n-1个（除了根节点，其他n-1个都向上需要一条边），则有2n+1个无用，浪费

方案二：

　　　每个结点指针域的个数等于该结点的度，用一个位置存储节点指针域的个数，结构如图示：

data为数据域，degree为度域，也就是存储该结点的孩子结点个数，chilid1 到 childd为指针域，指向该结点的各个孩子的结点。

缺点：维护困难，不易实现。

最终方案：

　　把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。如图示：

为此，设计两种结点结构，一个是孩子链表的孩子结点，如图示：

其中child是数据域，用来存储某个结点在表头数组中的下标。next域是指针于，用来存储指向某结点下一孩子结点的指针。

另一个是表头数组的表头结点，如图示：

其中data是数据域，存储某结点的数据信息。firstchild是头指针域，存储该结点链表的头指针。

孩子表示法的结构定义代码：

typedef struct CTNode   //孩子结点
{
    int child;     
    struct CTNode* next;
}*ChildPtr;
typedef struct          //表头结构 
{
    int data;
    ChildPtr firstchild; //头指针，指向第一个孩子结点
}CTBox;
typedef struct  
{
    CTBox nodes[MAX_TREE_SIZE];   //结点数组
    int r, n;        //r是根位置，n是结点数
}Tree;

改进三：添加双亲域，方便查找双亲结点（双亲孩子表示法）

三、孩子兄弟表示法

　　任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

结点结构如图示：　　其中data是数据域，fristchild为指针域，存储该结点的第一个孩子结点的存储地址，rightchil为指针域存储该结点的右兄弟结点的存储地址。

孩子兄弟表示法结构定义代码如下：

typedef struct BTNode
{
    int data;
    struct BTNode* firstchild, rightsib;
};

上图便便型就成二叉树了

树 存储结构

树存储结构