树的存储结构回顾

曾经终败给现在 2022-12-25 04:53 106阅读 0赞

## 一 概述 ##

树既可以采用顺序存储，同时可以采用链式存储，无论是那种存储结构，我们都需要通过某种方法对其进行描述。我们主要会右三种表示方法：双亲表示法，孩子表示法，孩子兄弟表示法。

## 二 双亲表示法 ##

双亲表示法通过采用一组连续的存储空间来存储每个结点，同时再每个结点中增设一个伪指针，指示双亲结点在数组中的位置，故通过该伪指针我们描述了结点之间的逻辑关系。根结点的下标为0，其伪指针域为-1。

**双亲表示法的实现**

#define MAX_TREE_SIZE 100
    //该结构体表示每个结点，其中包括数据部分data
    typedef struct{
    	ElemType data;
    	//标记双亲结点的整形变量parent
    	int parent;
    }PTNode;
    //该结构体描述树的结构
    typedef struct{
        //结点数组变量，保存每个结点的信息
    	PTNode nodes[MAX_TREE_SIZE];
    	//表示该树当中结点的数量
    	int n;
    }PTree;

**通过双亲表示法表示树结构的实例图**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70][]

如图：树中结点的编号按层序遍历依次从0~9。其中根结点不存在双亲结点，所以其双亲结点的编号为-1。

## 三 孩子表示法 ##

孩子表示法是将每个结点都用单链表连接起来形成一个线性结构，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_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70 1][]

由实例图可知，树中存在10个树结点，所以会存在10个孩子链表，对于无孩子的结点所对应的孩子链表为空。

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

以二叉链表作为树的存储结构，又称二叉树表示法。在该结构中，我们使用左指针指向其第一个孩子结点，右指针指向结点的下一个兄弟结点，

**孩子兄弟表示法的实现**

typedef struct CSNode {
    	//data表示该节点的数据
    	ElemType data;
    	//*firstChild指向其第一个孩子结点，*nextsibling指向其兄弟结点
    	struct CSNode *firstChild, *nextsibling;
    }CSNode,CSTree;

**通过孩子兄弟表示法表示树结构的实例图**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70 2][]

如图所示，根结点R不存在兄弟结点，所以其右指针为空，而A为R的第一个孩子结点，所有R的左指针指向它。对于结点A，由于D是其第一个孩子结点，所以A的做指针指向它，同时B为A的下一个兄弟结点，A的右指针指向B。

同理，其他结点也会根据上述规律进行树结构的表示。

## 五 上述不同方式的比较 ##

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

综上所述，树的不同表示法，所需要的数据结构会有一定的不同，执行不同操作的效率也会存在很大的差异，所以我们应该根据不同的需求使用最合适的表示法。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70]: /images/20221120/cf1aa0a454614f35b216bd1705d3a976.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70 1]: /images/20221120/617a317703814840a6ee1f2fc02d04e1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70 2]: /images/20221120/8e52b455d1f244149bef2db73900e346.png