树有3种常用的存储结构，即双亲表示法，孩子表示法，孩子兄弟表示法。

（1）双亲表示法

用一组连续的存储空间（一维数组）存储树中的各结点，每个结点包含两个域。如图6.21所示。

1）数据域：存放结点本身信息。

2）双亲域：指示本结点的双亲结点在数组中位置。

双亲表示法的C语言描述如下：

#define MAXSIZE 100      //树中结点的最大数

typedef struct PTnode

{     tdatatype   data;    //存储数据信息的值

      int  parent;         //存储双亲位置

} PTnode;

PTnode tree[MAXSIZE];

（2）孩子表示法

孩子表示法也是用一维数组来存储树中各结点的信息，每个结点包含两个域，但结点的结构与双亲表示法中结点的结构不同。孩子表示法中的结点除了存放结点本身信息外，还保存一个链表的第一个结点的地址信息。

（3）孩子兄弟表示法（二叉树表示法）

孩子兄弟表示法，以二叉链表作为树的存储结构。链表中结点的两个域分别指向其第一个孩子结点和下一个兄弟结点，分别命名为firstchild域和nextsibling域。

 

结点的C语言描述如下：

typedef  struct  tnode

{   datatype  data;             //数据域

    struct  tnode *fistchild, *nextsibling;  //指针域，分别指向第一个孩子和右兄弟

}tnode;