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

　　本節僅討論樹的三種常用表示法

　　雙親鏈表表示法

　　雙親鏈表表示法利用樹中每個結點的雙親唯一性在存儲結點信息的同時為每個結點附設一個指向其雙親的指針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向上鏈接適合求指定結點的雙親或祖先(包括根);求指定結點的孩子或其它後代時可能要

　　遍歷整個數組

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