树、森林

树的存储结构

树的存储方式有多种，既可采用顺序存储结构，又可采用链式存储结构，但无论采用何种存储方式，都要求能唯一地反映树中各结点之间的逻辑关系，这里介绍 3 种常用的存储结构。

双亲表示法（顺序存储）

这种存储方式采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。根结点下标为 0，其伪指针域为 -1。

双亲表示法的存储结构描述如下：

#define MAX_TREE_SIZE 100
typedef struct {
    int data;     // 数据元素
    int partent;  // 双亲位置域
} PTNode;
typedef struct {
    PTNode nodoes[MAX_TREE_SIZE];  // 双亲表示
    int n;                         // 结点数
} PTree；

孩子表示法（顺序+链式存储）

孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时 个结点就有 个孩子链表（叶子结点的孩子链表为空表）。这种存储方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历 个结点中孩子链表指针域所指向的 个孩子链表。

#define MAX_TREE_SIZE 100
struct CTNode {
    int child;            // 孩子结点在数组中的位置
    struct CTNode *next;  // 下一个孩子
};
typedef struct {
    int data;
    struct CTNode *firstChild;  // 第一个孩子
} CTBox;
typedef struct {
    CTBox nodes[MAX_TREE_SIZE];
    int n, r;  // 结点数和根的位置
} CTree;

孩子兄弟表示法（链式存储）

孩子兄弟表示法又称二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针，及指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点）。

typedef struct CSNode {
    int data;
    struct CSNode *firstchild, *nextsibling;  // 第一个孩子和右兄弟指针
} CSNode, *CSTree;

这种存储表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作，易于查找结点的孩子等，但缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个 parent 域指向其父结点，则查找结点的父结点也很方便。

树、森林与二叉树的转换

由于二叉树和树都可以用二叉链表作为存储结构，因此以二叉链表作为媒介可以导出树与二叉树的一个对应关系，即给定一棵树， 可以找到唯一的一棵二叉树与之对应。从物理结构上看，它们的二叉链表是相同的，只是解释不同而已。

树转换为二叉树的规则：每个结点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则又称“左孩子右兄弟”。由于根结点没有兄弟，所以对应的二叉树没有右子树。

树转换成二叉树的画法：

1. 在兄弟结点之间加一连线；
2. 对每个结点，只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉；
3. 以树根为轴心，顺时针旋转45°。

将森林转换为二叉树的规则与树类似。先将森林中的每棵树转换为二叉树，由于任何一棵和树对应的二叉树的右子树必空，若把森林中第二棵树根视为第一棵树根的右兄弟，即将第二棵树对应的二叉树当作第一棵二叉树根的右子树，将第三棵树对应的二叉树当作第二棵二叉树根的右子….以此类推，就可以将森林转换为二叉树。

森林转换成二叉树的画法：

1. 将森林中的每棵树转换成相应的二叉树
2. 每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线；
3. 以第一棵树的根为轴心顺时针旋转45°。

二叉树转换为森林的规则：若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树形式，故将根的右链断开。二叉树根的右子树又可视为一个由除第一棵树 外的森林转换后的二叉树，应用同样的方法，直到最后只剩一棵没有右子树的二叉树为止，最后再将每棵二叉树依次转换成树，就得到了原森林。二叉树转换为树或森林是唯一的。

树和森林的遍历

树的遍历是指用某种方式访问树中的每个结点，且仅访问一次。主要有两种方式（深度优先遍历）：

1. 先根遍历。若树非空，先访问根结点，再依次遍历根结点的每棵子树，遍历子树时仍遵循先根后子树的规则。其遍历序列与这棵树相应二叉树的先序序列相同。
2. 后根遍历。若树非空，先依次遍历根结点的每棵子树，再访问根结点，遍历子树时仍遵循先子树后根的规则。其遍历序列与这棵树相应二叉树的中序序列相同。

另外，树也有层次遍历（广度优先遍历），与二叉树的层次遍历思想基本相同，即按层序依次访问各结点。

按照森林和树相互递归的定义，可得到森林的两种遍历方法。

1. 先序遍历森林。若森林为非空，则按如下规则进行遍历（效果等同于依次对各个树进行先根遍历）：
   • 访问森林中第一棵树的根结点。
   • 先序遍历第一棵树中根结点的子树森林。
   • 先序遍历除去第一棵树之后剩余的树构成的森林。
2. 中序遍历森林。森林为非空时，按如下规则进行遍历（效果等同于依次对各个树进行后根遍历）：
   • 中序遍历森林中第一棵树的根结点的子树森林。
   • 访问第一棵树的根结点。
   • 中序遍历除去第一棵树之后剩余的树构成的森林。