数据结构

常用数据结构

树

此处尤指二叉树Binary Tree

基本性质

• 性质1： 第i层上最多有$2^{i-1}$个节点

• 性质2： 深度为k(根节点深度为1)的二叉树最多有$2^k-1$个节点

• 性质3： $n_0=n_2+1$

• 性质4： n个节点的完全二叉树的深度为 $\lfloor \log_2^n \rfloor$+1

• 性质5： n个节点的二叉树的叶子节点个数最多有$\frac{n+1}{2}$

遍历

这个都会吧（

前序： 根左右 波兰

中序： 左根右 投影

后序： 左右根 逆波兰

已知 前中、中后 都可画出唯一树

---

图

特殊图

• 欧拉图：
  从任意点开始，都能找到一笔画
  起点和终点重合

• 半欧拉图:
  只有两个奇点（度为奇数的点）
  一个奇点开始，一个奇点结束

• 哈密尔顿图：
  经过每个点1次，遍历完全部点

链式前向星

void addEdge(int u, int v, int w) {
	edge[++tot].v = v;
	edge[tot].w = w;
	edge[tot].next = head[u];
	head[u] = tot;
}