C語言數(shù)據(jù)結(jié)構(gòu)中樹與森林專項(xiàng)詳解
樹的存儲結(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) } }
樹的層序遍歷(廣度優(yōu)先遍歷)
層次遍歷(用隊(duì)列實(shí)現(xiàn))
①若樹非空,則根節(jié)點(diǎn)入隊(duì)
②若隊(duì)列非空,隊(duì)頭元素出隊(duì)并訪問,同時(shí)將該元素的孩子依次入隊(duì)
③重復(fù)②直到隊(duì)列為空
如圖
森林的遍歷
森林。森林是m (m>0)棵互不相交的樹的集合。每棵樹去掉根節(jié)點(diǎn)后,其各個(gè)子樹又組成森林。
先序遍歷森林
效果等同于依次對各二叉樹進(jìn)行先序遍歷
若森林為非空,則按如下規(guī)則進(jìn)行遍歷:
1.訪問森林中第一棵樹的根結(jié)點(diǎn)
2.先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林。
3.先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。
效果如下
中序遍歷森林
效果等同于依次對二叉樹進(jìn)行中序遍歷
若森林為非空,則按如下規(guī)則進(jìn)行遍歷:
中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林。
訪問第一棵樹的根結(jié)點(diǎn)。
中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。
效果如下
到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)中樹與森林專項(xiàng)詳解的文章就介紹到這了,更多相關(guān)C語言樹與森林內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C語言詳細(xì)分析講解關(guān)鍵字const與volatile的用法
在C語言中,我們經(jīng)常會見到const和volatile這兩個(gè)關(guān)鍵字,那么我們今天就來介紹下這兩個(gè)關(guān)鍵字,提起?const?關(guān)鍵字,我們可能首先想到的是經(jīng)過它修飾的變量便是常量了。其實(shí)我們這種想法是錯(cuò)誤的,其實(shí)?const?修飾的變量是只讀的,其本質(zhì)還是變量2022-04-04C++中設(shè)計(jì)一個(gè)類時(shí)的注意事項(xiàng)分享
這篇文章主要來和大家分享一下C++中,設(shè)計(jì)一個(gè)類要注意哪些東西,這往往也是C++面試時(shí)會考到的問題,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-06-06詳談C++ socket網(wǎng)絡(luò)編程實(shí)例(2)
這篇文章主要為大家介紹了C++ socket網(wǎng)絡(luò)編程實(shí)例,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助2021-11-11C++?move()函數(shù)及priority_queue隊(duì)列使用記錄
move(obj)函數(shù)的功能是把obj當(dāng)做右值處理,可以應(yīng)用在對象的移動上,這篇文章主要介紹了C++?move()函數(shù)及priority_queue隊(duì)列使用記錄,需要的朋友可以參考下2023-01-01VScode配置cuda開發(fā)環(huán)境的實(shí)現(xiàn)步驟
本文主要介紹了VScode配置cuda開發(fā)環(huán)境的實(shí)現(xiàn)步驟,文中通過圖文介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-07-07