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