#define 柚子树 右子树
0x00 树基本
0x01 树
树是啥？一种抽象但相当有用的数据结构。
树的结构特殊性使得它易于计算信息，并用来出各种各样的题。其各种变体还可以用于维护信息。
我们听说过的线段树、树状数组、树上启发式合并等高级方法均离不开树。可以说，没有树就不可能有OI。
下面便是一个树（oi-wiki）：
定义：一个无环、连通的简单无向图。图是啥
对于树上的点u，可以定义它的父节点、兄弟节点、子节点，以及祖先与子孙。
没有父节点的点成为根。没有子节点的点成为叶子。
树可根据有无确定的根进行分类。 无根树可任意指定一个根。
树上的点u的子树：u及其所有子孙节点。
点的深度：到根节点的边数。 树的高度：所有点深度的最大值。
树的宽度：这个真的有啥用吗
0x02 二叉树
每个点子节点个数均不超过2的树称为二叉树。
满二叉树：每一层节点数都达到最大值的树。
完全二叉树：除了最后一层都是满的，且最后一层所有点都集中在左边的二叉树。满二叉树为特殊的完全二叉树。
二叉树的一些性质：
- 对于第k层，二叉树最大节点数为 \(2^{k-1}\)。
- 有k层的满二叉树节点数为 \(2^k-1\)。
- 一个n个节点的二叉树，其深度最大为n（链），最小为 \(\log n+1\) （完全二叉树）。
- 二叉树中，有2个孩子的点个数 = 叶子个数-1.
- 有n个叶子的完全二叉树有 \(2n-1\) 个点。
0x10 树的存储与遍历
0x11 存储
父亲存储法
直接存储父亲节点的方法，适用于任何树，但不好用，一般只用于并查集。
数组直接存法
只用于完全二叉树。
对于任意一个完全二叉树，我们按bfs的顺序直接把所有点放进一个数组。
可以发现，对于任意一个下标为u的点，其左子节点下标为u<<1，柚子节点下标为u<<1|1。
如果你不能简单的判断一个点是不是叶子，最好把空间开2倍。
普通线段树也是用这种方法，但要开4倍空间。
左右儿子法
适用于二叉树。
方法：使用数组模拟链表。
每个点开一个结构体，存储它的左右儿子下标和其他信息。
以结构体类型开一个足够大的内存池。对于新点，从内存池中拿一个空的内存分配给它，然后更新它的、它父亲的左右子树即可。
没有删除节点操作时，不需要开额外空间。
应用：动态开点线段树、各种平衡树等。
struct Node{int val;//点权等信息int lc,rc;// 存左子结点的位置、存柚子节点的位置
}tr[N];// 内存池
int tot,rt;// 当前节点个数、树根
inline int New(int v){// 返回新加点的下标++tot;tr[tot].val=v;// anything elsereturn tot;
}
转二叉树法
又称孩子兄弟表示法。适用于多叉树。将多叉树转成二叉树后用左右儿子法存储。
对于一棵多叉树，断掉原来所有的边，将每个点与它第一个孩子连一条边，最靠近它的第二个孩子连一条边，这样即可建出一棵与原树基本等价的二叉树。
用处不大，可能在初赛考。
儿子数组法
每个点开一个数组存其儿子。
适用于任何树，大多数情况下被邻接表替代，一般只用于trie。
邻接表法
万能的方法。适用于一切树、森林、边带方向的树等。适合给你一个树让你维护树上信息，或计算各种各样的答案的题。
一般树的存储还有前文所述父亲法、儿子法、转二叉树法，都有点用但不多。
邻接表：来自图论，本质为一排链表。
将每个点的邻接点用链表串起来，就成了一个存着树/图的邻接表。
实现方法：2种。
最简单的方法：vector
优点：好写、不用考虑空间的问题（用手写链表存无向图不开两倍就会挂大分）
代码：
struct EDGE{int v,w;};
vector<EDGE> g[N];g[u].emplace_back(EDGE{v,w});
// g[v].emplace_back(EDGE{u,w}); //无向图// 遍历u的邻接点
for(EDGE to:g[u]){int v=to.v, w=to.w;// 邻接点、边权// anything else
}
另一种方法：手写链表法。
一般写头插法。
代码：
struct Node{int to,w,Next;}g[M];// 无向图要开2倍
int h[N];// 头指针// 加边
void Add(int u, int v, int w){num++; g[num].to=v; g[num].w=w;g[num].Next=h[u];h[u]=num;
}// 遍历u的邻接点
for(int i=h[u]; i; i=g[i].Next){int v=g[i].to, w=g[i].w;//anything else
}
0x12 遍历
DFS遍历
相当于以根节点为起点在树上进行深搜。
代码：
void Dfs(int fa, int u){for(EDGE to:g[u]){int v=to.v, w=to.w;if(v==fa) continue;// 避免走回父亲节点Dfs(u,v);}
}
对于二叉树，有三种特殊的遍历方法：
先序遍历：先访问根，再递归遍历左右子树：
void Rlr(int u){if(!u) return;cout<<u<<" ";Rlr(tr[u].lc); Rlr(tr[u].rc);
}
中序遍历：先递归遍历左子树，再访问根，然后递归遍历右子树：
void lRr(int u){if(!u) return;lRr(tr[u].lc);cout<<u<<" ";lRr(tr[u].rc);
}
后序遍历：先访问根，再递归遍历左右子树：
void lrR(int u){if(!u) return;lrR(tr[u].lc); lrR(tr[u].rc);cout<<u<<" ";
}
BFS遍历
相当于以根节点为起点在树上进行广搜。
代码：
inline void Bfs(int s){q.push(s);int u;while(!q.empty()){u=q.front(); q.pop();vis[u]=1;// 需要打标记for(int v:g[u]){if(!vis[v])q.push(v);}}
}