一、樹(shù)的定義

樹(shù)的定義
樹(shù)型結(jié)構(gòu)是?類重要的?線性數(shù)據(jù)結(jié)構(gòu)。
? 有?個(gè)特殊的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。
? 除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成M個(gè)互不相交的集合T1 、T2 、...、Tm T，其中每?個(gè)集合?是?棵樹(shù)，稱這棵樹(shù)為根節(jié)點(diǎn)的?樹(shù)。
因此，樹(shù)是遞歸定義的。

樹(shù)的基本術(shù)語(yǔ)
? 結(jié)點(diǎn)的度：樹(shù)中?個(gè)結(jié)點(diǎn)孩?的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。
? 樹(shù)的度：樹(shù)中結(jié)點(diǎn)最?的度數(shù)稱為樹(shù)的度。
? 樹(shù)的?度（深度）：樹(shù)中結(jié)點(diǎn)的最?層數(shù)稱為樹(shù)的?度（深度）。
? 路徑：樹(shù)中兩個(gè)結(jié)點(diǎn)之間的路徑是由這兩個(gè)結(jié)點(diǎn)之間所經(jīng)過(guò)的結(jié)點(diǎn)序列構(gòu)成的，路徑?度為序列中邊的個(gè)數(shù)。

有序樹(shù)和?序樹(shù)
? 有序樹(shù)：結(jié)點(diǎn)的?樹(shù)按照從左往右的順序排列，不能更改。
? ?序樹(shù)：結(jié)點(diǎn)的?樹(shù)之間沒(méi)有順序，隨意更改。
這個(gè)認(rèn)知會(huì)在我們后續(xù)學(xué)習(xí)?叉樹(shù)的時(shí)候?到，因?yàn)?叉樹(shù)需要區(qū)分左右孩?。

有根樹(shù)和?根樹(shù)
? 有根樹(shù)：樹(shù)的根節(jié)點(diǎn)已知，是固定的。
? ?根樹(shù)：樹(shù)的根節(jié)點(diǎn)未知，誰(shuí)都可以是根結(jié)點(diǎn)。
這個(gè)認(rèn)知主要會(huì)影響我們對(duì)于樹(shù)的存儲(chǔ)。在存儲(chǔ)樹(shù)結(jié)構(gòu)的時(shí)候，我們最重要的就是要存下邏輯關(guān)系。如果是?根樹(shù)，??關(guān)系不明確，此時(shí)我們需要把所有的情況都存下來(lái)。?如a和b之間有?條邊，我們不僅要存a有?個(gè)孩?b，也要存b有?個(gè)孩?a。
甚?有的時(shí)候，在有根樹(shù)的題??，也要這樣存儲(chǔ)。

二、樹(shù)的存儲(chǔ)

孩?表?法：

孩?表?法是將每個(gè)結(jié)點(diǎn)的孩?信息存儲(chǔ)下來(lái)。
如果是在?根樹(shù)中，??關(guān)系不明確，我們會(huì)將與該結(jié)點(diǎn)相連的所有的點(diǎn)都存儲(chǔ)下來(lái)。

實(shí)現(xiàn)?式?：vector數(shù)組實(shí)現(xiàn)

案例：
題?描述：
給定?棵樹(shù)，該樹(shù)?共有n 個(gè)結(jié)點(diǎn)，編號(hào)分別是1 ～ n 。
輸?描述：
第???個(gè)整數(shù)n ，表?n 個(gè)結(jié)點(diǎn)。
接下來(lái)n ? 1 ?，每?兩個(gè)整數(shù)u, v ，表?u 和v 之間有?條邊。vector是可變?數(shù)組，如果只涉及尾插，效率還是可以的。?樹(shù)結(jié)構(gòu)這種?對(duì)多的關(guān)系，正好可以利?尾插，把所有的關(guān)系全部存起來(lái)。

? 因此，可以創(chuàng)建?個(gè)??為n + 1 的vector 數(shù)組edges[n + 1] 。
? 其中edges[i] ??就保存著i 號(hào)結(jié)點(diǎn)所連接的結(jié)點(diǎn)。

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int n;
vector<int> edges[N]; // 存儲(chǔ)樹(shù) 
int main()
{cin >> n;for(int i = 1; i < n; i++){int a, b; cin >> a >> b;// a 和 b 之間有?條邊 edges[a].push_back(b);edges[b].push_back(a);}return 0;
}

實(shí)現(xiàn)?式?：鏈?zhǔn)角跋蛐?/h4>

鏈?zhǔn)角跋蛐堑谋举|(zhì)就是?數(shù)組來(lái)模擬鏈表。

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
// 鏈?zhǔn)角跋蛐?
int h[N], e[N * 2], ne[N * 2], id;
int n;
// 其實(shí)就是把 b 頭插到 a 所在的鏈表后? 
void add(int a, int b)
{id++;e[id] = b;ne[id] = h[a];h[a] = id;
}
int main()
{cin >> n;for(int i = 1; i < n; i++){int a, b; cin >> a >> b;// a 和 b 之間有?條邊 add(a, b); add(b, a);}return 0;
}

三、樹(shù)的遍歷

樹(shù)的遍歷就是不重不漏的將樹(shù)中所有的點(diǎn)都掃描?遍。
在之前學(xué)過(guò)的線性結(jié)構(gòu)中，遍歷就很容易，直接從前往后掃描?遍即可。但是在樹(shù)形結(jié)構(gòu)中，如不
按照?定的規(guī)則遍歷，就會(huì)漏掉或者重復(fù)遍歷?些結(jié)點(diǎn)。因此，在樹(shù)形結(jié)構(gòu)中，要按照?定規(guī)則去遍歷。常?的遍歷?式有兩種，?種是深度優(yōu)先遍歷，另?種是寬度優(yōu)先遍歷。

深度優(yōu)先遍歷-DFS

（?ppt展?，效果更佳）
深度優(yōu)先遍歷，英?縮寫(xiě)為DFS，全稱是DepthFirstSearch，中?名是深度優(yōu)先搜索，是?種?于遍歷或搜索樹(shù)或圖的算法。所謂深度優(yōu)先，就是說(shuō)每次都嘗試向更深的節(jié)點(diǎn)?，也就是?條路?到?。
具體流程：
1. 從根節(jié)點(diǎn)出發(fā)，依次遍歷每?棵?樹(shù)；
2. 遍歷?樹(shù)的時(shí)候，重復(fù)第?步。
因此，深度優(yōu)先遍歷是?種遞歸形式的遍歷，可以?遞歸來(lái)實(shí)現(xiàn)。

案例：
題?描述：
給定?棵樹(shù)，該樹(shù)?共有n 個(gè)結(jié)點(diǎn)，編號(hào)分別是1~n 。
輸?描述：
第???個(gè)整數(shù)n ，表?n 個(gè)結(jié)點(diǎn)。
接下來(lái)n ? 1 ?，每?兩個(gè)整數(shù)u, v ，表?u 和v 之間有?條邊。

1、?vector數(shù)組存儲(chǔ)

注：存儲(chǔ)樹(shù)結(jié)構(gòu)的時(shí)候，會(huì)把相鄰的所有結(jié)點(diǎn)都存下來(lái)，這樣在掃描?樹(shù)的時(shí)候會(huì)直接掃描到上?
層，這不是我們想要的結(jié)果。
因此，需要?個(gè)st 數(shù)組來(lái)標(biāo)記，哪些結(jié)點(diǎn)已經(jīng)訪問(wèn)過(guò)，接下來(lái)dfs 的時(shí)候，就不去遍歷那些點(diǎn)

int n;
vector<int> edges[N]; // edges[i] 保存著 i 號(hào)結(jié)點(diǎn)相連的所有點(diǎn) 
bool st[N]; // 標(biāo)記當(dāng)前結(jié)點(diǎn)是否已經(jīng)被遍歷過(guò) 
// 當(dāng)前遍歷到 u 這棵?樹(shù) 
void dfs1(int u)
{// 先訪問(wèn)該點(diǎn) cout << u << " ";st[u] = true; // 標(biāo)記該點(diǎn)已經(jīng)被訪問(wèn)過(guò) // 訪問(wèn)它的?樹(shù) for(auto v : edges[u]){if(!st[v]) dfs1(v); // 如果沒(méi)有遍歷過(guò)，再去遍歷 }
}
// ? vector 數(shù)組 
void test1()
{cin >> n;for(int i = 1; i <= n - 1; i++){int a, b; cin >> a >> b; // 讀??條邊 edges[a].push_back(b); // 保存 a -> b 的?條邊 edges[b].push_back(a); // 保存 b -> a 的?條邊 }dfs1(1);
}

2、鏈?zhǔn)较蚯靶谴鎯?chǔ)

int n;
int h[N], e[N * 2], ne[N * 2], id;
bool st[N]; // 標(biāo)記當(dāng)前結(jié)點(diǎn)是否已經(jīng)被遍歷過(guò) 
void add(int a, int b)
{id++;e[id] = b; // 搞?個(gè)格?，存 b // 把 b 頭插在 a 這個(gè)鏈表的后? ne[id] = h[a];h[a] = id;
}
// 當(dāng)前遍歷到 u 這棵?樹(shù) 
void dfs2(int u)
{cout << u << " ";st[u] = true;for(int i = h[u]; i; i = ne[i]){int v = e[i];if(!st[v]) dfs2(v);}
}
// ?數(shù)組模擬鏈表 
void test2()
{cin >> n;for(int i = 1; i <= n - 1; i++){int a, b; cin >> a >> b;add(a, b); add(b, a);}dfs2(1);
}

寬度優(yōu)先遍歷-BFS

寬度優(yōu)先遍歷，英?縮寫(xiě)為BFS，全稱是BreadthFirstSearch，也叫?度優(yōu)先遍歷。也是?種?于遍歷或搜索樹(shù)或圖的算法。所謂寬度優(yōu)先。就是每次都嘗試訪問(wèn)同?層的節(jié)點(diǎn)。如果同?層都訪問(wèn)完了，再訪問(wèn)下?層。
算法過(guò)程可以看做是在樹(shù)和圖中，在起點(diǎn)放上?個(gè)細(xì)菌，每秒向周圍的那些?凈的位置擴(kuò)散?層，直到把所有位置都感染。

具體實(shí)現(xiàn)?式：借助隊(duì)列。
1. 初始化?個(gè)隊(duì)列；
2. 根節(jié)點(diǎn)?隊(duì)，同時(shí)標(biāo)記該節(jié)點(diǎn)已經(jīng)?隊(duì)；
3. 當(dāng)隊(duì)列不為空時(shí)，拿出隊(duì)頭元素，訪問(wèn)，然后將隊(duì)頭元素的所有孩??隊(duì)，同時(shí)打上標(biāo)記；
4. 重復(fù)3 過(guò)程，直到隊(duì)列為空。

用vector實(shí)現(xiàn)：

int n;
vector<int> edges[N]; // edges[i] 保存著 i 號(hào)結(jié)點(diǎn)相連的所有點(diǎn) 
bool st[N]; // 標(biāo)記哪些點(diǎn)已經(jīng)?過(guò)隊(duì)了 
void bfs1()
{queue<int> q;q.push(1);st[1] = true;while(q.size()){auto u = q.front(); q.pop();cout << u << " ";// 讓孩??隊(duì) for(auto v : edges[u])//把這點(diǎn)的孩子全部加入進(jìn)來(lái){if(!st[v]){q.push(v);st[v] = true;}}}
}
// ? vector 數(shù)組 
void test1()
{cin >> n;for(int i = 1; i <= n - 1; i++){int a, b; cin >> a >> b; // 讀??條邊 edges[a].push_back(b); // 保存 a -> b 的?條邊 edges[b].push_back(a); // 保存 b -> a 的?條邊 }bfs1();
}

鏈?zhǔn)较蚯靶谴鎯?chǔ)：

int n;
int h[N], e[N * 2], ne[N * 2], id;
bool st[N]; // 標(biāo)記哪些點(diǎn)已經(jīng)?過(guò)隊(duì)了 
void add(int a, int b)
{id++;e[id] = b; // 搞?個(gè)格?，存 b // 把 b 頭插在 a 這個(gè)鏈表的后? ne[id] = h[a];h[a] = id;
}
void bfs2()
{queue<int> q;q.push(1);st[1] = true;while(q.size()){auto u = q.front(); q.pop();cout << u << " ";for(int i = h[u]; i; i = ne[i]){int v = e[i];if(!st[v]){q.push(v);st[v] = true;}}}
}
// ?數(shù)組模擬鏈表 
void test2()
{cin >> n;for(int i = 1; i <= n - 1; i++){int a, b; cin >> a >> b;add(a, b); add(b, a);}bfs2();
}