树的存储结构

【双亲表示法】

双亲表示法利用树中每个结点均有且仅有一个父结点的一特性，借助一维数组按层序来存储树的各个结点（顺序存储）

数组中的每个元素对应树中一个结点，每个结点记录两类信息：结点的数据信息、该结点的父结点在数组中的下标

同时规定根结点存储在数组的 0 号存储单元，其指针域设为 -1 表示没有父结点

对于给出的指定结点 p，容易查找到其父结点，但查找 p 的子结点只能从头到尾遍历整个数组

双亲表示法的存储结构描述如下

struct PTNode {
    int data;
    int parent; //父结点在数组中的下标
};
struct PTree {
    int n; //结点数
    PTNode nodes[N];
} tree;

【孩子表示法】

孩子表示法是顺序存储与链式存储的结合，由于树中的每个结点都可能有多个孩子，将每个结点的孩子链接成一个单链表，这样 $n$ 个结点共有 $n$ 个孩子链表，其中叶结点的孩子链表为空

那么 $n$ 个孩子链表共有 $n$ 个头指针，将这 $n$ 个头指针存放在数组中，数组中的每个元素为一表头结点

最后再将结点数、根结点在表头数组中的位置、表头数组封装，即得到一棵用单链表表示的树

对于给出的指定结点 p，很容易找到其所有孩子，但查找 p 的父结点只能从头到尾遍历整个数组

孩子表示法的存储结构描述如下

struct CTNode { //孩子结点
    int child; //孩子结点在数组中的下标
    struct CTNode *next; //下一个孩子
};
struct tableNode { //表头结点
    int data;
    struct CTNode *firstChild; //第一个孩子
};
struct CTree {
    int n;    //结点数
    int root; //根结点位置
    tableNode nodes[N]; //表头数组
} tree;

【孩子兄弟表示法】

孩子兄弟表示法，从存储结构上来看与二叉链表相同，但其存储结构不同，其链表中的每个结点除数据域外，还设置了两个指针分别指向该结点的第一个孩子和右兄弟

该表示法本质上是将树转化为二叉树，然后用二叉树的操作来对树进行操作

孩子兄弟表示法的存储结构描述如下

typedef struct CSNode {
    int data;
    struct CSNode *firstChild; //第一个孩子
    struct CSNode *nextSibling; //右兄弟
} CSNode, *CSTree;