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

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

樹(shù)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合，n=0時(shí)，稱為空樹(shù)，這是一種特殊情況。在任意--棵非空樹(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è)集合本身又是一-棵樹(shù)，并且稱為根結(jié)點(diǎn)的子樹(shù)。

雙親表示法（順序存儲(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    //樹(shù)中最多結(jié)點(diǎn)樹(shù) 
typedef struct{             //樹(shù)的結(jié)點(diǎn)定義 
	Elemtype date;         //數(shù)據(jù)元素 
	int parent;           //雙親位置域  
}PTNode;             
typedef struct{                    //樹(shù)的類型定義 
	PTNode nodes[MAX_TREE_SIZE];   //雙親表示 
	int n;                        //結(jié)點(diǎn)樹(shù) 
}PTree; 

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

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

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

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

代碼

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

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

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

代碼

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

森林

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

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

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

樹(shù)的遍歷

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

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

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

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

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

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

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

代碼

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

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

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

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

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

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

如圖

森林的遍歷

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

先序遍歷森林

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

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

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

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

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

效果如下

中序遍歷森林

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

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

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

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

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

效果如下

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

最新評(píng)論