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