> For the complete documentation index, see [llms.txt](https://xiuxin.gitbook.io/datastructre/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://xiuxin.gitbook.io/datastructre/shu-he-er-cha-shu/shu-sen-lin.md).

# 树、森林

## 树的存储结构

  树的存储方式有很多种，既可采用顺序结构，又可采用链式存储结构，但无论采用何种存储方式，都要求能唯一的反映树中各结点之间的逻辑关系。下面是常见的存储结构：

### 双亲表示法

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

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/树的双亲表示法.png)

  双亲表示法的存储结构描述:

```cpp
#define MAX_TREE_SIZE 100            //树中最多结点数
typedef struct{                        //树中的结点定义
    ElemType data;                    //数据元素
    int parent;                        //双亲位置
}PTNode;
typedef struct{                        //树的类型定义
    PTNode nodes[MAX_TREE_SIZE];    //双亲表示
    int n;                            //结点数
}PTTree;
```

  该存储结构利用了每个结点（根结点除外）只有唯一双亲的性质，可以很快得到每个结点的双亲结点，但求结点的孩子时需要遍历整个结构。

### 孩子表示法

  孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n个结点就有n个孩子链表（叶子结点的孩子链表尾空表）。

  这种存储方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/孩子表示法.jpg)

### 孩子兄弟表示法

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

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/孩子兄弟表示法.jpg)

  孩子兄弟表示法的存储结构：

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

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

## 树，森林与二叉树的转换

  **树转化为二叉树的规则**：每个结点左指针指向它的第一个孩子结点，右指针指向它在树中的相邻兄弟结点，可即为“左孩子右兄弟”。由于根结点没有兄弟，所以由树转换而得的二叉树没有右子树。

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/树转化为二叉树.jpg)

  **森林转化为二叉树的规则**：先将每一棵树转换为二叉树，再将第一棵树的根作为转换后的二叉树的根，将第一棵树的左子树作为转换后的左子树，将第二棵树作为转换后的右子树，将第三棵树作为转换后的二叉树的右子树的右子树，以此类推。

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/森林转化为二叉树.jpg)

  **二叉树转换为森林的规则**：若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树形式，二叉树的根的右子树可视为一个由除第一棵树外的森林转化后的二叉树，用同样的方法，知道最后产生一棵没有右子树的二叉树为止。

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/二叉树转换为森林.jpg)

  总结起来，个人愚见：将原先的左子树孩子节点转换为左子树孩子结点不变，原先的兄弟结点转换为左孩子结点的右子树。

## 树和森林的遍历

### 树的遍历

  1）**先根遍历**：若树非空，先访问根结点，再按从左到右的顺序遍历根结点的每棵子树。和相对应的二叉树的先序遍历顺序相同

  2）**后根遍历**：若树非空，先按从左到右的顺序遍历根结点的每棵子树，之后在访问根结点。和相对应的二叉树的中序遍历顺序相同

  3）**层次遍历**：与二叉树的层次遍历思想基本相同

### 森林的遍历

  1）**先序遍历森林**：若森林非空，访问森林中第一棵树的根结点；先序遍历第一课树中根结点的子树森林；先序遍历除去第一棵树之后剩余的树构成的森林。

  2）**中序遍历森林**：若森林非空，中序遍历第一课树中根结点的子树森林；访问森林中第一棵树的根结点；中序遍历除去第一棵树之后剩余的树构成的森林。

  树和森林的遍历与二叉树遍历的对应关系：

|   树  |  森林  |  二叉树 |
| :--: | :--: | :--: |
| 先根遍历 | 先序遍历 | 先序遍历 |
| 后根遍历 | 中序遍历 | 中序遍历 |

## 树的应用--并查集

  并查集是一种简单的集合表示，支持以下三种操作：

  1）Union（S，Root1，Root2）：把集合S中的子集合Root2并入子集合Root1。要求Root1和Root2 互不相交，否则不执行合并。

  2）Find（S，x）：查找集合S中单元素x所在的子集合，并返回该子集合的名字。

  3）Initial（S）：将集合S中的每个元素都初始化为只有一个单元素的子集合。

  通常用树（森林）的双亲表示作为并查集的存储结构，每个子集合以一棵树表示。所有表示子集合的树，构成表示全集合的森林，存放在双亲表示数组内，可以把它叫做 parent数组。通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲结点为负数（-1）。

  这里先简单将一下，后续会详细讲解。并查集可以用来检测图中是否含有闭合回路，当然还有其他用途。

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/并查集.png)

  并查集的结构定义：

```cpp
#define SIZE 100
int UFSets[SIZE];    //集合元素数组
```

  并查集的初始化操作：将parent数组中的元素值设为-1，代表元素无根结点，自己就是独立的元素

```cpp
void Initial(int parent[]){
    int size = sizeof(parent)/sizeof(int);
    for(int i = 0; i < size; i++){
        parent[i] = -1;
    }
}
```

  Find操作：找出元素的根结点

```cpp
int Find(int parent[],int x){
    while(parent[x] >= 0){
        x = parent[x];
    }
    return x;
}
```

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/并查集路径压缩.jpg)

  Union操作：求两个不相交集合的并集

```cpp
void Union(int parent[], int Root1, int Root2){
    parent[Root2] = Root1;         //将集合root2合并到集合Root1中
}
```