当前位置：首页 > news >正文

一文了解树与森林基础

news 来源：原创 2025/5/30 6:15:58

文章目录

- 树和森林
- - 1树的存储结构
  - - 1.1双亲表示法
    - 1.2孩子表示法
    - 1.3孩子兄弟表示法
  - 2树、森林与二叉树的转换
  - - 2.1森林与二叉树的转换
    - 2.2 树与二叉树的转换
  - 3树和森林的遍历
  - - 3.1树的遍历
    - 3.2森林的遍历
    - 3.3 树和森林的遍历与二叉树的遍历关系
  - 4树的应用——并查集
  - - 4.1并查集及其相关操作
    - 4.2并查集的路径压缩

树和森林

请添加图片描述

1树的存储结构

关于树的存储，要求既要存储结点的数据元素，又要存储结点之间的逻辑关系。有关树的存储方式有多种，常用的三种数据的存储结构是双亲存储结构、孩子存储结构和孩子兄弟存储结构。

1.1双亲表示法

这种存储方式采用一组连续的空间来存储每个结点，每个结点中保存有指向其双亲的“指针”。这种存储方法可以很快可以很快地得到每个结点的双亲结点；但求结点的孩子时，需要遍历整个结构。

#define MAX_TREE_SIZE 100 			//树中最多结点数
typedef struct PTNode
{ 									//树的结点定义TElemType data; 				//数据元素int parent; 					//双亲位置域
}PTNode;
typedef struct
{ 									//树结构PTNode nodes[MAX_TREE_SIZE];int root; 						//根结点位置int n; 							//结点数
}PTree

下图中，根节点下标为 0，根节点的伪指针域为-1。

请添加图片描述

data	parent
R	-1
A	0
B	0
C	0
D	1
E	1
F	3
G	6
H	6
K	6

1.2孩子表示法

顺序存储各个结点，每个结点中保存孩子链表头指针。即先将每个结点的孩子结点都分别用单链表链接起来形成一个线性结构，再将各个结点用顺序存储的存储方法存储起来，每个结点都包含有一个指向其孩子链表首个结点的指针（叶结点的孩子链表为空）。代码实现如下：

//树的孩子链表存储表示typedef struct CTNode
{ 								//孩子结点int child;struct CTNode *next;
}*ChildPtr;
typedef struct
{TElemType data;ChildPtr firstchild; 		//孩子链表头指针
}CTBox;
typedef struct
{CTBox nodes[MAX-TREE.SIZE];int n,r; 					//结点数和根的位置
}CTree;

1.3孩子兄弟表示法

又称二叉树表示法，或二叉链表表示法，即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为 firstchild 域和 nextsibling 域。

这种存储表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作，也非常易于查找结点的孩子；但缺点是从当前结点查找其双亲结点较为麻烦。

//孩子兄弟表示法
typedef struct CSNode
{ElemType data; 								//数据域struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;

2树、森林与二叉树的转换

由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。

2.1森林与二叉树的转换

将森林转换为二叉树基于树与二叉树的转换（建议先学习下一小节的内容）：先将森林中的每棵树转换为二叉树；由于任何一棵和树对应的二叉树的右子树必为空，因此我们可以把森林中第二棵树根视为第一棵树的根的右兄弟，即将第二棵树对应的二叉树当作第一棵二叉树根的右子树；将第三棵树对应的二叉树当作第二棵二叉树的根的右子树……以此类推，就可以将森林转换为二叉树。

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

请添加图片描述

2.2 树与二叉树的转换

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

请添加图片描述

3树和森林的遍历

3.1树的遍历

1.树的先根遍历

若树非空，先访问根结点，再依次对每棵子树进行先根遍历。

树的先根遍历序列与这棵树相应二叉树的先序序列相同。

//树的先根遍历
void PreOrder(TreeNode *R){
if(R!=NULL){visit(R); 					//访问根节点while(R 还有下一个子树 T)PreOrder(T); 			//后根遍历下一棵子树}
}

2.树的后根遍历

若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。

树的后根遍历序列与这棵树相应二叉树的中序序列相同。

//树的后根遍历
void PostOrder(TreeNode *R){if(R!=NULL){while(R 还有下一个子树 T)PostOrder (T); 			//后根遍历下一棵子树visit (R); 					//访问根节点}
}

3.层次遍历（用队列实现）

①若树非空，则根节点入队

②若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队

③重复②直到队列为空

3.2森林的遍历

1.先序遍历森林

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

森林的先序遍历序列与这棵树相应二叉树的先序序列相同。

2.中序遍历森林（中根遍历，也叫后根遍历）

若森林为非空，则按如下规则进行遍历：中序遍历第一棵树中根结点的子树森林（中序遍历第一棵树对应的二叉树，因此最后才访问原先的树的根，即得到的序列和树的后根遍历相同，所以又叫后根遍历，中根遍历是借用了二叉树遍历的说法）；访问森林中第一棵树的根结点；中序遍历除去第一棵树之后剩余的树构成的森林。

森林的中序遍历序列与这棵树相应二叉树的中序序列相同。

3.3 树和森林的遍历与二叉树的遍历关系

根据遍历得出的序列不同，我们可以得出下表中的对应关系。其中，最容易造成误解的是森林的中序遍历。因为在不同的教材中，该森林遍历方法的命名不同。如前文所说，中根遍历仅仅是借用了二叉树遍历的说法，然而实际上根是最后访问的，因此部分教材中又按照树的遍历方法称其为后根遍历。实际上它们指的都是同一种遍历方法。

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历（后根遍历）	中序遍历

4树的应用——并查集

4.1并查集及其相关操作

请添加图片描述

并查集是一种简单的集合表示，通常用树（森林）的双亲表示作为并查的存储结构，每个子集合以一棵树表示。所有表示子集合的树，构成表示全集合的森林，存放在双亲表示法的数组内。通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲结点为负数，负数的绝对值大小达标了该子集合包含的结点个数。它支持以下 3 种操作：

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

void Initial(int S[]){for(int i=0;i<size;i++)S[i] = -1;
}

（2）合并：把集合 S 中的子集合 Root2 并入子集合 Rootl。要求 Root1 和 Root2 互不相交，否则不执行合并。为了得到两个子集合的并，只需将其中一个子集合根结点的双亲指针指向另一个集合的根结点。判断两个元素是否属于同一集合，只需分别找到它们的根结点，比较根结点是否相同即可。

void Union(int S[], int Root1, int Root2){S[Root2] = Root1;
}

（3）查找：查找集合 S 中单元素 x 所在的子集合，并返回该子集合的根结点。

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

4.2并查集的路径压缩

倘若有 n 个结点的并查集对应的树高为 n，在查找根结点的时候平均时间复杂度就会达到 O（n），因此可以通过路径压缩来加快结点查找根结点的效率，最好的情况下，即将树高压缩为 2 时，时间复杂度可以降低为 O(1)。

文章目录

树和森林

1树的存储结构

1.1双亲表示法

1.2孩子表示法

1.3孩子兄弟表示法

2树、森林与二叉树的转换

2.1森林与二叉树的转换

2.2 树与二叉树的转换

3树和森林的遍历

3.1树的遍历

3.2森林的遍历

3.3 树和森林的遍历与二叉树的遍历关系

4树的应用——并查集

4.1并查集及其相关操作

4.2并查集的路径压缩

相关文章：