一文弄懂3种树的存储结构

树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树中的某个结点的孩子可以有多个，所以仅仅使用简单的顺序结构或者链式结构是不能完全表示一整棵树的。充分利用顺序存储结构和链式存储结构的特点，完全可以实现对树的存储结构的表示。

树的存储结构可以分为3种：双亲表示法，孩子表示法和孩子兄弟表示法

1.双亲表示法

采用的一组连续的存储空间来存储每个节点。以双亲作为索引的关键词的一种存储方式。每个结点只有一个双亲，所以选择顺序存储占主要。

根节点没有双亲，所以其在数组中存储的值为-1。

其余的节点，只需要存储其父节点对应的数组下标即可。

代码解释：

// 双亲表示法#define MAX_SIZE 100typedef int ElemType;
typedef struct PTNode{
    ElemType data;
    int parent;}PTNode;
typedef struct PTree{
    PTNode nodes[MAX_SIZE];
    int n;}PTree;

 2.孩子表示法

将每个节点的孩子节点都用单链表连接起来形成一个线性结构，n个节点具有n个孩子链表。由于每个结点可有多个子树（无法确定子树个数），可以考虑使用多重链表来实现。

代码解释：

// 孩子表示法typedef int ElemType;#define MAX_SIZE 100typedef struct CNode{
    int child;
    struct CNode *next;}CNode;
typedef struct PNode{
    ElemType data;
    struct CNode *child;}PNode;
typedef struct CTree{
    PNode nodes[MAX_SIZE];
    int n;}CTree;

3.孩子兄弟表示法

以二链表作为树的存储结构，又称二叉树表示法。任意一棵树，他的结点的第一个孩子如果存在就是唯一结点，他的右兄弟如果存在，也是唯一的，因此，我们设置两个指针，分别指向该结点的第一个孩子和该结点的右兄弟。

使用孩子兄弟表示法需要将树转换为二叉树。

转换前：

转换后：

代码解释：

typedef int ElemType;typedef struct Node{
    ElemType data;
    struct Node *FirstChild;
    struct Node *NextBrother;
    }Node,TREE;

以上就是3种树的存储结构，顺序结构或者链式结构只能表示一棵树的部分结构，只有结合双亲表示法，孩子表示法和孩子兄弟表示法才能完整的表示出一颗树的结构。对于树的顺序结构和者链式结构在本站的数据结构和算法教程中有更加详细的讲解，感兴趣的小伙伴不要错过哦。