数据结构进阶：树与递归之美

树是一个对于我这种小白来说是接触的第一个较复杂的数据结构，不像之前的线性结构，树让人感觉是从一个线到面的进阶。

树的定义是由一个根节点和许多子节点组成，再由子节点成为新的根节点有点像递归的过程，因此树的许多操作都要有递归的参与。

树的基本术语：

节点的度：树中的节点的子节点的个数称为度。

树的度：树中节点最大的度。

树的高度：树的层数或者深度。

路径：两个子结点之间的距离。

树又分为有根树和无根树，无序树指的是树的根是变化的根节点可以是子节点，子节点可以是根节点。有根树的根节点是固定的。树又分为有序树和无序树，有序树中树的子节点不可变化，无序树反之。

树的储存是一个相较于线性结构完全不同的，由于一对多的特性，使得他的存储变得困难。当我们在处理无根树时，由于根的不确定性，所以应在每个节点相互存储两次。对此我们有两种存储方式；vector数组和链式前向星。

vector数组是将以根节点为数组名的数组中存储他的子节点。

#include <iostream> #include <vector> using namespace std; const int N = 1e5 + 10; int n;//节点的个数 vector<int>edges[N]; int main() { cin >> n; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; edges[u].push_back(v); edges[v].push_back(u);//由于没有固定的根节点，需要相互储存 } return 0; }

链式前向向星指的是用链表进行存储。

#include <iostream> using namespace std; const int N = 1e5 + 10; int h[N], e[2 * N], ne[2 * N]; int n, id; void add(int a, int b) { id++; e[id] = b; ne[id] = h[a]; h[a] = id; } int main() { cin >> n; for(int i; i < n; i++) { int a, b; cin >> a >> b; add(a,b); add(b,a);//要将两种根的情况存储 } return 0; }

树的遍历如果按照之前的方法随便遍历的话，很容易漏掉数据。因此树有它特有的两种遍历方式，深度优先遍历DFS和宽度优先遍历BFS。

深度优先遍历是由根节点为起点一直往子节点的子节点不断遍历，直到找到叶子节点（没有子节点）时，原路返回至其他子节点再进行遍历，直到将所有数据遍历完结束。

#include <iostream> #include <vector> using namespace std; const int N = 1e6 + 10; vector<int>edges[N]; int n; bool st[N];//由于根节点不知，要将历遍过的节点标记防止死循环 void dfs(int u)//以它为根节点的往后的子节点 { cout << u <<" "; st[u] = true; for(auto v : edges[u]) { if(!st[v]) { dfs(v); } } } int main() { int n; cin >> n; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; edges[u].push_back(v); edges[v].push_back(u); } dfs(1);//以1为根结点的树 }

上述使用的是vector数组储存的树的深度优先遍历，接下来使用链式前向星再来模拟一次。要点：由于根节点的未知，要使用额外的bool 数组来标记已历遍过的数据。

#include <iostream> using namespace std; const int N = 1e6 + 10; int h[N], e[N * 2], ne[N * 2]; int id, n; bool st[N]; void add(int a,int b) { id++; e[id] = b; ne[id] = h[a]; h[a] = id; } int dfs(int u) { cout << u <<" "; st[u] = true; for(int i = h[a]; i = ne[id]) { int v = e[i]; if(!st[v]) { dfs(v); } } } int main() { cin >> n; for(int i = 1; i < n; i++) { int a, b; cin >> a >> b; add(a,b); add(b,a); } dfs(1); }

现在介绍宽度优先遍历，也叫广度优先遍历，指的是将同一层的节点遍历完后再遍历下一层。所以根据队列的特性，我们可以应用queue来完成这个遍历。

我们还是先用vector数组的存储方法来模拟：（不要忘了将已遍历过了的点标记 ，与之前相同）

#include <iostream> #include <vector> #include <queue> using namespace std; const int N = 1e6 + 10; vector<int>edges[N]; int n; bool st[N]; void bfs() { queue<int>q; q.push(1); while (q.size()) { int u = q.front(); q.pop(); cout << u << " "; for (auto v : edges[u]) { if (!st[v]) { q.push(v); st[v] = true; } } } } int main() { cin >> n; for (int i = 1; i < n; i++) { int u, v; edges[u].push_back(v); edges[v].push_back(u); } bfs(); }

再来使用链式前向星来储存时的bfs：

#include <iostream> #include <queue> using namespace std; const int N = 1e6 + 10; int h[N], e[N * 2], ne[N * 2]; int n, id; bool st[N]; void add(int a, int b) { id++; e[id] = b; ne[id] = h[a]; h[a] = id; } void bfs() { queue<int>q; q.push(1); while (q.size()) { int 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; } } } } int main() { cin >> n; for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; add(a, b); add(b, a); } bfs(); }#include <iostream> #include <queue> using namespace std; const int N = 1e6 + 10; int h[N], e[N * 2], ne[N * 2]; int n, id; bool st[N]; void add(int a, int b) { id++; e[id] = b; ne[id] = h[a]; h[a] = id; } void bfs() { queue<int>q; q.push(1); while (q.size()) { int 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; } } } } int main() { cin >> n; for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; add(a, b); add(b, a); } bfs(); }

树的种类还有许多可分为N叉树，我认为树的进阶和之后的节点的捆绑就是类似图的数据结构吧，当然纯属个人想法，等到学到该内容再与大家讨论。