@[toc]
关于树和二叉树的内容确实是非常多啊，没想到加上这篇已经有三篇了，这篇文章我将会把剩余的树和二叉树的内容全部介绍完，还有一个哈夫曼树的内容，我将单独写一篇专栏文章介绍。
森林的定义
前面的文章中提到了树的定义，我们说树是一个递归的定义，树由若干子树构成，其中的每一棵子树又由若干子树构成。
那么森林是什么呢？
森林是m(m ≥ 0)棵互不相交的树的集合
树的存储结构
下面介绍树的存储结构，对于树的存储结构，它有以下三种实现方式：
- 双亲表示法
- 孩子表示法
- 孩子兄弟表示法
双亲表示法
双亲表示法的关键就是双亲了，对于除根结点外的任意结点，它都有唯一的双亲结点，所以树的结构定义应为：
#define MAX_SIZE 10
typedef struct PTNode{
char data;
int parent; //双亲位置域
}PTNode;
typedef struct{
PTNode nodes[MAX_SIZE];
int r; //根结点的位置
int n; //树的结点个数
}PTree;
比如这样的一个数组：
通过双亲位置域很容易知道，这棵树的根结点为R，又因为A、B、C的双亲位置域均为0，而下标0表示根结点R，所以根结点R下有三棵子树，以此类推，这棵树的结构为：
双亲表示法的特点是：找双亲易，找孩子难。
孩子表示法
孩子表示法的意思是：
把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存储，则n个结点有n个孩子链表(叶子的孩子链表为空表)。而n个头指针又组成一个线性表，用顺序表存储。
比如这棵树：
其用孩子表示法表示结果如下：
先看根结点，根结点R有三个孩子结点，所以R结点结构中的指针域存放其第一个孩子结点位置，然后这三个孩子组成一个单链表，该单链表结点中的数据域存放结点在数组中的位置，以此类推。
所以树的结构定义应为：
//孩子结点结构
typedef struct CTNode{
int child;
struct CTNode *next;
}*ChildPtr;
//双亲结点结构
typedef struct{
char data;
ChildPtr firstChild; //存储第一个孩子结点的头指针
}CTBox;
typedef struct{
CTBox nodes[MAX_SIZE];
int r,n; //根结点位置和结点数
}CTree;
孩子表示法的特点是：找孩子易，找双亲难。
孩子兄弟表示法
什么是孩子兄弟表示法呢？
用二叉链表作为树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。
比如下面的一棵树：
如何用孩子兄弟法进行表示呢？
先看根结点，根结点R有三个孩子，无兄弟结点，所以应该让根结点的一个指针域指向第一个孩子结点A，另一个指针域为空。
再看结点A，结点A有两个孩子，一个兄弟结点，所以让结点A的一个指针域指向第一个孩子结点D，另一个指针域指向兄弟结点B。
以此类推，整棵树的表示结果如下：
其结构定义如下：
typedef struct CSNode{
char data;
struct CSNode *firstChild,*nextSibling;
}CSNode,*CSTree;
孩子兄弟表示法的特点：找孩子兄弟易，找双亲难。
树与二叉树的转换
到这里，树、二叉树和森林的讲解就结束了，下面还需要介绍一下树、二叉树、森林之间的相互转换，先讲讲树转换为二叉树。
树转换为二叉树
树要想转换为二叉树，需要一下步骤：
- 加线：在兄弟结点之间加上一条连线
- 去线：对每个结点，除了其左孩子外，去除与其它孩子结点之间的连线
- 旋转：以树的根结点为轴心，将整棵树顺时针旋转45°
总结为一句口诀：兄弟相连留长子。
比如下面的一棵树：
我们试着将这棵树转换为二叉树。
第一步，先将兄弟结点之间连上线：
第二步，去掉除左孩子外其它孩子结点的连线，比如根结点A只保留与结点B的连线，结点B只保留与结点E的连线，结点D只保留与结点H的连线：
此时作适当的旋转，最终结果为：
二叉树转换为树
知道了如何将树转换为二叉树后，将二叉树转换为树就非常简单了，需要进行如下步骤：
- 加线：若p结点是双亲结点的左孩子，则将p结点的右孩子，右孩子的右孩子......沿分支找到所有右孩子，都与p的双亲用线连起来
- 去线：去除原二叉树中双亲与右孩子的连线
- 调整：将结点按层次排列，形成树结构
总结为一句口诀：左孩右右连双亲，去掉原来右孩线。
比如下面的一棵二叉树：
如何将这棵二叉树转换为树呢？
第一步，加线。找到某个结点的左孩子，如根结点A的左孩子为结点B，然后将结点B的右孩子，右孩子的右孩子，右孩子的右孩子的右孩子......都与其双亲结点A用线连接起来，其它结点的操作也是如此。
第二步，去线。去掉原来的右孩子之间的连线，比如结点B的右孩子，结点C和结点D之间的连续可以去除。
此时进行适当调整使其层次分明，最终结果为：
森林与二叉树的转换
下面介绍森林与二叉树的相互转换，先说说如何将森林转换为二叉树。
森林转换为二叉树
要想将森林转换为二叉树，需要进行如下步骤：
- 将各棵树分别转换为二叉树
- 将每棵树的根结点用线相连
- 以第一棵树的根结点为二叉树的根，再以根结点为轴心，顺序针旋转
总结为一句口诀：树变二叉根相连。
比如下面的一个森林：
如何将该森林转换为一棵二叉树呢？
第一步，先将森林中的每棵树都转换为二叉树，树转二叉树相信已经难不倒大家了，结果如下：
第二步，将每棵二叉树的根结点用线连接在一起。
最后做适度的旋转进行调整，最终结果如下：
二叉树转换为森林
反过来，如何将二叉树转换为森林呢？需要进行如下步骤：
- 去线：将二叉树中的根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间的连线全部去除，使之变为孤立的二叉树
- 还原：将孤立的二叉树还原成树
总结为一句口诀：去掉全部右孩线，孤立二叉再还原。
比如上面的这棵二叉树：
我们如何将其转换为森林呢？
第一步，将根结点的右孩子之间的连线全部去除。
这样，一棵二叉树就被分为了三棵孤立的二叉树。
第二步，将每棵二叉树均转换为树，二叉树转换为树在前面也已经介绍过了，直接贴出最终结果：
树的遍历
前面介绍过二叉树的遍历，其有四种遍历方式：
- 先序遍历
- 中序遍历
- 后序遍历
- 层次遍历
而树有三种遍历方式：
- 先序遍历
- 后序遍历
- 层次遍历
它与二叉树的区别是，树没有中序遍历方式，为什么呢？
原因其实很简单，看这样的一棵树：
我们说中序遍历需要知道子树中的根结点是谁，而这棵树种，根结点A共有三个孩子结点，我们就无法确定哪个结点为中间的根结点了。
举个例子，比如下面的一棵树：
其先序遍历结果是怎样的呢？
首先访问根结点A，然后继续先序遍历各个子树。
子树B，先访问根结点B，结点B已无子树，遍历结束。
子树C，先访问根结点C，然后继续先序遍历结点C的子树D，先访问根结点D，结点D已无子树，遍历结束。
子树E，先访问根结点E，结点E已无子树，遍历结束。
综上所述，先序遍历序列为：A B C D E。
再看后序遍历结果：
先遍历根结点的子树，再访问根结点。
子树B，先遍历其子树，因其无子树，所以直接访问根结点B。
子树C，先遍历其子树，结点C的子树D无子树，所以直接访问根结点D。
此时结点C的子树遍历完成，接着访问根结点C。
子树E，因其无子树，所以直接访问根结点E。
最后访问根结点A。
综上所述，后序遍历序列为：B D C E A。
最后看层次遍历：
层次遍历非常简单，从上到下，从左到右，遍历结果为：A B C E D。
森林的遍历
最后是森林的遍历，森林的遍历也很简单，其遍历方式有：
- 先序遍历
- 中序遍历
看下面的一个森林：
先看先序遍历结果：
我们将第一棵树的根结点视为整个森林在遍历过程中的根结点。
先访问根结点A，然后先序遍历其子树。
子树B，因其无子树，所以直接访问根结点B。
子树C，无子树，直接访问根结点C。
子树D，无子树，直接访问根结点D。
此时第一棵树遍历完成，我们继续将第二棵树的根结点视为接下来的森林在遍历过程中的根结点。
先访问根结点E，然后先序遍历其子树。
子树F，无子树，直接访问根结点F。
此时第二棵树遍历完成，继续讲第三棵树的根结点视为接下来遍历过程中的根结点。
先访问根结点G，然后先序遍历其子树。
子树H，无子树，直接访问根结点H。
子树I，先访问根结点I，然后先序遍历其子树，结点I的子树J无子树，直接访问根结点J。
综上所述，该森林的先序遍历结果为：A B C D E F G H I J。
再来看中序遍历结果：
我们仍然将第一棵树的根结点视为整个森林遍历过程中的根结点，首先中序遍历根结点的子树。
子树B、子树C、子树D均无子树，直接访问根结点B、C、D。
此时根结点A的子树已遍历完成，接下来访问根结点A，然后中序遍历其它部分。
我们再将第二棵树的根结点视为接下来遍历过程中的根结点，先遍历子树，访问结点F，再访问根结点E。
最后是第三棵树，按照同样的遍历方式，结果为：H J I G。
综上所述，该森林的后序遍历结果为：B C D A F E H J I G。
其实，我们只需对每棵树进行后序遍历即可得到最终遍历结果。
