树的存储
树的父亲表示法
// data
string 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];
二叉树的数组表示法
// data
string 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 std::vector g[N];
// 添加一条边x->y
void 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 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已经被遍历过
}
}
} 
