树的存储
树的父亲表示法
// datastring nodes[N];int fa[N];fa[0] = -1;void add(int b, int a) { fa[b] = a;}二叉树的儿子表示法
struct Node { string data; int lc; // 未应用指针 int rc; // 未应用指针 Node() { lc = rc = -1; }};Node nodes[N];二叉树的数组表示法
// datastring nodes[N];// ch[i][0]示意左儿子，ch[i][1]示意右儿子int ch[N][2];树与图的存储
树是一种非凡的图，与图的存储形式雷同。
无向图也是一种非凡的有向图。对于无向图中的边 xy ，存储两条有向边 x->y , y->x 。因而咱们能够只思考有向图的存储。
邻接矩阵（浓密图）
bool g[N][N];void add(int x, int y) { g[x][y] = 1; }邻接表（稠密图）
#include <vector>std::vector<int> g[N];// 增加一条边x->yvoid add(int x, int y) { g[x].push_back(y); }树与图的遍历
深度优先遍历（邻接表）
void dfs(int i) { st[i] = true; // 点i曾经被遍历过 for (auto j : g[i]) if (!st[j]) dfs(j);}宽度优先遍历（邻接表）
void bfs(int i) { queue<int> q; q.push(i); st[i] = true; // 点i曾经被遍历过 while (!q.empty()) { int t = q.front(); q.pop(); for (auto j : g[t]) if (!st[j]) { q.push(j); st[j] = true; // 点j曾经被遍历过 } }}