1.树的定义

• 具有相同特性的数据元素的集合，当数据元素的个数为0时称之为空树，否则，存在一个唯一的称之为根的数据元素，
  当数据元素超过1时，其余的节点可以分为m个互不相交的有限集合，每个集合是树根的一个子树，下图，即都是A的子树；
• 树是二叉树的扩展，每个节点有且只有一个双亲，树中有0个或者多个孩子节点，但是二叉树最多只有2个节点
  

2.森林的定义

• 若干颗互不相交的子树的集合，由根节点和三个子树构成
  
• 表示方法
  

3.森林的存储结构

• 数的双亲表示法

#define MAX_TREE_SIZE 100
typedef struct PTNode
{
	DataType data;//数据域
	int parent;//双亲域
}PTNode;

typedef strucy PTree
{
	PTNode nodes[MAX_TREE_SIZE];//结构数组
	int r,n;
}PTree;

eg：F节点的双亲节点下标是1，即就是B，根节点没有双亲，就用1表示

• 树的孩子表示法

typedef struct CTNode//孩子节点
{
	int child;
	struct CTNode *next;
}CTNode;

typedef struct CTBox
{
	DataType data;
	CTNode *firstchild;
}CTBox;

typedef struct CTree
{
	CTBox nodes[MAX_TREE_SIZE];//结构数组
	int n,r;
} CTree;

eg：以A节点为头节点，引出一个链表，链表中就是A的孩子在这个数组中存放的位置

• 树的双亲孩子表示法：结合上面的双亲表示法和孩子表示法
  

• 树的孩子兄弟表示法

结点结构描述如下：
typedef struct CSNode
{
	DataType data;
	struct CSNode *firstchild, *nextsibling;//firstchild指向当前节点的第一个孩子节点，
									//nextsibling指向当前节点的下一个节点的兄弟节点
} CSNode;

eg：

4.森林的存储结构：非重点

• 双亲表示法
• 孩子表示法
• 孩子兄弟表示法

5.树及森林和二叉树的相互转换

• 转换的基础：由于二叉树，树都可以用二叉链表作存储结构，只是指针的含义不同，对于一棵树，可以到找一颗二叉树与之对应，物理存储方式是一样的，只是解释不同而已

• 树转化成二叉树的操作：经过图中的三步
  结论：树转换成的二叉树其根结点的右子树一定为空
  
  
  

• 二叉树转化成树的操作：经过图中的三步
  
  
  

• 森林转化成二叉树
  

• 二叉树转化成森林
  

6.树的遍历方法

遍历方法

• 先根（序）遍历：首先访问树根，再依次先根遍历每一颗子树
• 后根（序）遍历：首先后跟序每一科子树，然后再访问根
• 层次遍历：先访问根节点，然后依次遍历第二层到第n层的节点
  

7.森林的遍历方法

• 先序遍历
  先访问森林中第一颗树的根节点，先序遍历第一颗树的子树森林，最后，先序遍历除了第一颗树以外的剩下的森林
• 中序遍历
  先中序遍历第一颗树的根节点的子树森林，再访问第一颗树的根，再中序遍历剩下的森林