快捷導(dǎo)航

C語言數(shù)據(jù)結(jié)構(gòu)中樹與森林專項(xiàng)詳解

更新時(shí)間：2022年11月07日 09:51:08 作者：莫淺子

這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu)中樹與森林，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧

樹的存儲結(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)的子樹。

雙親表示法（順序存儲）

每個(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)酱鎯Γ?/h3>

順序存儲各個(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)酱鎯Γ?/h3>

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

代碼

//樹的存儲-孩子兄弟表示法
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ì)上，用二叉鏈表存儲森林

樹的遍歷

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

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

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

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

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

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

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

代碼

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