目录：

• 一、树的存储结构
• • （一）双亲表示法
  • （二）孩子链表表示法（带双亲的孩子链表-parent）
  • （三）树的二叉链表（孩子-兄弟）存储表示法
• 二、森林与二叉树的转换
• • （一）将树转换成二叉树
  • （二）将二叉树转换成树
  • （三）将森林转换成二叉树
  • （四）将二叉树转换成森林
• 三、树和森林的遍历
• • （一）树的遍历（不讨论中序）
  • （二）森林的遍历（不讨论后序）

一、树的存储结构

（一）双亲表示法

实现： 定义结构数组来存储树的结点，每个结点含有两个域：
数据域：存放结点本身信息
双亲域：指示本结点的双亲结点在数组中的位置

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

#define MAX_TREE_SIZE 100
typedef struct PTNode
{ //结点结构
	ElemType data;
	int parent;//保存双亲位置
}PTNode;

typedef struct
{ //定义树结构
	PTNode nodes[MAX_TREE_SIZE];
	int r, n;//根的位置和结点数
}PTree;

（二）孩子链表表示法（带双亲的孩子链表-parent）

//孩子链表表示法的类型描述
typedef struct CTNode
{ 
	int child;
	struct CTNode* nextchild;
}*ChildPtr;
//双亲结点结构
typedef struct
{ 
	ElemType data;
	int parent;//保存双亲位置
	ChildPtr firstchild;//孩子链的头指针
}CTBox;
//树结构
typedef struct
{ 
	CTBox nodes[MAX_TREE_SIZE];
	int n, r;//结点数和根结点的位置
}CTree;

（三）树的二叉链表（孩子-兄弟）存储表示法

typedef struct CSNode
{ 
	ElemType data;
	struct CSNode* firstchild, * nextsibling;
}CSNode,*CSTree;

二、森林与二叉树的转换

（一）将树转换成二叉树

加线： 在兄弟之间加一条连线
抹线： 对每个结点，除了其最左边孩子外，去除其与其余孩子之间的关系
旋转： 以树的根结点为轴心，将整树顺时针旋转45度。

树转换成的二叉树，根结点的右子树一定为空

（二）将二叉树转换成树

加线： 若p结点是双亲结点的左孩子，则将P的右孩子，右孩子的右孩子·····沿着分支找到的所有右孩子，都与p的双亲用线连起来
抹线： 抹掉原二叉树中双亲与右孩子之间的连线
调整： 将结点按层次排列，形成树的结构

（三）将森林转换成二叉树

1、将各棵树分别转换成二叉树
2、将每棵树的根结点用线连接起来
3、以第一棵树的根结点为二叉树的根，再以根结点为核心，顺时针旋转，构成二叉树形结构

（四）将二叉树转换成森林

抹线： 将二叉树中根结点与其右孩子连线，以及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立二叉树
还原： 将孤立的二叉树还原成树

三、树和森林的遍历

遍历： 按照一定规律走遍树的各个顶点，且使每个顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列

（一）树的遍历（不讨论中序）

常用方法：
1、先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树
2、后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点
3、按层次遍历：先访问第一层上的结点，然后依次遍历第二层，·····，第N层的结点。

（二）森林的遍历（不讨论后序）