数据结构考研学习笔记（九）---树、森林

心已赠人 2023-02-15 13:44 0阅读 0赞

### 树、森林 ###

*  1. 树的存储结构
 *   *  1.1 双亲表示法
     *  1.2 孩子表示法
     *  1.3 孩子兄弟表示法
     *  三种表示法的优缺点
 *  2. 树、 森林与二叉树的转换
 *  3. 树和森 林的遍历
 *  4. \*书的应用-并查集

# 1. 树的存储结构 #

树的存储方式有多种，即可采用顺序存储结构，又可采用链式存储结构。无论哪种方式都要反映出树中各结点之间的逻辑关系，下面介绍3种常用的存储结构

## 1.1 双亲表示法 ##

这种存储方式采用哟组连续空间来存储每个结点，同时在每个结点种增设一个伪指针，指示其双亲结点在数组中的位置。根结点的下标为0，其伪指针域为-1。  
双亲表示法的存储结构描述 `内联代码片`。

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

该存储结构利用了每个结点（根结点除外）只有唯一双亲的性质，可以很快得到每个结点的双亲结点，但求结点的孩子时需要遍历整个结构。  
例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center]

## 1.2 孩子表示法 ##

孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n个结点就有n个孩子链表（叶子结点的孩子链表为空表）如下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70]

#define MAX_TREE_SIZE 100
    typedef struct{
        //孩子结点的结构体
    int child;
    struct cNode *next;
    }CNode;
    typedef struct{
        //每一个结点存放的数据元素对应第一个孩子的指针，单链表的头指针
    ElemType data;
    struct cNode *child;
    }PNode ;
    typedef struct{
        //树，结点数
    PNodenodes [MAX_TREE_S1ZE];
    int n;
    )cTree;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 1]

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

## 1.3 孩子兄弟表示法 ##

孩子兄弟表示法又称**二叉树**表示法，即以二叉树表作为树的存储结构孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针，及指向结点下一个兄弟结点的指针。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 3]

孩子兄弟表示法的存储结构描述如下 `内联代码片`。

typedef struct CSNode{
        
    	ElemType data;//数据域
    	struct CSNode *f_child, *n_sibling;//第一个孩子和右兄弟指针
    }CSNode ,*CSTree;

## 三种表示法的优缺点 ##

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>优点</th> 
   <th>缺点</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>双亲表示法</td> 
   <td>寻找结点的双亲结点效率高</td> 
   <td>寻找结点的孩子结点效率低</td> 
  </tr> 
  <tr> 
   <td>孩子表示法</td> 
   <td>寻找结点的孩子结点效率高</td> 
   <td>寻找结点的双亲结点效率低</td> 
  </tr> 
  <tr> 
   <td>孩子兄弟表示法</td> 
   <td>寻找结点的孩子结点效率高方便实现树转换为二叉树</td> 
   <td>寻找结点的双亲结点效率低</td> 
  </tr> 
 </tbody> 
</table>

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

由于二叉树和树都可以用二叉链表作为存储结构，因此以一叉链表作为媒介可以导出树与二叉树的一个对应关系，即给定一棵树， 可以找到唯一的一 棵二叉树与之对应。从物理结构上看，它们的二叉链表是相同的，只是解释不同而已。  
树转换为二叉树的规则:每个结点左指针指向它的第一个孩子， 右指针指向它在树中的相邻右兄弟，这个规则又称“左孩子右兄弟”。由于根结点没有兄弟，所以对应的二又树没有右子树  
树转换成:又树的画法:①在兄弟结点之间加连线: ②对每个结点。只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉:③以树根为轴心顺时针发转45℃。  
森林转换成二又树的画法:①将森林中的每棵树转换成相应的二叉树:②每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线: ③以第一棵树的根 为轴心顺时针旋转45°。  
二又树转换为森林的规则:若二叉树非空，则二叉树的根及其左子树为第一棵树的 二叉树形式，故将根的右链断开。二叉树根的右子树又可视为一一个由除第一 棵树 外的森林转换后的二叉树，应用同样的方法，直到最后只剩棵没有右子树的二 叉树为止，最后再将每棵二叉树依次转换成  
树，就得到了原森林。

# 3. 树和森 林的遍历 #

树的遍历是指用某种方式访问树中的每个结点，且仅访问次。 主要有两种 方式:  
1)先根遍历。若树非空，先访问根结点，再依次遍历根结点的每棵子树，遍历子树时仍遵循先根后子树的规则。其遍历序列与这棵树相应二叉树的先序序列相同。  
2)后根遍历。若树非空，先依次遍历根结点的每棵子树，再访问根结点， 遍历子树时仍遵循先子树后根的规则。其遍历序列与这棵树相应二叉树的中序序列相同。  
按照森林和树相互递归的定义，可得到森林的两种遍历方法。  
1)先序遍历森林。若森林为非空，则按如下规则进行遍历:  
●访问森林中第一棵树 的根结点。  
●先序遍历第一 棵树中根结点的子树森林。  
●先序遍历除去第一棵树之后剩余的树构成的森林。  
2)中序遍历森林。森林为非空时，按如下规则进行遍历:  
●中序遍历森林中第一 棵树的根结点的子树森林。  
●访问第棵树的根结点。  
●中序遍历除去第一 棵树之后剩余的树构成的森林。

# 4. \*书的应用-并查集 #

**注：**  
在采用树的双亲指针数组表示作为并查集的存储表示时，集合元素的编号从0到size-1。其中size是最大无素的个数。下面是并查集主要运算的实现。  
`并查集的结构定义如下:`

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

`并查集的初始化操作(s即为并查集):`

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

`Find操作(函数在并查集S中查找并返回包含元素x的树的根):`

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

`Union操作(函数求两个不相交子集合的并集):`

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

应用后续更新：欢迎微信扫码“MeiXiangDao2020”  
领取资料

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201017183140256.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200605191702104.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201017183835187.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201017183952334.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201017184046731.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA==,size_16,color_FFFFFF,t_70#pic_center