16.0、C语言数据结构——树、森林、二叉树
普通树转换成二叉树 ：
步骤如下 ->
- 加线，在所有兄弟结点之间加一条线；
- 去线，在树种每个结点，只保留他与第一孩子结点的连线，删除他与其他孩子结点之间的连线；
- 层次调整，以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明；
树转换成相应的二叉树分为两个步骤：
第一步：在树种所有的兄弟结点之间加一条连线；
第二步：对每个结点，除了保留与其长子的连线外，去掉该结点与其他孩子的连线；
森林转换为二叉树：
第一步：先将森林中的每棵树变为二叉树；
第二步：第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点，将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树；
二叉树到树、森林的转换：
其实就是逆过程->
第一步：若结点 x 是其双亲 y 的左孩子，则把 x 的右孩子，右孩子的右孩子，......都与y用线连起来；
第二步：去掉所有双亲到右孩子之前的连线；判断一棵二叉树能够转换成一棵树还是森林，标准很简单，那就是只要看着棵二叉树的根结点有没有右孩子，有的话就是森林，没有的话就是一棵树；
数和森林的遍历：
树遍历分为两种方式：一种是先根遍历，另一种是后根遍历；
先根遍历：先访问树的根结点，然后再一次先根遍历根的每棵子树；
后根遍历：先依次遍历每棵子树，然后在访问根结点；
先根遍历结果为 ： A B E F C G D H I J
后根遍历结果为 ： E F B G C H I J D A
森林的遍历也分为前序遍历和后序遍历，其实就是按照树的先根遍历和后根遍历依次访问森林的每一棵树；
我们惊人的发现：树、森林的前根（序）遍历和二叉树的前序遍历结果相同，树、森林的后根（序）遍历和二叉树的中序遍历的结果相同；
最后补充一个知识点：线索二叉树
- 为什么需要线索二叉树呢？
- 我想正如程序员发觉单链表并不总能满足他们设计的程序某些要求我的时候，发明了双向链表来弥补一样，线索二叉树也是在需求中被创造的！
线索二叉树每个结点结构如下所示 ->
- ltap 为 0 的时指向该结点的左孩子，为 1 时指向该结点的前驱；
- rtag 为 0 的时指向该结点的右孩子，为 1 时指向该结点的后继；