一文了解树与森林基础

树和森林

1树的存储布局

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

1.1双亲表示法

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

1. #define MAX_TREE_SIZE 100                         //树中最多结点数
2. typedef struct PTNode
3. {                                                                         //树的结点定义
4.         TElemType data;                                 //数据元素
5.         int parent;                                         //双亲位置域
6. }PTNode;
7. typedef struct
8. {                                                                         //树结构
9.         PTNode nodes[MAX_TREE_SIZE];
10.         int root;                                                 //根结点位置
11.         int n;                                                         //结点数
12. }PTree

复制代码

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

dataparentR-1A0B0C0D1E1F3G6H6K6
1.2孩子表示法

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

1. //树的孩子链表存储表示
3. typedef struct CTNode
4. {                                                                 //孩子结点
5.         int child;
6.         struct CTNode *next;
7. }*ChildPtr;
8. typedef struct
9. {
10.         TElemType data;
11.         ChildPtr firstchild;                 //孩子链表头指针
12. }CTBox;
13. typedef struct
14. {
15.     CTBox nodes[MAX-TREE.SIZE];
16.         int n,r;                                         //结点数和根的位置
17. }CTree;

复制代码

1.3孩子兄弟表示法

​ 又称二叉树表示法，或二叉链表表示法，即以二叉链表作树的存储布局。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为 firstchild 域和 nextsibling 域。
​ 这种存储表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作，也非常易于查找结点的孩子；但缺点是从当前结点查找其双亲结点较为麻烦。

1. //孩子兄弟表示法
2. typedef struct CSNode
3. {
4.         ElemType data;                                                                 //数据域
5.         struct CSNode *firstchild, *nextsibling;
6. }CSNode, *CSTree;

复制代码

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

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

2.1森林与二叉树的转换

​ 将森林转换为二叉树基于树与二叉树的转换（发起先学习下一小节的内容）：先将森林中的每棵树转换为二叉树；由于任何一棵和树对应的二叉树的右子树必为空，因此我们可以把森林中第二棵树根视为第一棵树的根的右兄弟，即将第二棵树对应的二叉树看成第一棵二叉树根的右子树；将第三棵树对应的二叉树看成第二棵二叉树的根的右子树……以此类推，就可以将森林转换为二叉树。
​ 二叉树转换为森林的规则：若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树情势，故将根的右链断开。二叉树根的右子树又可视为一个由除第一棵树外的森林转换后的二叉树应用同样的方法，直到最后只剩一棵没有右子树的二叉树为止，最后再将每棵二叉树依次转换成树，就得到了原森林。二叉树转换为树或森林是唯一的。

2.2 树与二叉树的转换

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

3树和森林的遍历


3.1树的遍历

​ 1.树的先根遍历
​ 若树非空，先访问根结点，再依次对每棵子树进行先根遍历。
​ 树的先根遍历序列与这棵树相应二叉树的先序序列相同。

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

复制代码

​ 2.树的后根遍历
​ 若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。
​ 树的后根遍历序列与这棵树相应二叉树的中序序列相同。

1. //树的后根遍历
2. void PostOrder(TreeNode *R){
3.         if(R!=NULL){
4.                 while(R 还有下一个子树 T)
5.                         PostOrder (T);                         //后根遍历下一棵子树
6.                 visit (R);                                         //访问根节点
7.         }
8. }

复制代码

​ 3.层次遍历（用队列实现）
​ ①若树非空，则根节点入队
​ ②若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
​ ③重复②直到队列为空



3.2森林的遍历


​ 1.先序遍历森林
​ 若森林为非空，则按如下规则进行遍历：访问森林中第一棵树的根结点；先序遍历第一棵树中根结点的子树森林；先序遍历撤除第一棵树之后剩余的树构成的森林。
​ 森林的先序遍历序列与这棵树相应二叉树的先序序列相同。

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



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

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



4树的应用——并查集


4.1并查集及其相关操作

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

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

复制代码

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

1. void Union(int S[], int Root1, int Root2){
2.         S[Root2] = Root1;
3. }

复制代码

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

1. int Find(int S[], int x){
2.         while(S[x]>=0)
3.                 x = S[x];
4.         return x;
5. }

复制代码

4.2并查集的路径压缩

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。