树与森林

-树的存储结构

---

树的存储结构
树的存储方式有多种，可以采用顺序存储结构，也可以采用链式存储结构。

---

双亲表示法
这种存储方式采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。

//双亲表示法的存储结构
#define MAX_TREE_SIZE 100            //树中最多结点数
typedef struct{                      //树中结点定义
	ElemType data;                   //数据元素
	int parent;                      //双亲位置域
}PTNode;
typedef struct{                     //树类型的定义
	PTNode nodes[MAX_TREE_SIZE];    //双亲表示
	int n;                          //结点数
}PTree;

---

孩子表示法
孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，则N个结点就有N个孩子结点（叶子结点的孩子链表为空表）
对于这种存储方式寻找子女的操作非常直接，但是寻找双亲的操作需要遍历N个结点中孩子链表指针域所指向的N个孩子链表。

---

孩子兄弟表示法
孩子兄弟表示法又称为二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针和指向结点下一个兄弟结点的指针。

//孩子兄弟表示法的存储结构描述如下：
typedef struct CSNode{
	ElemType data;                           //数据域
	struct CSNode *firstchild,*nextsibling;  //第一个孩子和右兄弟指针
}CSNode,*CSTree;

这种存储表示法灵活，最大优点是可以方便的将树转换为二叉树，易于查找结点的孩子等，但缺点是从当前结点寻找其双亲结点比较麻烦。

---