日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C語言數據結構中樹與森林專項詳解_C 語言

作者：莫淺子 ? 更新時間： 2022-12-07 編程語言

樹的存儲結構

樹的邏輯結構

樹是n(n≥0)個結點的有限集合，n=0時，稱為空樹，這是一種特殊情況。在任意--棵非空樹中應滿足:

1)有且僅有一個特定的稱為根的結點。

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

雙親表示法（順序存儲）

每個結點保存雙親的“指針”， 結點中保存父節點在數組的下標

優點：找父節點方便

缺點：找孩子不方便

刪除元素方案一 ，數據刪除后，parent 變為-1

刪除元素方案二，數據刪除后，將尾部數據填充到那

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

孩字表示法（順序+鏈式存儲）

順序存儲各個結點，每個結點保存孩子鏈表頭指針

優點：找孩子方便

缺點：找雙親不方便

代碼

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

孩子兄弟表示法（鏈式存儲）

優點：可以用二叉樹的操作來處理樹

代碼

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

森林

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

森林中各個樹的根結點之間是為兄弟關系

在二叉樹中，如果是兄弟關系就在右邊，如果是孩子就在左邊，本質上，用二叉鏈表存儲森林

樹的遍歷

樹的先根遍歷（深度優先遍歷）

先根遍歷。若樹非空，先訪問根結點，在依次對沒棵子樹進行先根遍歷。

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

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

樹的后根遍歷（樹的深度優先遍歷）

若樹非空，先依次對沒棵子樹進行后根遍歷，最后在訪問根結點

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

?

代碼

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

樹的層序遍歷（廣度優先遍歷）

層次遍歷（用隊列實現)

①若樹非空，則根節點入隊

②若隊列非空，隊頭元素出隊并訪問，同時將該元素的孩子依次入隊

③重復②直到隊列為空

如圖

森林的遍歷

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

先序遍歷森林

效果等同于依次對各二叉樹進行先序遍歷

若森林為非空，則按如下規則進行遍歷:

1.訪問森林中第一棵樹的根結點

2.先序遍歷第一棵樹中根結點的子樹森林。

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

效果如下

中序遍歷森林

效果等同于依次對二叉樹進行中序遍歷

若森林為非空，則按如下規則進行遍歷:

中序遍歷森林中第一棵樹的根結點的子樹森林。

訪問第一棵樹的根結點。

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

效果如下

原文鏈接：https://blog.csdn.net/qq_64691289/article/details/127499369

欄目分類
最近更新