树的存储结构&&树和森林的遍历

ゞ浴缸里的玫瑰 2022-11-09 12:33 167阅读 0赞

# 树的存储结构 #

## 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_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70]

## 2. 孩子表示法 ##

将每个结点的孩子结点都用单链表连接起来形成一个线性结构，n个结点具有n个孩子链表。

#define MAX_TREE_SIZE 100
    typedef struct { 
    	int child;
    	struct CNode *next;
    } CNode;
    
    typedef struct { 
    	ElemType data;
    	struct CNode *child;
    } PNode;
    
    typedef struct { 
    	PNode nodes[MAX_TREE_SIZE];
    	int n;
    } CTree;

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

## 3. 孩子兄弟表示法 ##

以二叉链表作为树的存储结构，又称二叉树表示法。  
![在这里插入图片描述][20210315093518569.png]  
又称之为“左孩子，右兄弟”。

typedef struct CSNode { 
    	ElemType data;
    	struct CSNode *firstchild, *nextsibling;
    } CSNode, CSTree;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 2]

## 4. 总结 ##

<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>寻找结点的孩子结点效率高<br>方便实现树转换为二叉树</td> 
   <td>寻找结点的双亲结点效率低</td> 
  </tr> 
 </tbody> 
</table>

--------------------

# 树的遍历 #

按照某种方式访问树中的每个结点，且仅访问一次。

*  先根遍历：若树非空，则先访问根结点，再按从左到右的顺序遍历根结点的每棵子树。
 *  后跟遍历：若树非空，则先按从左到右的顺序遍历根结点的每棵子树，再访问根结点。

## 1. 先根遍历 ##

树的先根遍历序列和对应的树转换为二叉树后的先序遍历序列是一样的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 3]

## 2. 后根遍历 ##

树的后根遍历序列与这棵树对应二叉树的中序遍历序列相同。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 4]

# 森林的遍历 #

## 1. 先序遍历 ##

若森林非空，则

*  访问森林中第一棵树的根节点
 *  先序遍历第一课树的子树森林
 *  先序遍历除去第一棵树之后剩余的树构成的子树森林

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 5]  
森林的先序遍历序列与对应二叉树的先序遍历序列相同。

## 2. 中序遍历 ##

若森林非空，则：

*  中序遍历第一棵树的根结点的子树森林
 *  访问第一棵树的根结点
 *  中序遍历除去第一棵树之后剩余的树构成的子树森林

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 6]  
森林的中序遍历序列与对应二叉树的中序遍历序列相同。

## 3. 总结 ##

--------------------

参考：  
[https://www.bilibili.com/video/BV1b7411N798?t=285&p=44][https_www.bilibili.com_video_BV1b7411N798_t_285_p_44]

参考：[https://www.bilibili.com/video/BV1b7411N798?p=43][https_www.bilibili.com_video_BV1b7411N798_p_43]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70]: /images/20221023/16d060f2a3554d358e81c5ea7452b43c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 1]: /images/20221023/0527c51d670f4cccb3c2c836e622d3de.png
[20210315093518569.png]: /images/20221023/e73c3a3fc8334410ac83c2602a463363.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 2]: /images/20221023/db0246662a394238bf9c0422425eea9b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 3]: /images/20221023/1eaa13d34eac469d98a4f6715b18012e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 4]: /images/20221023/ff3fdeb0ae1a4df5a511db015c0d9b00.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 5]: /images/20221023/8bdc6d7d4e98459ab87e48f3ec14f4c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 6]: /images/20221023/a37429a28735494284edb78829d05fb6.png
[https_www.bilibili.com_video_BV1b7411N798_t_285_p_44]: https://www.bilibili.com/video/BV1b7411N798?t=285&p=44
[https_www.bilibili.com_video_BV1b7411N798_p_43]: https://www.bilibili.com/video/BV1b7411N798?p=43