5.5 树和森林

树的双亲表示法、孩子表示法和孩子兄弟表示法；树、森林与二叉树的相互转换；树和森林的遍历。

树的存储结构

双亲表示法

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

#define MAX_TREE_SIZE 100
typedef struct {
    ElemType data;
    int parent;                         // 双亲位置域
} PTNode;
typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int n;                              // 结点数
} PTree;

• 优点：利用了每个结点（根结点除外）只有唯一双亲的性质，可以很快地得到每个结点的双亲结点；
• 缺点：求结点的孩子时需要遍历整个结构。

孩子表示法

将每个结点的孩子结点视为一个线性表，且以单链表作为存储结构，则 $n$ 个结点就有 $n$ 个孩子链表（叶结点的孩子链表为空表）。

• 优点：寻找子女的操作非常直接；
• 缺点：寻找双亲的操作需要遍历 $n$ 个结点中孩子链表指针域所指向的 $n$ 个孩子链表。

孩子兄弟表示法

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

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

• 优点：可以方便地实现树转换为二叉树的操作，易于查找结点的孩子等；
• 缺点：从当前结点查找其双亲结点比较麻烦（可以为每个结点增设一个 parent 域）。

树、森林与二叉树的转换

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

树转换为二叉树的规则：每个结点的左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则又称”左孩子右兄弟”。

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

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

树和森林的遍历

树的遍历：

• 先根遍历：若树非空，先访问根结点，再依次遍历根结点的每棵子树。其遍历序列与这棵树相应二叉树的先序序列相同。
• 后根遍历：若树非空，先依次遍历根结点的每棵子树，再访问根结点。其遍历序列与这棵树相应二叉树的中序序列相同。
• 层次遍历：与二叉树的层次遍历思想基本相同。

森林的遍历：

• 先序遍历森林：访问第一棵树的根 → 先序遍历第一棵树中根结点的子树森林 → 先序遍历除去第一棵树之后剩余的树构成的森林。
• 中序遍历森林（也称后序遍历森林）：中序遍历第一棵树中根结点的子树森林 → 访问第一棵树的根结点 → 中序遍历除去第一棵树之后剩余的树构成的森林。

即时练习