signed

QiShunwang

“诚信为本、客户至上”

树和森林的遍历

2021/4/26 14:07:55   来源:

树的遍历操作:某种方式访问树中的每个结点,且仅访问一次。

先根遍历。若树非空,则先访问根结点,再按从左到右的顺序遍历根结点的每棵子树。其访问顺序与这棵树相应二叉树的先序遍历顺序相同。

后根遍历。若树非空,则按从左到右的顺序遍历根结点的每棵子树,之后再访问根结点。其访问顺序与这棵树相应二叉树的中序遍历顺序相同

层次遍历。与二叉树的层次遍历思想基本相同,即按层次依次访问各结点。

先序遍历森林。若森林为非空,则按如下规则进行遍历
● 访问森林中第一棵树的根结点
● 先序遍历第一棵树中根结点的子树森林
● 先序遍历除去第一棵树之后剩余的树构成的森林

中序遍历森林。若森林为非空,则按如下规则进行遍历
● 中序遍历森林中第一棵树的根结点的子树森林
● 访问第一棵树的根结点
● 中序遍历除去第一棵树之后剩余的树构成的森林。

树和森林的遍历:可采用对应二叉树的遍历算法实现

树的应用——并查集

并查集:一种简单的集合表示,它支持以下 3 种操作
1)Union(S, Root1, Root2):把集合 S 中的子集合 Root2 并入子集合 Root1。要求 Root1 和 Root2 互不相交,否则不执行合并。
2)Find(S, x):查找集合 S 中单位元素 x 所在的子集合,并返回该子集合的名字。
3)Initial(S):将集合 S 中的每个元素都初始化为只有一个单元素的子集合。

通常用树(森林)的双亲表示作为并查集的存储结构,每个子集合以一棵树表示。所有表示子集合的树,构成表示全集合的森林,存放在双亲表示数组内。通常用数组元素的下标代表元素名,用根结点的下标代表子集合名,根结点的双亲结点为负数。

例如:若设有一个全集合为 S={0, 1, 2, 3, 4, 5, 6, 7, 8, 9},初始化时每个元素自成一个单元素子集合,每个子集合的数组值为 -1。

经过一段时间的计算,这些子集合合并为 3 个更大的子集合 S1={0, 6, 7, 8},S2={1, 4, 9},S3={2, 3, 5},此时并查集的树形表示和存储结构如下。

为了得到两个子集合的并,只需要将其中一个子集合根结点的双亲指针指向另一个集合的根结点。因此,S1US2~可以具有如图的表示。

在采用树的双亲指针数组表示作为并查集的存储表示时,集合元素的编号从 0 到 size-1。其中 size 是最大元素的个数。

#define SIZE 100
int UFSets[SIZE]; //集合元素数组(双亲指针数组)

void Initial(int S[])
{
    for(int i=0; i<size; i++) //每个自成单元素集合
        S[i] = -1;
}

int Find(int S[], int x)
{
    while(S[x] >= 0) //循环寻找x的根
        x = S[x];
    return x; //根的S[]小于0
}

void Union(int S[], int Root1, int Root2)
{
    //要求Root1与Root2是不同的,且表示子集合的名字
    S[Root2] = Root1; //将根Root2连接到另一根Root1下面
}