树的存储¶

普通树¶

只记录每一个结点的父亲，这样子空间消耗特别小，但是存储的信息过于少，无法完成很多操作。

记录每一个结点的儿子，如果需要网上还原路径的话就记录每一个结点的父亲。如果是无根数的话我们就需要记录与每个节点所有相连的结点，也就是存双向边。

邻接表也有著名的优化——链式前向星，也就是用链表的方式存邻接表，但是由于链表是随机存储的，因此在实际使用中并不比使用 vector 的快，甚至还可能会慢一点。

使用 vector 存储使用链式前向星存储

vector<int> e[kMaxN];

void add(int u, int v) {
  e[u].push_back(v);
}

struct Edge {
  int to, nxt;
} e[kMaxN];

int h[kMaxN], c;

void add(int u, int v) {
  e[++c] = {v, h[u]}, h[u] = c;
}

开 \(n\) 个结构体，然后在结构体内存储每一个结点的左儿子和右儿子。

如果结点的编号有顺序的话，那么 \(x\) 的左儿子就是 \(x\times 2\)，右儿子就是 \(x\times 2+1\)，用数组就可以进行存储。