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)中树的孩子兄弟链表如下图所示。
注意：
这种存储结构的最大优点是：它和二叉树的二叉链表表示完全一样。可利用二叉树的算法来实现对树的操作。
2010-04-15 12:59
饿……你提问了啊！！
A双亲表示法