树
树的概念
树的定义
树形结构是一类重要的非线性数据结构。
- 有一个特殊的结点，称为根结点，根节点没有前驱结点。
- 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm ，其中每一个集合Ti(1<= i <= m)又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
因此，树是递归定义的。
树的基本术语
- 结点的度：树中一个结点的子树的个数称为该结点的度。
- 树的度：树中所有结点度的最大值。
- 树的高度（深度）：树中结点的最大层次。
- 路径：树中两个结点之间的路径是由这两个节点之间所经过的结点序列构成的，路径长度为序列中边的个数（即结点个数减一）。
有序树和无序树
- 有序树：结点的子树从左到右是有次序的，不能互换。
- 无序树：结点的子树之间没有顺序关系，随意更改。
有根树和无根树
- 有根树：树的根节点已知且固定。
- 无根树：树的根节点未知且任意。
这个认知主要会影响我们对于树的存储。在存储树结构的时候，我们最重要的就是要存下逻辑关系。
如果是无根树，父子关系不明确，就需要存储下所有情况。比如a和b之间存在一条边，我们需要存储a有一个儿子b，同时b也有一个儿子a。
甚至在部分有根树题目中也需要存储下所有情况。
树的存储
树的存储相较于线性结构更为复杂。存储时需要保存值域，也需要保存结点间的关系。这里我们主要学习孩子表示法。
孩子表示法
孩子表示法即将每个结点的孩子信息存储下来。
对于无根树，因为父子关系不明确，我们需要将与该结点相连的所有的点都存储下来。
vector数组实现
题目描述
给定一棵树，该数包含n个结点，编号分别是1~n。
输入描述
第一行一个整数n，表示n个结点。
接下来n-1行，每行两个整数u和v，表示u和v之间有一条边。
vector是可变长数组，针对于树结构这种一对多的关系，正好可以利用其尾插的高效性来存储。
- 可以创建一个大小为n+1的vector数组edges[n+1]。
- 其中edges[i]表示与结点i相连的所有结点。
代码实现：
#include <iostream>
#include <vector>
using namespace std;const int N = 1e5 + 10;vector<int> edges[N];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);}return 0;
}
链式前向星
链式前向星的本质就是利用数组来模拟链表。
#include <iostream>
using namespace std;const int N = 1e5 + 10;int h[N], e[N * 2], ne[N * 2], id;
int n;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 u, v;cin >> u >> v;add(u, v);add(v, u);}return 0;
}
总结
- vector数组用到了容器vector，较链式前向星更为耗时。
- 通常情况下，两种情况都可以使用，不会因此超时。
做题过程中，任选其一即可。
树的遍历
树的遍历就是不重不漏的将树中所有的点都扫描⼀遍。
在之前学过的线性结构中，遍历就很容易，直接从前往后扫描⼀遍即可。但是在树形结构中，如果不
按照⼀定的规则遍历，就会漏掉或者重复遍历⼀些结点。因此，在树形结构中，要按照⼀定规则去遍
历。常⽤的遍历⽅式有两种，⼀种是深度优先遍历，另⼀种是宽度优先遍历。
深度优先遍历(DFS)
Depth First Search，简称DFS，即深度优先遍历。
深度优先遍历的思想是，从根节点开始，沿着一条路径一直走下去，直到走到叶子节点，然后返回上一个节点，继续沿着另一条路径走下去，直到所有节点都被遍历完。
题目描述
给定一棵树，该数包含n个结点，编号分别是1~n。
输入描述
第一行一个整数n，表示n个结点。
接下来n-1行，每行两个整数u和v，表示u和v之间有一条边。
测试用例：
111 37 33 101 54 52 111 26 1111 811 9
vector数组存储
在使用vector进行存储时，我们会将所有相连元素都存起来，因此可能会存在重复遍历的情况，我们需要另外使用一个数组来记录是否遍历过。
#include <iostream>
#include <vector>
using namespace std;const int N = 1e5 + 10;vector<int> edges[N];
bool st[N];void dfs(int u) {st[u] = true;cout << u << " ";for(auto v : edges[u]){if(!st[v]){dfs(v);}}
}int main(){int n;cin >> n;for(int i = 1;i < n;i++){int a,b;cin >> a >> b;edges[a].push_back(b);edges[b].push_back(a);}dfs(1);
}
链式前向星存储
#include <iostream>
using namespace std;const int N = 1e5 + 10;int h[N],e[N * 2],ne[N * 2],id;
bool st[N];void add(int a,int b){id++;e[id] = x;ne[id] = h[a];h[a] = id;
}void dfs(int u){st[u] = true;cout << u << " ";for(int i = h[u];i;i = ne[i]){int j = e[i];if(!st[j]){dfs(j);}}
}int main(){int n;cin >> n;for(int i = 1;i < n;i++){int a,b;cin >> a >> b;add(a,b); add(b,a);}dfs(1);return 0;
}
时空复杂度：
在整个dfs过程中，会把树中每个边扫描两边，即2*(n-1)，因此时间复杂度为O(n)。
空间复杂度：
最差情况下，树退化成链表，递归深度为n，因此空间复杂度为O(n)。
宽度优先遍历(BFS)
Breadth First Search，简称BFS，即宽度优先遍历。
宽度优先遍历的思想是，从根节点开始，每次都尝试访问同⼀层的节点。如果同⼀层都访问完
了，再访问下⼀层。
具体实现方式：使用队列
- 初始化一个队列。
- 将根节点入队，同时标记该结点已访问。
- 当队列不为空时，取出队头元素，访问该元素，将其所有孩子入队，同时标记这些孩子已访问。
- 重复步骤3，直到队列为空。
题目描述
给定一棵树，该数包含n个结点，编号分别是1~n。
输入描述
第一行一个整数n，表示n个结点。
接下来n-1行，每行两个整数u和v，表示u和v之间有一条边。
测试用例
111 37 33 101 54 52 111 26 1111 811 9
vector数组存储
#include <iostream>
#include <vector>
#include <queue>
using namespace std;const int N = 1e5 + 10;vector<int> edges[N];
queue<int> q;
bool st[N];void bfs(int u){q.push(u);st[u] = true;while(!q.empty()){int t = q.front();q.pop();cout << t << " ";for(auto v : edges[t]){if(!st[v]){q.push(v);st[v] = true;}}}
}int main(){int n;cin >> n;for(int i = 1;i < n;i++){int a,b;cin >> a >> b;edges[a].push_back(b);edges[b].push_back(a);}bfs(1);return 0;
}
链式前向星存储
#include <iostream>
#include <queue>
using namespace std;const int N = 1e5 + 10;int h[N],e[N * 2],ne[N * 2],id;
bool st[N];
queue<int> q;void add(int a,int b){id++;e[id] = b;ne[id] = h[a]; h[a] = id;
}void bfs(int u){q.push(u);st[u] = true;while(!q.empty()){int t = q.front();q.pop();cout << t << " ";for(int i = h[t];i;i = ne[i]){int j = e[i];if(!st[j]){q.push(j);st[j] = true;}}}
}int main(){int n;cin >> n;for(int i = 1;i < n;i++){int a,b;cin >> a >> b;add(a,b);add(b,a);} bfs(1);return 0;
}
时空复杂度：
所有节点入队一次，出队一次，因此时间复杂度为O(n)。
空间复杂度：
最差情况下，所有节点在同一层，此时队列里最多n-1个元素，因此空间复杂度为O(n)。
