樹 - 樹和森林- 樹的存儲結構（二）

　　孩子鏈表表示法

　　() 結點結構

　　① 定長結點

　　即樹中每個結點均按樹的度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)中的樹

From:http://tw.wingwit.com/Article/program/sjjg/201311/23871.html