博客

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

1.双亲表示法

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

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

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

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

2.孩子表示法

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

// 孩子表示法
#define MAX_SIZE 100
typedef int ElemType;
typedef 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;