数据结构—基础知识（13）：树的存储结构

数据结构—基础知识（13）：树的存储结构

1. 双亲表示法

   这种表示方法中，以一组连续的存储单元存储树的结点，每个结点除了数据域data外，还附设一个parent域用以指示其双亲结点的位置。
   

   这种存储结构利用了每个结点（除根结点外）只有唯一的双亲性质。这种存储结构下，求结点的双亲十分方便，也很容易求树的根，但求结点的孩子时需要遍历整个结构。

2. 孩子表示法

   由于树中每个结点可能有多棵子树，则可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，此时链表中的结点可以有如下图的两种结点格式。
   

   若采用第一种结点格式，则多重链表中的结点是同构的，其中d为树的度。由于树中很多结点的度小于 d，所以链表中有很多空链域，空间较浪费，不难推出，在一棵有n个结点度为k的树中必有n(k-1)+1 个空链域。

   若采用第二种结点格式，则多重链表中的结点是不同构的，其中d为结点的度，degree 域的值同d。此时，虽能节约存储空间，但操作不方便。

   另一种办法是，把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表做存储结构，则n个结点有n个孩子链表(叶子的孩子链表为空表)。而n个头指针又组成一个线性表，为了便于查找，可采用顺序存储结构。

   下图(a)所示为下图中的树的孩子表示法。与双亲表示法相反，孩子表示法便于那些涉及孩子的操作的实现。可以把双亲表示法和孩子表示法结合起来，即将双亲表示和孩子链表合在一起。图(b)所示的就是这种存储结构的一例，它和图(a)表示的是同一棵树。
   

3. 孩子兄弟法

   孩子兄弟法又称二叉树表示法，或者二叉链表表示法，即以二叉链表做树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点(firstchild)和下一个兄弟结点(nextsibling)

   //------树的二叉链表（孩子—兄弟）存储表示------
   typedef struct CSNode{ElemType data;struct CSNode *firstchild,*nextsibling;
   }CSNode,*CSTree;