樹
樹的存儲
1.雙親表示法：
以一組連續(xù)空間存儲樹的結(jié)點，同時在每個結(jié)點中，附設(shè)一個指示器指向其雙親結(jié)點到鏈表中的位置
#define MAX_TREE_SIZE 100
typedef int ELemType
typedef struct PTNode //結(jié)點結(jié)構(gòu)
{
ElemType data; //結(jié)點數(shù)據(jù)
int partent; //雙親位置
}PTNode;
typedef struct
{
PTNode nodes[MAX_TREE_SIZE]; //結(jié)點數(shù)組
int r; //根
int n;//結(jié)點
}PTree
2.孩子雙親表示法:
把每個結(jié)點的孩子排列起來，以單鏈表做存儲結(jié)構(gòu)，則n個結(jié)點有n個孩子鏈表，如果是葉子結(jié)點則此單鏈表為空。然后n個頭指針有組成一個線性表，采用順序存儲結(jié)構(gòu)，存放進(jìn)入一個一維數(shù)組中.
#define MAX_TREE_SIZE 100
typedef char ElemType
typedef struct CNode //孩子結(jié)構(gòu)
{
int data; 孩子所在數(shù)組的下標(biāo)
struct CNode *next;//指向下一個孩子結(jié)點的指針
}*ChildPtr;
typedef struct //表頭結(jié)構(gòu)
{
ElemType data;//結(jié)點數(shù)據(jù)
ChildPtr firstchild;//指向第一個孩子的指針
}CTbox;
typedef struct //將兩個結(jié)構(gòu)聯(lián)合起來
{
CTbox nodes[MAX_TREE_SIZE];
int r,n;//樹的根，結(jié)點
}
3.孩子兄弟表示法：
我們發(fā)現(xiàn)，任意一顆樹，它的結(jié)點的第一個孩子如果存在就是的，它的右兄弟如果存在也是唯一的。因此，我們設(shè)置兩個指針，分別指向該結(jié)點的第一個孩子和此結(jié)點的右兄弟。
typedef int ElemType
typedef struct CSNode
{
ElemType data;
struct CSNode *firstchild *rightsib;
}CSNode,*CSTree;
