《数据结构》—— 树的基本介绍、存储结构、树、森林与二叉树的转换

Myth丶恋晨 2022-09-12 05:51 183阅读 0赞

### 树的介绍 ###

*   *  一、树的定义
     *  二、树的基本术语
     *  三、树的性质
     *  四、树的存储结构
     *   *  4.1 双亲表示法（顺序存储）
         *  4.2 孩子表示法（顺序+链式存储）
         *  4.3 孩子兄弟表示法（链式存储）
     *  五、树、森林与二叉树的转换

## 一、树的定义 ##

树是n(n>=0)个结点的有限集。当n=0时，称为空树。  
树是一种递归定义的数据结构，在任意一棵非空树中应满足：

*  有且仅有一个特定的称为根的结点；
 *  当n>1时，其余结点可分为m（m > 0）个互不相交的有限集合T1, T2,…, Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。

**非空树的特性：**

*  有且仅有一个根节点；
 *  没有后继的结点称为“叶子结点”（或终端结点）；
 *  有后继的结点称为“分支结点”（或非终端结点）；
 *  除了根节点外，任何一个结点都有且仅有一个**前驱**；
 *  每个结点可以有0个或多个**后继**。  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_18_color_FFFFFF_t_70_g_se_x_16]

## 二、树的基本术语 ##

以图中的K结点示例，根节点A是K的**祖先**；K是B的**子孙**结点；K与E是**双亲**，K是E的**孩子**，K与L是**兄弟**结点。

**树的度：** 各结点的度的最大值，如B的度为2，D的度为3，取MAX树的度为3；  
度>0的结点（有子女结点）则有分支，度=0的结点（无子女结点）是叶子结点；  
**结点的度**：有几个孩子（分支）就度是几；结点中最大的度就是树的度；  
**结点的层次**: 从树根开始定义,根结点为第1层，它的子结点为第2层，以此类推；  
**结点的深度**: 从根结点开始自顶向下逐层累加的；  
**结点的高度**: 从叶结点开始自底向上逐层累加的；  
**树的高度(或深度)** : 树中结点的最大层数。

**有序树**\-——逻辑上看，树中结点的各子树从左至右是有次序的，不能互换；

**无序树**——逻辑上看，树中结点的各子树从左至右是无次序的，可以互换。

森林是m（m≥0）棵互不相交的树的集合。把树的根节点删掉就变成了森林，森林添加根节点就变成了树。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16]

## 三、树的性质 ##

<table> 
 <thead> 
  <tr> 
   <th>度为m的树</th> 
   <th>m叉树</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>任意结点的度 ≤ m(最多m个孩子)</td> 
   <td>任意结点的度 ≤ m(最多m个孩子)</td> 
  </tr> 
  <tr> 
   <td>至少有一个结点度=m(有m个孩子)</td> 
   <td>允许所有结点的度都＜m</td> 
  </tr> 
  <tr> 
   <td>一定是非空树，至少有m+1个结点</td> 
   <td>可以是空树</td> 
  </tr> 
  <tr> 
   <td>度为m的树第 i 层至多有m的i-1次方个结点（i≥1）</td> 
   <td>m叉树第 i 层至多有m的i-1次方个结点（i≥1）</td> 
  </tr> 
  <tr> 
   <td>高度为h、度为m的树至少有h+m-1个结点</td> 
   <td>高度为h的m叉树至多有 (m的h次方-1)/(m-1)个结点。</td> 
  </tr> 
  <tr> 
   <td>m</td> 
   <td>具有n个结点的m叉树的最小高度为 [<strong>log</strong> m <strong>(n(m - 1)</strong> + 1)]</td> 
  </tr> 
 </tbody> 
</table>

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

## 四、树的存储结构 ##

### 4.1 双亲表示法（顺序存储） ###

这种存储方式采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针， 指示其双亲结点在数组中的位置。如图所示，根结点下标为0，其伪指针域为-1。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
我们可以看到，R为根节点，结点下标为0，其伪指针域为-1。例如要找ABC的双亲是parent ==0 的结点下标 R；G的双亲是结点下标为6的F，其他也是同理查找。

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

树的存储结构中，用双亲表示法：优点：查指定结点的双亲很方便；插入结点只需直接在接着顺序插入；在删除某一个结点后，会显示空数据，导致遍历速度慢；查指定结点的孩子只能从头遍历。

而二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来，且结点编号不仅反映了存储位置，也隐含了结点之间的逻辑关系。

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

### 4.2 孩子表示法（顺序+链式存储） ###

孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n个结点就有n个孩子链表(叶子结点的孩子链表为空表)，如图所示。这种存储方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_15_color_FFFFFF_t_70_g_se_x_16]

struct CTNode {
        
    	int child;		      //孩子 结点在数组中的位置
    	struct CTNode *next;  //下一个孩子
    };
    typedef struct {
        
    	ElemType data;
    	struct CTNode *firstChild; //第一个孩子
    }CTBox;
    typedef struct {
        
    	CTBox nodes [MAX_ TREE_ SIZE];
    	int n, r; //结点数和根的位置
    }CTree;

### 4.3 孩子兄弟表示法（链式存储） ###

孩子兄弟表示法又称二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容:结点值、指向结点第一个孩子结点的指针，及指向结点下一个兄弟结点的指针 (沿此域可以找到结点的所有兄弟结点)，如图所示。

![在这里插入图片描述][2de0141e5ce449009c5a6f69515ff5f4.png]  
这种存储表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作，易于查找结点的孩子；但从当前结点查找其双亲结点比较麻烦。

//树的存储一孩子 兄弟表示法
    typedef struct CSNode{
        
    	ElemType data;	//数据域
    	struct CSNode *firstchild, *nextsibling;  //第一个孩子(左指针)和右兄弟指针
    }CSNode, *CSTree;

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

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

**树转换为二叉树的规则**：每个结点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则又称“左孩子连右兄弟”。由于根结点没有兄弟，所以对应的二叉树没有右子树，  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
**树转换成二叉树的画法**: ①在兄弟结点之间加一连线；②对每个结点，只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉；③以树根为轴心，顺时针旋转45%。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
**森林转换成二叉树的画法:** ①将森林中的每棵树转换成相应的二叉树:②每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线；③以第一棵树的根为轴心顺时针旋转45%。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
**二叉树转换为森林的规则:** 若二叉树非空,则二叉树的根及其左子树为第-棵树的二叉树形式，故将根的右链断开，二叉树根的右子树又可视为一个由除第一棵树外的森林转换后的二叉树，应用同样的方法，直到最后只剩一棵没有右子树的二叉树为止，最后再将每棵二叉树依次转换成树，就得到了原森林，如图所示。二叉树转换为树或森林是唯一的。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 5]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/ea28e171fc1247d0a0eb8bd7997d16a3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/5a7679a415414ef2a5d05117a0dc612f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/66b16a84b0ee49b0b79c95260d34e766.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/82ec5aa1c83849d1bbc14cad3e064c4c.png
[2de0141e5ce449009c5a6f69515ff5f4.png]: /images/20220828/9fe709e2618946d4bc7bd7947e313594.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/e15c650c33ef44449b8e44fcf846d0f2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/bb3f19878744490e82ba67864bf7912a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/ffc9e00c493b44ed8309b9ddf02c62e5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/f58c487ab4be45de8a9b06db44862ce8.png