樹的存儲(chu)結(jie)構(gou)
時間：2018-09-27 來源：未知
1.樹的存儲結構：
(1)雙親表(biao)示法
是一種順序保存(cun)方(fang)法，即用(yong)數(shu)組存(cun)儲。
每個(ge)結點有兩個(ge)域(yu):
data是(shi)結點的(de)數(shu)據元素;
parent是指(zhi)出該結(jie)點(dian)的雙(shuang)親結(jie)點(dian)在數組中的下標;
本文引用地址：//fsbing.cn/emb/Column/7465.html
樹的雙親(qin)表示法說明：
#define MAX-TREE-SIZE 100
typedef struct PTNode{
ElementType data;
int parent; // 該結點的雙親的下標
} PTNode;
typedef struct {
PTNode nodes[MAX-TREE-SIZE];
int n; //樹的(de)結點(dian)數
} PTree;
例子：使用(yong)雙(shuang)親法存儲(chu)森林(lin)
(2)孩子(子女)表示法
typedef struct CTNode { //孩子結(jie)點(表結(jie)點)
int child;
struct CTNode *next;
} *ChildPtr;
tyPedef struct { //頭(tou)結點
TElemType data;
ChildPtr firstchild;
}CTBox;
typedef struct { //孩(hai)子(zi)鏈表(biao)頭指針
CTBox nodes[MAX_TREE_SIZE];
int n，r; //結點數和根(gen)的位置;
}CTree;
帶雙親(qin)的孩子(zi)鏈表存儲(chu)表示(shi)
typedef struct CTNode { //孩子結點(表(biao)結點)
int child;
struct CTNode *next;
} *ChildPtr;
typedef struct{ //頭結點
TElemType data; int parent;
ChildPtr firstchild;
}CTBox;
typedef struct { //孩子鏈表頭指針
CTBox nodes[MAX_TREE_SIZE];
int n，r; //結點數和根的位(wei)置;
}CTree;
(3)孩子兄弟表示(shi)法(也稱二(er)叉樹表示(shi)法或(huo)二(er)叉鏈表表示(shi)法)
結點結構(CSNode)：
firstchild:指向該結(jie)點的第一(yi)個孩子
nextsibling:指向該結點的下一個兄弟
typedef struct CSNode {
TElemType data;
struct CSNode * firstchild， * nextsihling;
}CSNode，*CSTree;
例子：用孩子兄弟法存儲樹
2.樹與森林的遍歷
樹的遍(bian)歷(li):按(an)根(gen)的次序區分有(you)兩(liang)種(zhong)遍(bian)歷(li)次序
(1)先根序遍歷(li)：
若樹(shu)非空，則訪問(wen)根(gen)節點;從左(zuo)到右根(gen)遍歷根(gen)的(de)每(mei)棵子樹(shu);
遍歷上面(mian)的樹：A B E C F D G H I J
(2)后根(gen)遍歷：
若(ruo)樹非(fei)空，則從左到右后根序遍歷根的每(mei)棵子樹;訪問根結點;
遍歷上面的樹：E B F C H I J G D A
森林的遍歷：
森林的(de)(de)遍歷是基于樹的(de)(de)遍歷完成的(de)(de)，對應有兩種(zhong)遍歷次(ci)序
(1)先序遍歷
訪(fang)問第一棵樹的(de)根;
先序遍(bian)歷第一棵(ke)樹中的根結點的子樹森林;
先序遍歷其(qi)余的樹所構成的森林;
(2)中序遍(bian)歷
中序(xu)遍歷第(di)一棵樹的子樹;
訪問(wen)第一棵樹的根;
中序(xu)遍歷其余的樹(shu)構成的森林;
3.森林與二叉樹的轉換
在(zai)森林與(yu)二叉樹之間(jian)存在(zai)一(yi)一(yi)對(dui)應的關系(xi)
(1)森林=>二叉樹的(de)轉(zhuan)換
自然轉(zhuan)(zhuan)換法：凡是兄弟用(yong)線(xian)連(lian)起來，然后去(qu)掉雙(shuang)(shuang)親到子女的(de)連(lian)線(xian)，但(dan)保留雙(shuang)(shuang)親到其第一子女的(de)連(lian)線(xian)，后轉(zhuan)(zhuan)45度。
(2)二(er)叉樹=>森林的轉換
自然轉換法：
若(ruo)某結點是(shi)其雙親(qin)的左孩(hai)子(zi)(zi)(zi)，則該結點的右孩(hai)子(zi)(zi)(zi)、右孩(hai)子(zi)(zi)(zi)的右孩(hai)子(zi)(zi)(zi)...,都是(shi)與(yu)該結點的雙親(qin)連接起(qi)來，后去掉所有雙親(qin)到右孩(hai)子(zi)(zi)(zi)的連線。
