树的存储
树的各种操作还是离不开树的存储的，其实树的存储才是最好玩的东西。
双亲表示法
假设以一组连续的空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置
#define MAX_TREE_SIZE 100
typedef struct //节点结构
{
TElemType data;
int parent; //双亲位置域
}PTNode;
typedef struct //树结构
{
PTNode node[MAX_TREE_SIZE];
int count; //根的位置和节点个数
}PTree;
这种存储结构利用了每个结点（除了根结点以外）只有唯一的双亲的性质，在查找双亲的操作中可以在O(1)内实现，对于查找根结点也不过多次找双亲，实现和时间复杂度都可以接受。 但是，如果要找孩子结点，要遍历整棵树！！！因此，数据结构和算法是相互服务的，看需求选择。
孩子表示法
由于每个结点可能有多个子树，则可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵树的根结点。 其实和二叉链表很像，但是不一定是几个叉，也就是说对于孩子指针域，个数不确定，那么我们也要重新考虑这个问题，设定几个指针，既然个数不确定，那用动态存储就比较好，那么，指针域用链表存储，那么实现存储一棵树就应该是这个样子：
实现虽然麻烦，但是这应该是最直观最好理解的存储方式，不作细总结了。
孩子兄弟表示法
孩子兄弟表示法又称二叉树表示法，或二叉链表表示法。即以二叉链表作树的存储结构。链表中结点的两个链域分表指向该结点的第一个孩子结点和下一个兄弟结点。是不是很炫酷。。。
typedef struct CSNode
{
TElemType data;
CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
其实就是左支保存孩子，右支保存兄弟，当想遍历所有孩子的时候，只需要先遍历左子树一次，然后遍历左子树的右子树到空就可以了。 如果只看孩子兄弟表示法不形象的话，参照孩子孩子表示法便可以知道存储的是什么样子的：
也就是有这样的存储结构，所以树和森林转换起来非常的方便。
森林和二叉树的转换
由于二叉树和树都可以用二叉链表作为存储结构，则以二叉链表作为媒介可导出树和二叉树之间的一个对应关系。也就是说，给定一棵树，可以找到一颗二叉树与之对应，从物理结构来看，它们的二叉链表是相同的，只是解释不同而已。
对于右面那棵树，即可以认为他是左面那可树的存储结构表示，也可以认为他本来就是一棵二叉树。 如果按照孩子兄弟表示法，我们可知，根结点的右支必为空（根没有兄弟），那么若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。 这个一一对应的关系导致森林或树与二叉树可以相互转换：
森林转换为二叉树
如果F={T1,T2,...,Tm}是森林，则可按如下规则转换成一棵二叉树B=(root,LB,RB)。
- 若F为空，即m=0，则B为空树
- 若F非空，即m！=0，则B的根root即为森林中第一棵树的根ROOT（T1）；B的左子树LB是从T1中根结点的子树森林F1={T11，T12，....，T1m1}转换而成的二叉树，其右子树RB是从森林F'={T2,T3,...,Tm}转换而成的二叉树
二叉树转换为森林
如果B=(root,LB,RB)是一棵二叉树，则可按如下规则转换成森林F={T1,T2,...,Tm}。
- 若B为空，则F为空
- 若B非空，则F中第一棵树T1的根ROOT（T1）即为二叉树B的根root；T1中根结点的子树森林F1是由B的左子树LB转换而成的森林；F中除T1之外其余树组成F'={T2,T3,...,Tm}是由B的右子树RB转换而成的森林。
明显，上述算法为递归算法。
树和森林的遍历
已知二叉树有三种遍历方式，因为树和森林都可以用二叉链表，因此树和森林的遍历的实现也算是依靠着树的遍历实现的。 由树结构的定义可引出两种次序遍历树的方法，一种是先根遍历树，即：先访问树的根结点，然后依次访问先根遍历根的每一棵树；另一种是后根遍历，即：先依次后根遍历每一棵树，然后访问根结点。 按照森林和树的相互递归关系，我们可以推出森林的两种遍历方法：
先序遍历森林
若森林非空，则可按照下述规则遍历之：
- 访问森林第一棵树的根结点
- 先序遍历第一棵树中根结点的子树森林
- 先序遍历除去第一棵树之后剩余的树构成的森林
中序遍历森林
若森林非空，则可按照下述规则遍历之：
- 中序遍历森林中的第一棵树的根结点的子树森林
- 访问第一棵树的根结点
- 中序遍历除去第一棵树之后剩余的树构成的森林
其实说白了，森林的先序和中序遍历分别对应了二叉树的先序和中序遍历（当用孩子兄弟表示法的时候）。
