数据结构——树——双亲表示法

清疚 2023-01-08 12:22 535阅读 0赞

## 数据结构——树——双亲表示法 ##

我们人可能因为种种原因，没有孩子，但无论是谁都不可能是从石头里蹦出来的，孙悟空显然不能算是人，所以是人一定会有父母。树这种结构也不例外，除了根结点外，其余每个结点，它不一定有孩子，但是一定有且仅有一个双亲。

我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。也就是说，每个结点除了知道自己是谁以外，还知道它的双亲在哪里。它的结点结构为表6-4-1所示。

![在这里插入图片描述][20210120094237357.png]  
其中 data是数据域，存储结点的数据信息。而parent是指针域，存储该结点的双亲在数组中的下标。

以下是我们的双亲表示法的结点结构定义代码。

/*树的双亲表示法的结点结构定义*/
    #define MAX_TREE_SIZE 100
    typedef int TElemType;/*树结点的数据类型*/
    
    typedef struct PTNode /*结点结构*/
    {
        
        TElemType data;   /*结点数据*/
        int parent;       /*双亲位置*/
    } PTNode;
    
    typedef struct PTree      /*树结构*/
    {
        
        PTNode nodes[MAX_TREE_SIZE];/*结点数组*/
        int r, n;  /*根的位置和结点数*/
    } PTree;

有了这样的结构定义，我们就可以来实现双亲表示法了。由于根结点是没有双亲的，所以我们约定根结点的位置域设置为一1，这也就意味着，我们所有的结点都存有它双亲的位置。如图6-4-1中的树结构和表6-4-2中的树双亲表示所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 1]  
这样的存储结构，我们可以根据结点的parent指针很容易找到它的双亲结点，所用的时间复杂度为0(1)，直到parent为-1时，表示找到了树结点的根。可如果我们要知道结点的孩子是什么，对不起，请遍历整个结构才行。

[20210120094237357.png]: /images/20221119/bf319a1847c64fcab92cb0804d7fca74.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70]: /images/20221119/a4630a4c2de9430498405bab3a5f78df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 1]: /images/20221119/eed8e4406cdc4798aeaa6286b5e5895b.png