C語言數據結構中樹與森林專項詳解
樹的存儲結構
樹的邏輯結構
樹是n(n≥0)個結點的有限集合，n=0時，稱為空樹，這是一種特殊情況。在任意--棵非空樹中應滿足:
1)有且僅有一個特定的稱為根的結點。
2)當n>1時，其余結點可分為m(m>0)個互不相交的有限集合T1,2....Tm，其中每個集合本身又是一-棵樹，并且稱為根結點的子樹。
雙親表示法（順序存儲）
每個結點保存雙親的“指針”， 結點中保存父節(jié)點在數組的下標
優(yōu)點：找父節(jié)點方便
缺點：找孩子不方便
刪除元素方案一 ，數據刪除后，parent 變?yōu)?1
刪除元素方案二，數據刪除后，將尾部數據填充到那
#define MAX_TREE_SIZE 100 //樹中最多結點樹
typedef struct{ //樹的結點定義
Elemtype date; //數據元素
int parent; //雙親位置域
}PTNode;
typedef struct{ //樹的類型定義
PTNode nodes[MAX_TREE_SIZE]; //雙親表示
int n; //結點樹
}PTree; 孩字表示法（順序+鏈式存儲）
順序存儲各個結點，每個結點保存孩子鏈表頭指針
優(yōu)點：找孩子方便
缺點：找雙親不方便
代碼
#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; //結點樹和根的位置
}; 孩子兄弟表示法（鏈式存儲）
優(yōu)點：可以用二叉樹的操作來處理樹
代碼
//樹的存儲-孩子兄弟表示法
typedef struct CSDode{
Elemtype date; //數據域
struct CSDode *firstchild ,*nextsibling; //第一個孩子和右兄弟指針
}CSDode ,*CSTree; 森林
森林是m（m>=0）棵互不相交的樹集合
森林中各個樹的根結點之間是為兄弟關系
在二叉樹中，如果是兄弟關系就在右邊，如果是孩子就在左邊，本質上，用二叉鏈表存儲森林
樹的遍歷
樹的先根遍歷（深度優(yōu)先遍歷）
先根遍歷。若樹非空，先訪問根結點，在依次對沒棵子樹進行先根遍歷。
上圖這樣一棵樹的先根遍歷順序和二叉樹的很像，按照二叉樹的方法
//樹的先根遍歷
void PreOrder(TreeNode *R){
if(R!=NULL){
visit(R); //訪問根結點
while(R還有下一個子樹T)
PreOrder(T); //先根遍歷下一棵子樹
}
} 樹的后根遍歷（樹的深度優(yōu)先遍歷）
若樹非空，先依次對沒棵子樹進行后根遍歷，最后在訪問根結點
上圖這樣一棵樹的后根遍歷順序和二叉樹的很像，按照二叉樹的方法
代碼
//樹的后根遍歷
void PostOrder(TReeNode *R)
{
if(R != NULL){
while(R還有下一個子樹T)
PodtOrder(T); //后根遍歷下一棵子樹
visit(R) //訪問根結點
}
} 樹的層序遍歷（廣度優(yōu)先遍歷）
層次遍歷（用隊列實現)
①若樹非空，則根節(jié)點入隊
②若隊列非空，隊頭元素出隊并訪問，同時將該元素的孩子依次入隊
③重復②直到隊列為空
如圖
森林的遍歷
森林。森林是m (m>0）棵互不相交的樹的集合。每棵樹去掉根節(jié)點后，其各個子樹又組成森林。
先序遍歷森林
效果等同于依次對各二叉樹進行先序遍歷
若森林為非空，則按如下規(guī)則進行遍歷:
1.訪問森林中第一棵樹的根結點
2.先序遍歷第一棵樹中根結點的子樹森林。
3.先序遍歷除去第一棵樹之后剩余的樹構成的森林。
效果如下
中序遍歷森林
效果等同于依次對二叉樹進行中序遍歷
若森林為非空，則按如下規(guī)則進行遍歷:
中序遍歷森林中第一棵樹的根結點的子樹森林。
訪問第一棵樹的根結點。
中序遍歷除去第一棵樹之后剩余的樹構成的森林。
效果如下
到此這篇關于C語言數據結構中樹與森林專項詳解的文章就介紹到這了,更多相關C語言樹與森林內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家詳細介紹了C語言實現掃雷游戲，可以自動展開，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-11-11
Cocos2d-x中使用CCScrollView來實現關卡選擇實例
這篇文章主要介紹了Cocos2d-x中使用CCScrollView來實現關卡的選擇實例,本文在代碼中用大量注釋講解了CCScrollView的使用,需要的朋友可以參考下2014-09-09
C++中有兩種類型的枚舉：不限定作用域的枚舉類型和限定作用域的枚舉類型。限定作用域的枚舉類型是C++11標準引入的新類型，對C++11中限定作用域的枚舉類型相關知識感興趣的朋友一起看看吧2022-01-01
野狗優(yōu)化算法(Dingo?Optimization?Algorithm,?DOA)模仿澳大利亞野狗的社交行為。DOA算法的靈感來源于野狗的狩獵策略，即迫害攻擊、分組策略和食腐行為。本文將通過Matlab實現這一算法，感興趣的可以了解一下2022-04-04
本文主要介紹了VS C++頭文件引用提示“未定義標識符”的問題解決，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-07-07
這篇文章主要為大家介紹了C語言算法練習中數組元素排序的四種類型，文中的示例代碼講解詳細，對我們學習C語言有一定幫助，需要的可以參考一下2022-12-12
這篇文章主要為大家詳細介紹了C++實現航空訂票系統(tǒng)課程設計，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要介紹了使用C語言解決字符串全排列問題,文中包括了一道ACM相關的競賽題目作為實例,需要的朋友可以參考下2015-08-08
這篇文章主要分享的是面試官常用的16個c/c++面試題，?C中static有什么作用、C++中const有什么用？C與C++各自是如何定義常量的？有什么不同？等等問題，具有一定的參考資料，需要的小伙伴可以參考一下2022-01-01
strcmp函數語法為“int strcmp(char *str1,char *str2)”，其作用是比較字符串str1和str2是否相同，如果相同則返回0，如果不同，前者大于后者則返回1，否則返回-12022-05-05