【树的存储结构,孩子链表】

树和森林

森林：是m(m>=0)棵互不相交的树的集合。

树的存储结构

1.双亲表示法
实现：定义结构数组存放树的结点，每个结点含两个域。
数据域：存放结点本身信息。
双亲域：指示本结点的双亲结点在数组中的位置。

表示出来就是：

特点：找双亲容易，找孩子难。

#define TElemType int
#define MAX_TREE_SIZE 100//定义
typedef struct PTNode {TElemType data;int parent;//双亲域位置
}PTNode;//树结构
typedef struct {PTNode nodes[MAX_TREE_SIZE];int r, n;//根结点的位置和结点个数
}PTree;

孩子链表

把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存，则n个结点有n个孩子链表（叶子的孩子链表为空表）。而n个头指针又组成一个线性表，用顺序表（含n个元素的结构数组）存储。

//树结构
typedef struct {PTNode nodes[MAX_TREE_SIZE];int r, n;//根结点的位置和结点个数
}PTree;//孩子结点
typedef struct CTNode {int child;struct CTNode* next;
}*ChildPtr;//双亲结点
typedef struct {TElemType data;ChildPtr firstchild;//孩子链表头指针}CTBox;

带孩子的双亲链表