5-6 树和森林

树（Tree）是n（n≥0）个结点的有限集。若n=0，称为空树；

若n>0：

1. 有且仅有一个特定的称为根（Root）的结点；
2. 其余结点可分为m（m≥0）个互不相交的有限集$T_1,T_2,T_3,...,T_m$

森林

森林是m（m≥0）棵互不相交的树的集合

树的存储结构

双亲表示法：

实现：定义结构数组。存放树的结点，每个结点含两个域：

• 数据域：存放结点本身信息
• 双亲域：指示本结点的双亲结点在数组中的位置

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

结点代码：

typedef struct PTNode {
	TElemType data;
	int parents; //双亲位置域
}PTNode;

树结构：

#define MAX_TREE_SIZE 100
typedef struct {
	PTNode nodes[MAX_TREE_SIZE};
	int r,n; //r为根结点的位置，n为结点个数
}PTree;

5-6 树的存储结构(2)

孩子链表

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

孩子结点结构：

typedef struct CTNode {
	int child; //存储孩子在顺序表中的下标
	struct CTNode *next;
}*ChildPtr;