理论基础 —— 树 —— 树的存储结构

【父亲表示法】

由于树中每个结点均有且仅有一个父结点，那么根据这一特性，用一维数组来存储树的各个结点（一般按层序存储），数组中的一个元素对应树中的一个结点，每个结点记录两类信息：结点的数据信息、该结点的父亲在数组中的下标

优缺点：利用了树中除根结点外每个结点都有唯一的父结点这个性质，很容易找到树根，但找孩子时需要遍历整个线性表

template<class T>
struct Node{
    T data;//数据域，存放该结点的数据信息
    int parent;//指针域，指向该结点的父结点
}tree[N];

【孩子表示法】

树的孩子表示法是基于链表的存储方法，其缺陷是只能从父结点遍历到子结点，不能从某个子结点返回到它的父结点，有两种形式：

1.多重链表表示法

由于树中的每个结点都可能有多个孩子，因此链表中的每个结点都包含一个数据域与多个指针域，每个指针域指向该结点的一个孩子结点。

由于树中各节点的度不同，因此指针域的设置有两种方法：

• 指针域的个数等于该结点的度：节省空间但各种操作不易实现，适用于各节点的度相差较大、操作较少的情况
• 指针域的个数等于树的度：浪费空间但各种操作容易实现，适用于各节点的度相差不大、操作较多的情况

//指针域的个数等于该结点的度
template<class T>
struct Node{
    T data;//数据域，存放数据信息
    int degree;//度域，存放该结点的度
    int child[degree];//指针域，child[i]指向该结点的第i个孩子
}tree[N];
//指针域的个数等于树的度
template<class T>
int num;//num为树的度
struct Node{
    T data;//数据域，存放数据信息
    int child[num];//指针域，child[i]指向该结点的第i个孩子
}tree[N];

2.孩子链表表示法

用多个单链表来表示树，将每个结点的孩子结点进行排列，看成一个线性表，并以单链表存储，称为该结点的孩子链表。

那么，n 个结点共有 n 个孩子链表，其中叶结点的孩子链表为空，即 n 个单链表共有 n 个头指针，这 n 个头指针又组成了一个线性表，将这存放 n 个头指针的数组和存放 n 个结点的数组结合起来，构成孩子链表的表头数组

struct childNode{//孩子结点
    int child;
    childNode *next;
};
template<class T>
struct tableNode{//表头结点
    T data;
    childNode *firstChild;
};

【父亲孩子表示法】

父亲孩子表示法是父亲表示法、孩子链表表示法的结合。

父亲孩子表示法仍将各结点的孩子分别组成单链表，同时用一维数组顺序存储树中的各节点，数组元素除了包括结点的数据信息和该结点的孩子链表的头指针外，还增设一指针域用于该结点的父结点在数组中的下标。

template<class T>
struct Node{
    T data;//数据域，存放数据信息
    Node<T> *child[m];//指针域，指向若干孩子结点
    Node<T> *father;//指针域，指向父亲结点
};

【孩子兄弟表示法】

孩子兄弟表示法又称二叉链表表示法，是一种双链表结构，其链表中的每个结点除数据域外，还设置了两个指针分别指向该结点的第一个孩子和右兄弟。

template <class T>
struct Node{
    T data;//数据域，存放数据信息
    Node<T> *firstChild;//指针域，存放该结点第一个孩子结点的地址
    Node<T> *rightBrother;//指针域，存放该结点的右兄弟的地址
};