|
本节仅讨论树的三种常用表示法 双亲链表表示法双亲链表表示法利用树中每个结点的双亲唯一性在存储结点信息的同时为每个结点附设一个指向其双亲的指针parent惟一地表示任何棵树 （）双亲链表表示法的实现 方法① 用动态链表实现 方法② 用向量表示——更为方便 （）双亲链表向量表示的形式说明 #define MaxTreeSize //向量空间的大小由用户定义 typedef char DataType //应由用户定义 typedef struct{ DataType data//结点数据 int parent //双亲指针指示结点的双亲在向量中的位置 }PTreeNode typedef struct{ PTreeNode nodes[MaxTreeSize]; int n //结点总数 }PTree PTree T //T是双亲链表 注意 若Tnodes[i]parent=j则Tnodes[i]的双亲是Tnodes[j] （）双亲链表表示实例 【例】图(a)的双亲链表表示如下面数组所示 分析 E和F所在结点的双亲域是它们的双亲结点在向量中的位置是即B是它们的双亲 注意 ① 根无双亲其parent域为 ② 双亲链表表示法中指针parent向上链接适合求指定结点的双亲或祖先(包括根)求指定结点的孩子或其它后代时可能要遍历整个数组 孩子链表表示法 （） 结点结构 ① 定长结点即树中每个结点均按树的度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 nroot //n为结点总数root指出根在向量中的位置 }CTree Ctree T //T为孩子链表表示 注意 当结点Tnodes[i]为叶子时其孩子链表为空即Tnodes[i]firstchild=NULL ②孩子链表表示法实例 【例】图(a)所示树的孩子链表表示T如下面(a)图所示 注意 ① 孩子结点的数据域仅存放了它们在向量空间的序号 ② 与双亲链表表示法相反孩子链表表示便于实现涉及孩子及其子孙的运算但不便于实现与双亲有关的运算 ③ 将双亲链表表示法和孩子链表表示法结合起来可形成双亲孩子链表表示法 【例】上面的(b)图就是用双亲链表表示法来存储图(a)中的树 孩子兄弟链表表示法 （）表示方法 在存储结点信息的同时附加两个分别指向该结点最左孩子和右邻兄弟的指针域leftmostchild和rightsibling即可得树的孩子兄弟链表表示 （）表示实例 【例】图．(a)中树的孩子兄弟链表如下图所示 注意 这种存储结构的最大优点是它和二叉树的二叉链表表示完全一样可利用二叉树的算法来实现对树的操作 |
