树的存储结构

时间:2021-04-15 13:00:18

原文地址:http://student.zjzk.cn/course_ware/data_structure/web/shu/shu6.5.2.1.htm

本节仅讨论树的三种常用表示法。

1.双亲链表表示法
     双亲链表表示法利用树中每个结点的双亲唯一性,在存储结点信息的同时,为每个结点附设一个指向其双亲的指针parent,惟一地表示任何-棵树。
(1)双亲链表表示法的实现
 方法① 用动态链表实现
 方法② 用向量表示——更为方便

(2)双亲链表向量表示的形式说明
  #define MaxTreeSize 100 //向量空间的大小,由用户定义
  typedef char DataType; //应由用户定义
  typedef struct{
      DataType data;//结点数据
      int parent; //双亲指针,指示结点的双亲在向量中的位置
    }PTreeNode;
  typedef struct{ 
      PTreeNode nodes[MaxTreeSize];
      int n; //结点总数 
    }PTree;
  PTree T; //T是双亲链表
  注意:
     若T.nodes[i].parent=j,则T.nodes[i]的双亲是T.nodes[j]。

(3)双亲链表表示实例
  【例】图6.17(a)的双亲链表表示如下面数组所示。

树的存储结构树的存储结构

  分析:

     E和F所在结点的双亲域是1,它们的双亲结点在向量中的位置是1,即B是它们的双亲。
  注意:
     ① 根无双亲,其parent域为-1。
     ② 双亲链表表示法中指针parent向上链接,适合求指定结点的双亲或祖先(包括根);求指定结点的孩子或其它后代时,可能要遍历整个数组。



2.孩子链表表示法

(1) 结点结构
① 定长结点
      即树中每个结点均按树的度k来设置指针。
     n个结点的树一共有n*k个指针域,而树中只有n-1条边,故树中的空指针数目为
         kn-(n-1)=n(k-1)+1(k越大,浪费的空间越多)。

②不定长结点
     即树中每个结点按本结点的度来设置指针数,并在结点中增设一个度数域degree指出该结点包含的指针数。
     各结点不等长,虽然节省了空间,但是给运算带来不便。

(2)孩子链表表示法
     孩子链表表示法是为树中每个结点设置一个孩子链表,并将这些结点及相应的孩子链表的头指针存放在一个向量中。

①孩子链表表示法的类型说明
    //以下的DataType和MaxTreeSize由用户定义
    typedef struct CNode{//子链表结点
        int child; //孩子结点在向量中对应的序号
        struct CNode *next;
      }CNode;
    typedef struct{ 
        DataType data; //存放树中结点数据
        CNode *firstchild;//孩子链表的头指针
      }PTNode;
    typedef struct{
        PTNode nodes[MaxTreeSize];
        Int n,root; //n为结点总数,root指出根在向量中的位置
      }CTree;
    Ctree T; //T为孩子链表表示
  注意:
    当结点T.nodes[i]为叶子时,其孩子链表为空,即T.nodes[i].firstchild=NULL。

②孩子链表表示法实例 
【例】图6.17(a)所示树的孩子链表表示T如下面(a)图所示。

树的存储结构树的存储结构


 注意:
     ① 孩子结点的数据域仅存放了它们在向量空间的序号。
     ② 与双亲链表表示法相反,孩子链表表示便于实现涉及孩子及其子孙的运算,但不便于实现与双亲有关的运算。
     ③ 将双亲链表表示法和孩子链表表示法结合起来,可形成双亲孩子链表表示法。
   【例】上面的(b)图就是用双亲链表表示法来存储图6.17(a)中的树。


3.孩子兄弟链表表示法 
(1)表示方法
     在存储结点信息的同时,附加两个分别指向该结点最左孩子和右邻兄弟的指针域leftmostchild和rightsibling,即可得树的孩子兄弟链表表示。

(2)表示实例
  【例】图6.17(a)中树的孩子兄弟链表如下图所示。 
树的存储结构


注意:
     这种存储结构的最大优点是:它和二叉树的二叉链表表示完全一样。可利用二叉树的算法来实现对树的操作。