树的存储结构分为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 版权协议,转载请附上原文出处链接和本声明。