|
本节仅讨论树的三种常用表示法 双亲链表表示法 双亲链表表示法利用树中每个结点的双亲唯一性在存储结点信息的同时为每个结点附设一个指向其双亲的指针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向上链接适合求指定结点的双亲或祖先(包括根);求指定结点的孩子或其它后代时可能要 遍历整个数组 |
