树的存储结构
1.双亲表示法：以一组连续空间储存树的结点，同时在每个结点中附设一个指示器指示其父结点在数组中的位置，这是运用了每个结点只有一个父结点的逻辑。
#define MAX_TREE_SIZE 100
typedef struct PTNode//结点结构
{TElemType data;
int parent; //双亲位置域
}PTNode;
typedef struct//树结构
{ PTNode nodes[MAX_TREE_SIZE];
int r,n; //根的位置和结点数
}PTree;2.孩子表示法：由于树中的每个结点可能有多棵子树，则可用多重链表，即每个结点有多个指针域，其中的每个结点指向一棵子树的根结点，此时有俩种方案，一种是多重链表中的结点是同构的，每一个结点的孩子指针数为树的度d，明显不是所有结点的度都是d。第二种方法是每个结点都有一个degree域表明该结点的度，虽然节约空间但是操作麻烦。
更好的方法是把n个结点的n个孩子结点排列其来，用一个孩子链表存储起来，则树的结点结构中保存孩子链表的头指针就行。
typedef struct CTNode//孩子结点
{int child;
struct CTNode *next;
}*ChildPtr;
typedef struct
{TElemType data;
Childptr firstchild;//孩子链表头指针
}CTBox;
typedef struct
{ CTBox nodes[MAX_TREE_SIZE];
int n,r; //结点数和根的位置
}CTree;
孩子表示法和双亲表示法都能够表示树，但一个方便找孩子一个方便找双亲，如有需求也可结合起来。
3.孩子兄弟表示法：
又称二叉树表示法，或二叉链表表示法。结点中的两个链域分别指向该结点的第一个孩子和下一个兄弟结点。要访问第结点X的第i个孩子，则只需要找到它的第1个孩子结点，然后找i-1此孩子结点的右兄弟。如果要找结点的双亲结点也可在原结点结构中加入parent域。
typedef struct
{ElemType data;
struct CSNode *firstchild,*nextsibling;//左孩子右兄弟
}CSNode,*CSTree;
树、森林和二叉树的转换
由于树和二叉树都有以二叉链表表示，所以其物理结构相同，只是对这样的物理结构的解释不太一样，那么我们对其解释的逻辑图肯定也可以相互转换。森林是互不相交的树，其实让森林中最左边的树的根结点的孩子结点是右边一棵树的根结点，这不就满足树的定义中子树不相交的定义了，说明森林和树也是相互转换的，那么森林和二叉树也是相互转换的。
树转换为二叉树：树的二叉链表是储存左孩子右兄弟，二叉树是左右孩子，所以只需让每一个结点的第一个右兄弟都变成它的右孩子即可。
二叉树转换为树：所以只需让每一个结点的所有右孩子都变成它的父结点的右兄弟即可。
森林转换为二叉树：先把森林里的每个树转化为二叉树（这样的二叉树的根结点只会有一个孩子结点，因为原本根节点的所有右孩子结点都挨个转换下去了），那么我们把树二的根结点当作树一的右孩子结点就行了，同样树三的根结点当作树二的右孩子结点.....
二叉树转换为森林:从根结点开始,若右孩子存在,则断开右孩子与根结点的连接。右孩子结点也是此操作.这样就得到n个二叉树,再把二叉树转换为树即可。
树和森林的遍历
树的遍历：
- 先根遍历树：即先访问树的根结点，然后依次从左至右先根遍历根的每棵子树。
- 后根遍历树：先依次从左至右后根遍历每棵子树，再访问树的根结点。
没有中根遍历是因为树中每个结点的度不一样，没有左根右这样的方式了。
森林的遍历
- 先序遍历森林：先根遍历第一棵树，然后依次遍历剩下的树
- 中序（后序）遍历森林：后根遍历第一棵树，然后依次遍历剩下的树。
这里后序遍历和二叉树的中序遍历结果相同 ，原因其实是树也是可以用二叉链表作为储存结构。我们可以借用二叉树的前序遍历和中序遍历的算法来实现树的先序遍历和后序遍历。这是对树和森林这种复杂问题的简单解决方法。