【数据结构】树的三种存储结构

  • Post author:
  • Post category:其他


树的存储结构分为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;



版权声明:本文为qq_32139191原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。