樹的存儲結(jié)構(gòu)
時間：2018-09-27 來源：未知
1.樹的存儲結(jié)構(gòu)：
(1)雙親表示法
是一種順序保存方法，即用數(shù)組存儲。
每個結(jié)點有兩個域:
data是結(jié)點的數(shù)據(jù)元素;
parent是指出該結(jié)點的雙親結(jié)點在數(shù)組中的下標;
本文引用地址：//www.einuk.cn/emb/Column/7465.html
樹的雙親表示法說明：
#define MAX-TREE-SIZE 100
typedef struct PTNode{
ElementType data;
int parent; // 該結(jié)點的雙親的下標
} PTNode;
typedef struct {
PTNode nodes[MAX-TREE-SIZE];
int n; //樹的結(jié)點數(shù)
} PTree;
例子：使用雙親法存儲森林
(2)孩子(子女)表示法
typedef struct CTNode { //孩子結(jié)點(表結(jié)點)
int child;
struct CTNode *next;
} *ChildPtr;
tyPedef struct { //頭結(jié)點
TElemType data;
ChildPtr firstchild;
}CTBox;
typedef struct { //孩子鏈表頭指針
CTBox nodes[MAX_TREE_SIZE];
int n，r; //結(jié)點數(shù)和根的位置;
}CTree;
帶雙親的孩子鏈表存儲表示
typedef struct CTNode { //孩子結(jié)點(表結(jié)點)
int child;
struct CTNode *next;
} *ChildPtr;
typedef struct{ //頭結(jié)點
TElemType data; int parent;
ChildPtr firstchild;
}CTBox;
typedef struct { //孩子鏈表頭指針
CTBox nodes[MAX_TREE_SIZE];
int n，r; //結(jié)點數(shù)和根的位置;
}CTree;
(3)孩子兄弟表示法(也稱二叉樹表示法或二叉鏈表表示法)
結(jié)點結(jié)構(gòu)(CSNode)：
firstchild:指向該結(jié)點的第一個孩子
nextsibling:指向該結(jié)點的下一個兄弟
typedef struct CSNode {
TElemType data;
struct CSNode * firstchild， * nextsihling;
}CSNode，*CSTree;
例子：用孩子兄弟法存儲樹
2.樹與森林的遍歷
樹的遍歷:按根的次序區(qū)分有兩種遍歷次序
(1)先根序遍歷：
若樹非空，則訪問根節(jié)點;從左到右根遍歷根的每棵子樹;
遍歷上面的樹：A B E C F D G H I J
(2)后根遍歷：
若樹非空，則從左到右后根序遍歷根的每棵子樹;訪問根結(jié)點;
遍歷上面的樹：E B F C H I J G D A
森林的遍歷：
森林的遍歷是基于樹的遍歷完成的，對應有兩種遍歷次序
(1)先序遍歷
訪問第一棵樹的根;
先序遍歷第一棵樹中的根結(jié)點的子樹森林;
先序遍歷其余的樹所構(gòu)成的森林;
(2)中序遍歷
中序遍歷第一棵樹的子樹;
訪問第一棵樹的根;
中序遍歷其余的樹構(gòu)成的森林;
3.森林與二叉樹的轉(zhuǎn)換
在森林與二叉樹之間存在一一對應的關(guān)系
(1)森林=>二叉樹的轉(zhuǎn)換
自然轉(zhuǎn)換法：凡是兄弟用線連起來，然后去掉雙親到子女的連線，但保留雙親到其第一子女的連線，后轉(zhuǎn)45度。
(2)二叉樹=>森林的轉(zhuǎn)換
自然轉(zhuǎn)換法：
若某結(jié)點是其雙親的左孩子，則該結(jié)點的右孩子、右孩子的右孩子...,都是與該結(jié)點的雙親連接起來，后去掉所有雙親到右孩子的連線。
