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

树和森林

森林：是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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

孩子链表

把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存，则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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

带孩子的双亲链表