树 - 树和森林- 树的存储结构(二)

如题所述

第1个回答  2022-11-12

   孩子链表表示法

  ( ) 结点结构

  ① 定长结点

  即树中每个结点均按树的度k来设置指针

  n个结点的树一共有n*k个指针域 而树中只有n 条边 故树中的空指针数目为

  kn (n )=n(k )+ (k越大 浪费的空间越多)

  ②不定长结点

  即树中每个结点按本结点的度来设置指针数 并在结点中增设一个度数域degree指出该结点包含的指针数

  各结点不等长 虽然节省了空间 但是给运算带来不便

  ( )孩子链表表示法

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

  ①孩子链表表示法的类型说明

  //以下的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

  ②孩子链表表示法实例

  【例】图 (a)所示树的孩子链表表示T如下面(a)图所示

  

  

  注意

  ① 孩子结点的数据域仅存放了它们在向量空间的序号

  ② 与双亲链表表示法相反 孩子链表表示便于实现涉及孩子及其子孙的运算 但不便于实现与双亲有关的运算

  ③ 将双亲链表表示法和孩子链表表示法结合起来 可形成双亲孩子链表表示法

  【例】上面的(b)图就是用双亲链表表示法来存储图 (a)中的树

lishixinzhi/Article/program/sjjg/201311/23871

相似回答
大家正在搜