【数据结构——树和森林】

悠悠 2022-11-21 09:29 182阅读 0赞

### 目录： ###

*  一、树的存储结构
 *   *  （一）双亲表示法
     *  （二）孩子链表表示法（带双亲的孩子链表-parent）
     *  （三）树的二叉链表（孩子-兄弟）存储表示法
 *  二、森林与二叉树的转换
 *   *  （一）将树转换成二叉树
     *  （二）将二叉树转换成树
     *  （三）将森林转换成二叉树
     *  （四）将二叉树转换成森林
 *  三、树和森林的遍历
 *   *  （一）树的遍历（不讨论中序）
     *  （二）森林的遍历（不讨论后序）

# 一、树的存储结构 #

## （一）双亲表示法 ##

**实现： 定义结构数组来存储树的结点，每个结点含有两个域：**  
![在这里插入图片描述][20201031082154792.png_pic_center]**数据域：存放结点本身信息  
双亲域：指示本结点的双亲结点在数组中的位置**

**特点： 找双亲容易，找孩子难**

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

#define MAX_TREE_SIZE 100
    typedef struct PTNode
    {
        //结点结构
    	ElemType data;
    	int parent;//保存双亲位置
    }PTNode;
    
    typedef struct
    {
        //定义树结构
    	PTNode nodes[MAX_TREE_SIZE];
    	int r, n;//根的位置和结点数
    }PTree;

## （二）孩子链表表示法（带双亲的孩子链表-parent） ##

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

//孩子链表表示法的类型描述
    typedef struct CTNode
    {
        
    	int child;
    	struct CTNode* nextchild;
    }*ChildPtr;
    //双亲结点结构
    typedef struct
    {
        
    	ElemType data;
    	int parent;//保存双亲位置
    	ChildPtr firstchild;//孩子链的头指针
    }CTBox;
    //树结构
    typedef struct
    {
        
    	CTBox nodes[MAX_TREE_SIZE];
    	int n, r;//结点数和根结点的位置
    }CTree;

## （三）树的二叉链表（孩子-兄弟）存储表示法 ##

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

![在这里插入图片描述][20201031091039854.png_pic_center]

/*树的二叉链表类型描述*/
    typedef struct CSNode
    {
        
    	ElemType data;
    	struct CSNode* firstchild, * nextsibling;
    }CSNode,*CSTree;

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

## （一）将树转换成二叉树 ##

**加线： 在兄弟之间加一条连线**  
**抹线： 对每个结点，除了其最左边孩子外，去除其与其余孩子之间的关系**  
**旋转： 以树的根结点为轴心，将整树顺时针旋转45度。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]  
**树转换成的二叉树，根结点的右子树一定为空**

## （二）将二叉树转换成树 ##

**加线： 若p结点是双亲结点的左孩子，则将P的右孩子，右孩子的右孩子·····沿着分支找到的所有右孩子，都与p的双亲用线连起来**  
**抹线： 抹掉原二叉树中双亲与右孩子之间的连线**  
**调整： 将结点按层次排列，形成树的结构**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 4]

## （三）将森林转换成二叉树 ##

**1、将各棵树分别转换成二叉树  
2、将每棵树的根结点用线连接起来  
3、以第一棵树的根结点为二叉树的根，再以根结点为核心，顺时针旋转，构成二叉树形结构**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 5]

## （四）将二叉树转换成森林 ##

**抹线： 将二叉树中根结点与其右孩子连线，以及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立二叉树**  
**还原： 将孤立的二叉树还原成树**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 6]

# 三、树和森林的遍历 #

**遍历： 按照一定规律走遍树的各个顶点，且使每个顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列**

## （一）树的遍历（不讨论中序） ##

**常用方法：**  
**1、先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树  
2、后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点  
3、按层次遍历：先访问第一层上的结点，然后依次遍历第二层，·····，第N层的结点。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 7]

## （二）森林的遍历（不讨论后序） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 8]

[20201031082154792.png_pic_center]: /images/20221120/53cafcfe6dce4eb89e8e940c96a58238.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/40fa9bef53eb435c8513473799d377a4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/c7eddbde48bf45168cf31422cc59926a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/9349cae144774ae1bed4cf4516e47c05.png
[20201031091039854.png_pic_center]: /images/20221120/bc1ebe9a0584416e9927c3cd6b0bbd49.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/33696c8dc42e453b87d61ae1aa7ac81d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/81e08172bbda4a8caca7c450fe59def1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221120/bfe3a0f1b4e94ff4835b3d53c7a25e67.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221120/e60c3e5aeffa477b97983b872d9e2afd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221120/0f66679abf174d9eaeecb59ec32f0deb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221120/c35552bf0b0f4407be8a61c1c3998fb7.png