【数据结构】树的存储结构（C语言）

短命女 2023-02-18 09:55 42阅读 0赞

### 文章目录 ###

*   *  双亲表示法
     *  孩子表示法
     *  孩子兄弟表示法

利用顺序存储结构和链式存储结构的特点，完全可以实现对树的存储结构的表示。介绍三种不同的表示方法：双亲表示法，孩子表示法，孩子兄弟表示法。

## 双亲表示法 ##

假设一组连续的空间存储树的特点。同时**在每个结点中，附设一个指示器指示双亲结点到链表中的位置。** 也就是说，每个结点除了知道自己是谁以外，还知道他的双亲在哪里，他的结点结构图1-1所示。  
![在这里插入图片描述][20200617124455959.png_pic_center]

图1-1  
其中data是数据域，存储结点的数据信息。而parent是指针域，存储该结点的双亲在数组中的下标。

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

有了这样的数据结构就可以来实现双亲表示法。由于根结点是没有双亲的，所以我们约定根结点的位置域设置为-1，这也就意味着，我们所有的结点都存有他双亲的位置。如图1-2中的树结构和表1-3中的树双亲表示。  
![在这里插入图片描述][20200617130322946.png_pic_center]

图1-2  
![在这里插入图片描述][20200617130414841.png_pic_center] 表1-3  
这样的存储结构，我们可以根据结点的parent’指针很容易找到他的双亲结点，时间复杂度为O(1)，直到parent为-1时，表示找到了树结点的根，可是如果我们要直到结点的孩子是什么，要遍历整个结点才行。

改进一下，增加一个结点最左边孩子的域，不妨叫他长子域，这样就可以很容易得到结点的孩子。如果没有孩子的结点，这个长子域就设置为-1，如表1-4所示。  
![在这里插入图片描述][20200617131405266.png_pic_center]

表1-4  
对于有0个或者1个孩子结点来说，这样的结构是解决了要找结点孩子的问题了。甚至是有2个孩子，知道了长子是谁，另一个当然就是次子了。

另外一个问题，我们很关注各兄弟之间的关系，双亲表示法无法体现这样的关系，可以增加一个右兄弟域来体现兄弟关系，也就是说，每个结点如果他存在右兄弟，则记录下右兄弟的下标。同样的，如果右兄弟不存在，则赋值-1.表1-5所示。  
![在这里插入图片描述][20200617131853463.png_pic_center]

表1-5  
但是如果结点的孩子很多，超过了2个，我们又关注结点的孩子们，还关注结点的兄弟，而且对时间遍历要求高，我们可以把此结构扩展为有双亲域，长子域，再有右兄弟域。 **存储结构的设计是一个非常灵活的过程，一个存储结构设计是否合理，取决于该存储结构的运算是否适合，是否方便，时间复杂度好不好等。**

## 孩子表示法 ##

换一种完全不同的考虑方法，由于树中每个结点可能有多棵子树，可以考虑用多重链表。**每个结点有多个指针域，其中每个指针指向一颗子树的根结点，我们把这种方法叫做多重链表的表示方法。** 不过，树的每个结点的度，也就是他的孩子个数是不同的，所以设计两种方法：  
方案一：  
指针域的个数就等于树的度，树的度就是树各个结点度的最大值。其结构如图1-6所示。  
![在这里插入图片描述][20200617134403546.png_pic_center]

图1-6  其中data是数据域，child1到childd是指针域，用来指向该结点的孩子结点。对于图1-1来说，树的度是3，所以我们指针域个数就是3，如图1-7所示。

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

图1-7  这种方法对于数组各个结点的度相差很大时，显然是很浪费空间的，因为有很多的结点，它的指针域是空的，不过树的各个结点度相差很小时，那就意味着开辟的空间被充分利用了，这时存储结构的缺点反而变成了优点。 既然很多指针域都可能为空，为什么不按需分配空间了？

方案二：  
每个结点指针域的个数等于该结点的度，我们专门取一个位置来存储结点指针的个数。如图1-8所示。

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

图1-8  
data为指针域，degree为度域，也就是存储该结点的孩子结点的个数，结构如图1-9所示。  
![在这里插入图片描述][2020061713590553.png_pic_center] 图1-9  
这种方式克服了浪费空间的缺点，对空间利用率很高，但是由于各个结点的链表是不同的结构，加上要维护结点度的数值，在运算上就会带来时间上的损耗。

这就是我们要说的**孩子表示法，把每个结点的孩子都排列起来，以单链表为存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组**，如图1-10所示。  
![在这里插入图片描述][20200617140417452.png_pic_center]

图1-10  
为此，设计两种存储结构，一个是孩子链表的孩子结点，图1-11所示。  
![在这里插入图片描述][20200617140940777.png_pic_center] 图1-11  
child是数据域，用来存储某个结点在表头数组中的下标。next是指针域，用来存储指向结点的下一个孩子结点的指针。

另一个是表头数组的表头结点，如图1-12所示  
![在这里插入图片描述][20200617141139675.png_pic_center]

图1-12  
data是数据域，存储某结点的数据信息，firstchild是头指针域，存储该结点的孩子链表的头指针。

//树的孩子表示法结构定义
    #define MAX_TRUE_SIZE 100
    typedef struct CTNode  //孩子结点
    {
        
    	int child；
    	struct CTNode *next;
    }*ChildPtr;
    //表头结构
    typedef struct
    {
        
    	TElemType data;
    	ChildPtr firstchild;
    }CTBox;
    //树结构
    typedef struct
    {
        
    	CTBox nodes[MAX_TRUE_SIZE];  //结点数组
    	int r,n;               //根的位置和结点数
    }CTree

这样的结构对于我们要查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。对于遍历整棵树也是很方便的，对于头结点的数组循环即可。  
但是这也存在问题，我们如何知道某个结点的双亲是谁了？比较麻烦，需要调整整颗遍历树才行，难道就不可以把双亲表示法和孩子表示法综合一下吗？当然是可以的。图1-13所示。

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

图1-13  
这种表示法叫做双亲孩子表示法，应该算是孩子表示法的改进。

## 孩子兄弟表示法 ##

**任一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此。我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。** 结点结构表图1-14所示。  
![在这里插入图片描述][20200617181157906.png_pic_center]

图1-14  
data是数据域，fitstchild为指针域，存储该结点的第一个孩子结点的存储地址，rightsib是指针域，存储该结点的右兄弟结点的存储位置。

//孩子兄弟表示法结构定义
    typedef struct CSDNode
    {
        
    	TElemType data;
    	struct CSNode *firstchild,*rightsib;
    }CSNode,*CSTree;

对于图1-1的树来说，这种方法的示意图如1-15所示。  
![在这里插入图片描述][20200617181641506.png_pic_center]

图1-15  
这种表示法，给查找某个结点的某个孩子带来了方便，只需要通过firstchild找到此结点的长子，然后在通过长子结点的rightsib找到它的二弟，接着一直找下去，直到找到具体的孩子。

[20200617124455959.png_pic_center]: https://img-blog.csdnimg.cn/20200617124455959.png#pic_center
[20200617130322946.png_pic_center]: https://img-blog.csdnimg.cn/20200617130322946.png#pic_center
[20200617130414841.png_pic_center]: https://img-blog.csdnimg.cn/20200617130414841.png?#pic_center
[20200617131405266.png_pic_center]: https://img-blog.csdnimg.cn/20200617131405266.png#pic_center
[20200617131853463.png_pic_center]: https://img-blog.csdnimg.cn/20200617131853463.png#pic_center
[20200617134403546.png_pic_center]: https://img-blog.csdnimg.cn/20200617134403546.png#pic_center
[20200617135138902.png_pic_center]: https://img-blog.csdnimg.cn/20200617135138902.png#pic_center
[20200617135734868.png_pic_center]: https://img-blog.csdnimg.cn/20200617135734868.png#pic_center
[2020061713590553.png_pic_center]: https://img-blog.csdnimg.cn/2020061713590553.png#pic_center
[20200617140417452.png_pic_center]: https://img-blog.csdnimg.cn/20200617140417452.png#pic_center
[20200617140940777.png_pic_center]: https://img-blog.csdnimg.cn/20200617140940777.png#pic_center
[20200617141139675.png_pic_center]: https://img-blog.csdnimg.cn/20200617141139675.png#pic_center
[20200617143909367.png_pic_center]: https://img-blog.csdnimg.cn/20200617143909367.png#pic_center
[20200617181157906.png_pic_center]: https://img-blog.csdnimg.cn/20200617181157906.png#pic_center
[20200617181641506.png_pic_center]: https://img-blog.csdnimg.cn/20200617181641506.png#pic_center