孩子链表表示法
( ) 结点结构
① 定长结点
即树中每个结点均按树的度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