樹的存儲(chǔ)結(jié)構(gòu)

樹的邏輯結(jié)構(gòu)

樹是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合，n=0時(shí)，稱為空樹，這是一種特殊情況。在任意--棵非空樹中應(yīng)滿足:

1)有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)。

2)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集合T1,2....Tm，其中每個(gè)集合本身又是一-棵樹，并且稱為根結(jié)點(diǎn)的子樹。

雙親表示法（順序存儲(chǔ)）

每個(gè)結(jié)點(diǎn)保存雙親的“指針”， 結(jié)點(diǎn)中保存父節(jié)點(diǎn)在數(shù)組的下標(biāo)

優(yōu)點(diǎn)：找父節(jié)點(diǎn)方便

缺點(diǎn)：找孩子不方便

刪除元素方案一 ，數(shù)據(jù)刪除后，parent 變?yōu)?1

刪除元素方案二，數(shù)據(jù)刪除后，將尾部數(shù)據(jù)填充到那

#define MAX_TREE_SIZE 100    //樹中最多結(jié)點(diǎn)樹 
typedef struct{             //樹的結(jié)點(diǎn)定義 
	Elemtype date;         //數(shù)據(jù)元素 
	int parent;           //雙親位置域  
}PTNode;             
typedef struct{                    //樹的類型定義 
	PTNode nodes[MAX_TREE_SIZE];   //雙親表示 
	int n;                        //結(jié)點(diǎn)樹 
}PTree; 

孩字表示法（順序+鏈?zhǔn)酱鎯?chǔ)）

順序存儲(chǔ)各個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)保存孩子鏈表頭指針

優(yōu)點(diǎn)：找孩子方便

缺點(diǎn)：找雙親不方便

代碼

#define MAX_TREE_SIZE 100    //樹中最多結(jié)點(diǎn)樹 
typedef struct{             //樹的結(jié)點(diǎn)定義 
	Elemtype date;         //數(shù)據(jù)元素 
	int parent;           //雙親位置域  
}PTNode;             
typedef struct{                    //樹的類型定義 
	PTNode nodes[MAX_TREE_SIZE];   //雙親表示 
	int n;                        //結(jié)點(diǎn)樹 
}PTree;
struct CTNOde{
	int child; //孩子結(jié)點(diǎn)在數(shù)組的位置
	struct CTNode *next;   //下一個(gè)孩子 
}CTBox;
typedef struct {
	CTBox nodes[MAX_TREE_SIZE];
	int n,r;   //結(jié)點(diǎn)樹和根的位置 
}; 

孩子兄弟表示法（鏈?zhǔn)酱鎯?chǔ)）

優(yōu)點(diǎn)：可以用二叉樹的操作來(lái)處理樹

代碼

//樹的存儲(chǔ)-孩子兄弟表示法
typedef struct CSDode{
	Elemtype date;                    //數(shù)據(jù)域 
	struct CSDode *firstchild ,*nextsibling;  //第一個(gè)孩子和右兄弟指針 
}CSDode ,*CSTree; 

森林

森林是m（m>=0）棵互不相交的樹集合

森林中各個(gè)樹的根結(jié)點(diǎn)之間是為兄弟關(guān)系

在二叉樹中，如果是兄弟關(guān)系就在右邊，如果是孩子就在左邊，本質(zhì)上，用二叉鏈表存儲(chǔ)森林

樹的遍歷

樹的先根遍歷（深度優(yōu)先遍歷）

先根遍歷。若樹非空，先訪問(wèn)根結(jié)點(diǎn)，在依次對(duì)沒棵子樹進(jìn)行先根遍歷。

上圖這樣一棵樹的先根遍歷順序和二叉樹的很像，按照二叉樹的方法

//樹的先根遍歷
void PreOrder(TreeNode *R){
	if(R!=NULL){
		visit(R);     //訪問(wèn)根結(jié)點(diǎn) 
		while(R還有下一個(gè)子樹T)
		  PreOrder(T);   //先根遍歷下一棵子樹 
	}
} 

樹的后根遍歷（樹的深度優(yōu)先遍歷）

若樹非空，先依次對(duì)沒棵子樹進(jìn)行后根遍歷，最后在訪問(wèn)根結(jié)點(diǎn)

上圖這樣一棵樹的后根遍歷順序和二叉樹的很像，按照二叉樹的方法

代碼

//樹的后根遍歷
void PostOrder(TReeNode *R)
{
	if(R != NULL){
		while(R還有下一個(gè)子樹T)
		   PodtOrder(T);   //后根遍歷下一棵子樹
		visit(R)    //訪問(wèn)根結(jié)點(diǎn) 
	} 
} 

樹的層序遍歷（廣度優(yōu)先遍歷）

層次遍歷（用隊(duì)列實(shí)現(xiàn))

①若樹非空，則根節(jié)點(diǎn)入隊(duì)

②若隊(duì)列非空，隊(duì)頭元素出隊(duì)并訪問(wèn)，同時(shí)將該元素的孩子依次入隊(duì)

③重復(fù)②直到隊(duì)列為空

如圖

森林的遍歷

森林。森林是m (m>0）棵互不相交的樹的集合。每棵樹去掉根節(jié)點(diǎn)后，其各個(gè)子樹又組成森林。

先序遍歷森林

效果等同于依次對(duì)各二叉樹進(jìn)行先序遍歷

若森林為非空，則按如下規(guī)則進(jìn)行遍歷:

1.訪問(wèn)森林中第一棵樹的根結(jié)點(diǎn)

2.先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林。

3.先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。

效果如下

中序遍歷森林

效果等同于依次對(duì)二叉樹進(jìn)行中序遍歷

若森林為非空，則按如下規(guī)則進(jìn)行遍歷:

中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林。

訪問(wèn)第一棵樹的根結(jié)點(diǎn)。

中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。

效果如下

到此這篇關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中樹與森林專項(xiàng)詳解的文章就介紹到這了,更多相關(guān)C語(yǔ)言樹與森林內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！