树和森林，森林和二叉树的转换，树和森林的遍历

1 树的存储结构

1）双亲表示法用一组连续的存储空间来存储树的结点，同时在每个结点中附加一个指数器（整数域），用以指示双亲结点的位置（下标值）。

typedef int ElemType;
typedef struct PTNode {
    ElemType data;
    int parent;
} PTNode;
typedef struct {
    PTNode nodes[MAXSIZE];
    int root;//根结点位置
    int num;//结点数
} Ptree;

利用了任一结点的父结点唯一的性质。可以方便地直接找到任一结点的父结点，求结点的子结点时需要扫描整个数组。

2）孩子链表表示法树中每个结点有多个指针域，每个指针指向其一颗子树的根结点。有两种结点结构
①定长结点结构
指针域的数目就是树的度。其特点是：链表结构简单，但指针域的浪费明显。在一棵有n个结点，度为k的树中必有n(k-1)+1个空指针域。
②不定长结点结构
树中每个结点的指针域数量不同，是该结点的度。没有多余的指针域，操作不便。
③复合链表结构
对于树中的每个结点，其孩子结点用头结点的单链表表示。
n个结点的树有n个（孩子）单链表（叶子结点的孩子链表为空），而n个头结点又组成一个线性表且以顺序存储结构表示。

typedef struct listNode {
    int childNo;//孩子结点编号
    struct listNode *next;
} CTNode;//表结点结构
typedef struct {
    ElemType data;
    CTNode *firstChild;
} HNode;//头结点结构
typedef struct {
    HNode nodes[MAXSIZE];
    int root;//根结点位置
    int num;//结点数
} CLinkList;//头结点结构

3）孩子兄弟表示法这是一种常用的存储结构。在树中，每个结点除其信息域外，再增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针。两个指针域:分别指向结点的第一个子结点和下一个兄弟结点。

typedef int ElemType;
typedef struct CSnode {
    ElemType data;
    struct CSnode *firstchild, *nextsibing;//第一个孩子结点，亲兄弟结点
} CSNode;

孩子兄弟表示法

2 森林和二叉树的转换

由于二叉树和树都可用二叉链表（孩子兄弟表示法）作为存储结构，对比各自的结点结构可以看出，以二叉链表作为媒介可以导出树和二叉树之间的一个对应关系。
从物理结构来看，树和二叉树的二叉链表是相同的，只是对指针的逻辑解释不同而已。
从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树一定为空。(因为根结点只有孩子，没有兄弟)

1)树转换为二叉树
对于一棵无序树，树中结点的各孩子的次序是无关紧要的，而二叉树中结点的左、右孩
子结点是有区别的。为避免发生混淆，约定树中每一个结点的孩子结点按从左到右的次序顺序编号。将一棵树转换为二叉树的方法是:
(1)树中所有相邻兄弟之间加一条连线;
(2)对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线;
(3)以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层次分明。可以证明，树作这样的转换所构成的二叉树是唯一的。由转换过程可以看出，在二叉树中，左分支上的各结点在原来的树中是父子关系，而右分支上的各结点在原来的树中是兄弟关系。
由于树的根结点没有兄弟，所以变换后的二叉树的根结点的右孩子必为空。
事实上，一棵树采用孩子兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表
存储结构是完全相同的。
举例:将下列树转换成二叉树。

转换过程:
加线:在兄弟之间加一连线;

抹线:对每个结点，除了其左孩子外，去除其与其余孩子之间的关系;

旋转:以树的根结点为轴心，将整树顺时针转 45°

2)二叉树转换为树的过程
(1) 加虚线。若某结点i是其父结点的左子树的根结点，则将该结点i的右子结点以及沿右子链不断地搜索所有的右子结点，将所有这些右子结点与 i 结点的父结点之间加虚线相连。
(2) 去连线。去掉二叉树中所有父结点与其右子结点之间的连线。
(3) 规整化。将图中各结点按层次排列且将所有的虚线变成实线。

3)森林转换为二叉树
由森林的概念可知，森林是若干棵树的集合，只要将森林中各棵树的根视为兄弟，每棵树又可以用二叉树表示，这样，森林也同样可以用二叉树表示。

4)二叉树还原为森林
(1) 去连线。将二叉树的根结点与其右子结点以及沿右子结点链方向的所有右子结点的连线全部去掉，得到若干棵孤立的二叉树，每一棵就是原来森林 F中的树依次对应的二叉树。
(2)将各棵孤立的二叉树按二叉树还原为树的方法还原成一般的树。

image.png

3 树和森林的遍历

1.树的遍历
(1)先序遍历：先访问根结点，然后依次先序遍历完每棵子树。
(2)后序遍历：先依次后序遍历完每棵子树，然后访问根结点。
由于不分左右子树，所以无中序遍历。

总结：对于一颗树的先序遍历等于转变为二叉树后的先序遍历；
对于一棵树的后序遍历等于转变为二叉树后的中序遍历。

2.森林的遍历
(1)先序遍历：按先序遍历树的方式依次遍历森林中的每棵树。
(2)中序遍历：按后序遍历树的方式依次遍历森林中的每棵树。（注意定义为中序遍历）