色偷偷偷亚洲综合网另类,亚洲欧美另类在线观看,欧美午夜激情在线,久久久精品一区

1.樹的存儲結(jié)構(gòu)：

(1)雙親表示法

是一種順序保存方法，即用數(shù)組存儲。

每個結(jié)點有兩個域:

data是結(jié)點的數(shù)據(jù)元素;

parent是指出該結(jié)點的雙親結(jié)點在數(shù)組中的下標(biāo);

本文引用地址：//www.17old.cn/emb/Column/7465.html

樹的雙親表示法說明：

#define MAX-TREE-SIZE 100

typedef struct PTNode{

ElementType data;

int parent; // 該結(jié)點的雙親的下標(biāo)

} 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

森林的遍歷：

森林的遍歷是基于樹的遍歷完成的，對應(yīng)有兩種遍歷次序

(1)先序遍歷

訪問第一棵樹的根;

先序遍歷第一棵樹中的根結(jié)點的子樹森林;

先序遍歷其余的樹所構(gòu)成的森林;

(2)中序遍歷

中序遍歷第一棵樹的子樹;

訪問第一棵樹的根;

中序遍歷其余的樹構(gòu)成的森林;

3.森林與二叉樹的轉(zhuǎn)換

在森林與二叉樹之間存在一一對應(yīng)的關(guān)系

(1)森林=>二叉樹的轉(zhuǎn)換

自然轉(zhuǎn)換法：凡是兄弟用線連起來，然后去掉雙親到子女的連線，但保留雙親到其第一子女的連線，后轉(zhuǎn)45度。

(2)二叉樹=>森林的轉(zhuǎn)換

自然轉(zhuǎn)換法：

若某結(jié)點是其雙親的左孩子，則該結(jié)點的右孩子、右孩子的右孩子...,都是與該結(jié)點的雙親連接起來，后去掉所有雙親到右孩子的連線。