数据结构与算法----树(中)

hey,我们继续上篇文章学习树。上篇文章，我们主要讲了树的一些基本概念、定义，抽象数据结构。今天，我们要学习它的数据结构，让我们开始学习吧。

树的存储结构:

一讲到存储结构，就会想到顺序存储与链式存储，让我们来回顾一下它们的概念。顺序存储，就是用一组连续的内存地址来存储数据元素，我们一般用一维数组来表示连续的内存地址。链式存储，用一块儿空闲的内存区域来存放数据元素。存放数据的地址不需要连续，通过元素中的指针域来表示逻辑关系。像之前我们学习的线性表，因为它是有唯一先驱、唯一后继。所以，顺序存储可以很好的表示出它的逻辑关系，链式存储也可很好得表示出它们的逻辑关系。而树这种数据结构，它有多棵子树，多个孩子结点，单是使用顺序存储、链式存储，是不能很好的显示出它们的逻辑关系的。我们需要通过集合这两种存储结构来存储树。

一、双亲表示法:

树虽然很多棵子树，但是子树的根结点是唯一确定的。所以，我们可以采用存储结点双亲的方式来存储树。

data是数据域，存放结点数据。parent是指针域，存放该结点的双亲结点的位置。我们来定义下树的双亲表示法结点的结构:

     /*树的双亲表示法的结点结构定义*/
     #define MAX_TREE_SIZE 100
    type int TElemType /*树结点的数据类型，目前暂定为int*/ 
    typedef struct PTNode  /*结点结构*/
    {
     TElemType data;  /*结点数据*/
    PTNode   parent;  /*双亲位置*/
   }PTNode;

   typedef struct  /*树结构*/
  {
      PTNode nodes[MAX_TREE_SIZE];   /*结点数组*/
       int r,n;  /*根的位置和结点数*/   
 }PTree;

，它所对应的双亲表示法应该为像下图这样子:

因为根结点没有双亲，所以parent指针域为-1.

我们要想查询某结点的双亲，可以通过parent指针，快速查询。但是，如果需要查询孩子结点，那么只能整个遍历。

二、多重链表表示法:

因为树会有多棵子树，所以我们可以使用双链表来表示。就是说，每个结点有多个指针域，分别指向该结点子树的根结点。我们把这种表示法，称为多重链表表示法。但是，每个结点的度数是不同的，也就是每个结点的指针域个数是不同的。这里，我们有两种思路。

第一种:

让每个结点的度数都等于树的度数(树的度数，等于所有结点中度数最大的)，其结构如下图:

其中，data存放结点数据，child1….childd存放该结点子树的根结点地址。

通过上图，大家可以发现，如果结点的度数相差太大，那么会出现很多没用指针域。

第二种:

我们在结点中，加一个计数器，专门记录该结点的度数。

其中data是数据域，存放结点的数据。degree是计数器，存放结点的度数。child1….childd是指针域，指向该结点子树的根结点。

这样一来，就不存在浪费指针域的情况了。可是，这种存储结构也是有弊端的。因为各个结点的结构不同，计数器难以维护，会造成时间上的弊端。

三、孩子表示法:

我们可以通过改进多重链表表示法，来设计出高效的存储结构。首先，我们把所有结点以顺序存储结构存放入一个一维数组中，这样就构成了一个线性表。我们再把每个结点的孩子结点以链式存储结构存入单链表中。如下图:

我们设计两种结点结构，一种是孩子链表的存储结构如下图:

其中child存放某结点的孩子结点在线性表中的数组下标，next指针域，指向下个孩子结点在单链表中的位置。

另一种结点结构，是线性表中表头结点，如下图:

data存放结点数据，firstchild指针域，指向第一个孩子结点在单链表中的位置。

/*树的孩子表示法结构定义*/
#define MAX_TREE_SIZE 100
typedef struct CTNode  /*孩子结点*/
{
     int child;
    struct CTNode  *next;

}*ChildPtr;

typedef struct   /*表头结构*/
{
   TElemType data;
  ChildPtr firstchild;
}CTBox;

typedef struct  /*树结构*/
{
   CTBox nodes[MAX_TREE_SIZE];/*结点数组*/
   int r,n;  /*根的位置和结点数*/
}CTree;

以上是树的孩子表示法结构定义。对于孩子表示法，需要查找结点的孩子结点、兄弟结点，我们查看单链表就可以查到。对于，遍历整棵树，只需遍历表头线性表就可以。

四、孩子兄弟表示法:

以上三种表示法，都是从双亲、孩子的角度来思考的。我们换一下思路，从兄弟的角度来思考一下。如果树中的结点的左孩子存在，即是唯一的。如果右兄弟结点存在，即是唯一的。我们设置两个指针，分别指向该结点的第一个孩子和该结点的右兄弟。如下图：

data是数据域，存放结点的数据。firstchild、rightsib是指针域，分别指向结点的左孩子，右兄弟。

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

兄弟孩子表示法，对查找孩子、兄弟结点提供了方便。我们将上图整理一下：

上图其实就是一棵二叉树，我们可以通过二叉树的性质来操作树。关于二叉树，我们留在下一章讲。我们来复习一下，这章讲的知识。

归纳总结:

这章主要讲了树的几种存储结构，因为树不同与线性表，它的子树个数不确定。单单使用顺序存储、链式存储不能表示树的逻辑结构。所以，需要顺序存储与链式存储配合使用。

我们讲了双亲表示法:因为树中结点的双亲结点是唯一的，我们可以通过记录双亲的方法来表示树的存储结构。多重链表表示法:我们把结点的所有孩子结点都记录下来，这样的方法就是多重链表表示法。孩子表示法:将所有结点以顺序存储的方式放入一维数组中，再用单链表存储孩子结点。孩子兄弟表示法:记录左孩子、有兄弟的方法，来表示树的结构。