数据结构学习：树，二叉树和森林
树是一种递归定义的的数据结构
双亲表示法（顺序存储）
每个结点中保存指向双亲的指针
// 双亲表示法
#define Max_TREE_SIZE 100 //树中最多结点数
typedef struct //树的定义
{
ElemType data; //数据元素
int parent; //双亲
}PTNode;
typedef struct //树的类型定义
{
PTNode node[Max_TREE_SIZE]; //双亲表示
int n; //结点数
}PTree;
孩子表示法（顺序+链式存储）
// 孩子表示法
struct CTNode
{
int child; //孩子结点在数组中的位置
struct CTNode *next; //下一个结点
}
typedef struct
{
ElemType data;
struct CTNode *firstChild;//第一个孩子
}CTBox;
typedef struct
{
CTBox nodes[Max_TREE_SIZE];
int n,r; //结点数和根的位置
}CTree;
孩子兄弟表示法（链式存储）
树与二叉树的转化（孩子兄弟表示法）
树中结点的左指针指向第一个孩子，右指针指向右边第一个兄弟，即可转化为二叉树
森林转化为二叉树
先把每一棵树都转化为二叉树，再连起来
Eg:
–>
二叉树转化为森林
二叉树的每一层的最右边的结点是森林中树的根节点
Eg:
树的先根遍历
//树的先根遍历，若树不为空，先访问根节点，再依次对每棵子树进行先根遍历
// 伪代码
void PreOrder(TreeNode *R)
{
if(R != NULL)
{
visit(R); //访问根节点
while(R还有下一棵未访问的子树T)
PreOrder(T); //先根遍历下一棵子树
}
}
树的后根遍历与其对应二叉树的中序遍历序列相同
// 树后根遍历
void PostOrder(TreeNode *R)
{
if(R != NULL)
{
while(R还有下一棵未访问的子树T)
PostOrder(T);
visit(R);
}
}
树的层析遍历（用队列实现）
先序遍历森林（与对应二叉树的先序遍历一样）
若森林非空：
访问森林的第一棵树的根节点
先序遍历第一棵树中根节点的子树森林
先序遍历除去第一棵树之后的剩余的树构成的森林
中序遍历森林（效果等同于对应二叉树的中序遍历）
若森林非空：
中序遍历森林中第一棵树的根节点的子树森林
访问森林的第一棵树的根节点
中序遍历除去第一棵树之后的剩余的树构成的森林